Связность графа. Компоненты связности.

ИНДИВИДУАЛЬНАЯ РАБОТА № 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