Инд работа2(связность графа)
.doc
ИНДИВИДУАЛЬНАЯ РАБОТА № 2
Связность графа. Компоненты связности.
Для выполнения и защиты индивидуальной работы №2 необходимо изучить теоретический материал по данной теме.
Перечень вопросов по второй индивидуальной работе:
-
Определение булевой матрицы
-
Операции над булевыми матрицами ( конъюнкция, дизъюнкция, логическое умножение, операция sign)
-
Определения связности, сильной связности, односторонней связности, слабой связности графов.
-
Определения матриц связности и сильной связности
-
Формулы для нахождения матриц связности и сильной связности
-
Определения компонент связности (сильной связности), количества компонент связности (сильной связности)
-
Алгоритм выделения компонент сильной связности в орграфе.
-
Определить по формуле матрицу связности для графа, заданного своей матрицей смежности. Построить реализацию графа.
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