Контрольная на тему Контрольная работа 120305-03

Контрольная работа 4

Задача 1
Запишите матрицы достижимости и взаимодостижимости для графа
. Выделите сильные компоненты графа.


Построение матрицы достижимости R.
Размер матрицы (5(5). Из вершины 1 можно попасть в вершины 2, 3. По определению достижимости вершина 1 достижима сама из себя. Элементы первой строки матрицы достижимости с номерами 1,2,3 равны единице, остальные элементы первой строки равны нулю.
Далее, из вершины 2 графа можно попасть в вершину 2 и 3. Вторая строка матрицы состоит из нулей, кроме элемента 2 и 3.
Из вершины 3 можно попасть в вершины 3 и 2. Элементы третьей строки матрицы с номерами 3, 2 равны единице, остальные элементы третьей строки равны нулю.
Из вершины 4 можно попасть только в вершину 4. Из вершины 5 можно попасть только в вершину 5. Матрица достижимости R построена:


.

Для того, чтобы построить матрицу взаимодостижимости, построим матрицу контрдостижимости Р. Матрица контрдостижимости равна транспонированной матрице достижимости P=RT.


.

Элементы матрицы взаимодостижимости вычисляются по формуле: si,j=ri,j & pi,j.

Матрица взаимодостижимости S:


.

Выделим сильные компоненты графа по матрице взаимодостижимости.
Вычеркнем те столбцы и строки из матрицы S, которые соответствуют единичным элементам первой строки матрицы. Это элемент с номером j=1. Вычеркнем столбец 1 и строку 1. Таким образом, сильная компонента связности - подграф G1 на вершине 1.
Далее рассмотрим измененную матрицу