Сильной связности ориентированного графа

Алгоритм выделения компонент

Шаг 1. Полагаем p=1, D₁(G) = D(G).

Шаг 2. Включаем во множество вершин очередной ( р -й) компоненты сильной связности H_p графа G вершины, соответствующие единицам первой строки матрицы D_р(G). В качестве матрицы смежности графа H_p – A(H_p) берем подматрицу матрицы A(G) , элементы которой находятся на пересечении строк и столбцов, соответствующих вершинам из .

Шаг 3. Вычеркиваем из D_р(G) строки и столбцы, соответствующие вершинам . Если в результате не остаётся ни одной строки (и соответственно ни одного столбца), то р - количество компонент H₁, H₂,…, H_p сильной связности графа G, соответственно A(H₁), A(H₂),…, A(H_p) – их матрицы смежности. В противном случае обозначим оставшуюся после вычеркивания из D_р(G) соответствующих строк и столбцов матрицу через D_р+1 (G),положим р=р+1 (увеличим значение индекса р на единицу) и перейдем к шагу 2.

Решение:

Выпишем ранее сформированную матрицу смежности ориентированного графа G.

A(G) =

Построим матрицу сильной связности графа G.

D(G) =

Так как матрица D(G) полностью состоит из единиц, то единственной компонентой связности графа G будет сам ориентированный граф G.

H₁

Задание 8.

Найти компоненты связности неориентированного графа G´.

Определение. Компонентами связности неориентированного графа называются все его связные подграфы, не являющиеся собственными подграфами никакого другого связного подграфа графа G´.

Замечание. Неориентированные графы обладают следующим важным свойством: каждый неориентированный граф можно представить в виде объединения его компонент связности. Разложение неориентированного графа на его компоненты связности единственно и однозначно.

Определение. Пусть дан граф G´ - неориентированный. Матрицей связности графа G´ называется матрица D(G´)_{[n x n]}, где n – мощность множества вершин, с элементами d_ij , которые определяются следующим условием:

d_ij =

Замечание. Отметим, что, после внесения соответствующих изменений в обозначения и терминологию рассмотренного ранее алгоритма выделения компонент сильной связности ориентированного графа G, его можно применять и для нахождения компонент связности неориентированного графа G´.

Решение:

Выпишем ранее сформированную матрицу смежности неориентированного графа G´.

A(G´) =

Построим матрицу связности неориентированного графа D(G´).

D(G´) =

Так как матрица D(G´) полностью состоит из единиц, то единственной компонентой связности графа G´ будет сам неориентированный граф G´.

H₁

Задание 9.

Перечислить все пути в ориентированном графе G, состоящие из четырех дуг.

Определение. Пусть задан ориентированный граф G = (X_G, P_G) и пусть x_i1, x_in ϵ X_G. Kортеж вида (x_i1, x_i2,…,x_in-1,x_in) называется путем из вершины x_i1 в вершину x_in графа G, если для любого k от 1 до n-1 двойка (x_ik, x_ik+1)ϵ P_G.