|
ИНДИВИДУАЛЬНАЯ РАБОТА № 2
Связность графа. Компоненты связности.
Для выполнения и защиты индивидуальной работы №2 необходимо изучить теоретический материал по данной теме.
Перечень вопросов по второй индивидуальной работе:
1. Определение булевой матрицы
2. Операции над булевыми матрицами (конъюнкция, дизъюнкция, логическое умножение, операция sign)
3. Определения связности, сильной связности, односторонней связности, слабой связности графов.
4. Определения матриц связности и сильной связности
5. Формулы для нахождения матриц связности и сильной связности
6. Определения компонент связности (сильной связности), количества компонент связности (сильной связности)
7. Алгоритм выделения компонент сильной связности в орграфе.
1. Определить по формуле матрицу связности для графа, заданного своей матрицей смежности. Построить реализацию графа.
I
VI
II
VII
III
VIII
IV
IX
V
X
2. Пусть орграф D задан матрицей смежности. Определить по формуле матрицу сильной связности S(D). Используя алгоритм, найти количество компонент сильной связности орграфа D и определить матрицы смежности этих компонент. Построить реализации орграфа D и его компонент сильной связности.
I
VI
II
VII
III
VIII
IV
IX
V
X
Дата добавления: 2015-09-30; просмотров: 96 | Нарушение авторских прав
<== предыдущая лекция | | | следующая лекция ==> |
Печникова Елена Юрьевна | | | Российская федерация ОАО «авиакомпания «сибирь» |