Нахождение сильных компонент

Подграф называется собственным, если он отличен от самого графа. Граф (орграф) называется связным (сильно связным), если для любых его вершин х_i и х_j существует маршрут (путь), соединяющий х_i и х_j. Орграф называется односторонне связным, если для любых его вершин, по крайней мере, одна достижима из другой.

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

Рис. 32

У графа на рисунке а) 3 компоненты связности. У ориентированного графа на рисунке б) 3 компоненты сильной связности, показанные на рисунке в).

Поскольку в сильно связном графе произвольная вершина x_j достижима из любой другой вершины x_i, то в ориентированном графе существует одна и только одна сильная компонента, содержащая данную вершину x_i. Действительно, если бы вершина x_i принадлежала двум или большему числу сильных компонент, то существовал бы путь из любой вершины сильной компоненты в произвольную вершину другой сильной компоненты, следовательно, что объединение этих сильных компонент было бы сильно связным графом, что противоречит определению сильной компоненты.

Если вершина x_i является одновременно начальной и конечной вершиной пути, то множество вершин совпадет с пересечением .

Поскольку все промежуточные вершины цикла достижимы из x_i и, кроме того, из каждой такой вершины достижима вершина x_i, то все эти вершины взаимодостижимы.

Множество , которое может быть построено с помощью формул: , однозначно определяет сильную компоненту графа, содержащую вершину x_i .

Если все эти вершины удалить из графа G(X,Г), то в оставшемся порождённом подграфе: , то можно таким образом выделить новую сильную компоненту, содержащую вершину .

Эту процедуру можно повторять до тех пор, пока все вершины графа не будут сгруппированы в соответствующие сильные компоненты графа G.

После завершения этой процедуры граф G будет разбит на сильные компоненты.

Пусть G^*=G(X^*,Г^*) такой, что каждая его вершина представляет собой множество вершин некоторой сильной компоненты графа G.

Дуга (x_i^*,x_j^*) в графе G^* существует тогда и только тогда, когда в графе G существует дуга (x_i,x_j), такая что , a .

Граф G^* называется конденсацией графа G. Конденсация G^* не содержит циклов, поскольку наличие цикла означает, что любые вершины этого цикла взаимодостижимы, а поэтому совокупность всех вершин цикла принадлежит некоторой сильной компоненте в графе G^* и, следовательно, содержится в сильной компоненте графа G, что противоречит определению конденсации, в силу которого вершины из G^* соответствуют сильным компонентам графа G.

x₁ x₂ x₃ x₄ x₅ x₆ x₇

x₁ x₂ x₃ x₄ x₅ x₆ x₇

Определить сильные компоненты графа

Выполнение операции объединения будет продолжаться до тех пор, пока в результате этих операций не будут использованы все вершины графа.