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

Сильная компонента графа была определена в предыдущей главе как максимальный сильно связный подграф графа Поскольку в сильно связном графе произвольная вершина достижима из любой другой вершины то в ориентированном

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

Если вершина одновременно является начальной и конечной вершиной пути, то множество вершин, существенных относительно этих двух идентичных концов (т. е. множество вершин некоторого цикла, содержащего совпадает с пересечением Поскольку все эти существенные вершины достижимы из кроме того, из каждой такой вершины достижима вершина то все они взаимно достижимы. Более того, если нет другой вершины, существенной относительно концов то множество которое может быть построено с использованием соотношений (2.1) и (2.2), однозначно определяет графа содержащую вершину

Если эти вершины удалить из графа то в оставшемся порожденном подграфе можно таким же способом выделить новую содержащую Эту процедуру можно повторять до тех пор, пока все вершины графа не будут сгруппированы в соответствующие После завершения этой процедуры граф будет разбит на свои сильные компоненты [3].

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

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

3.1. Пример

Для графа приведенного на рис. 2.2, найти сильные компоненты и построить конденсацию

Найдем в содержащую вершину

Рис. 2.2. Граф

Рис. 2.3. G - конденсация графа

Из соотношений (2.1) и (2.2) получаем

и

Следовательно, содержащая вершину является порожденным подграфом

Аналогично, содержащая вершину есть порожденный подграф содержащая подграф

содержащая - подграф и содержащая - подграф . Следует отметить, что последняя состоит из единственной вершины графа

Конденсация приведена на рис. 2.3.

Процедуру, описанную выше и связанную с нахождением графа, можно сделать более удобной, если непосредственно использовать матрицы определенные в предшествующем разделе. Пусть запись означает поэлементное умножение этих матриц; тогда сразу видно, что строка матрицы содержит единицы только в тех столбцах для которых выполняется условие: вершины взаимно достижимы; в других местах строки стоят нули. Таким образом, две вершины находятся в одной и той же тогда и только тогда, когда соответствующие им строки (или столбцы) в матрице идентичны. Вершины, которым соответствуют строки, содержащие 1 в столбце образуют множество вершин содержащей Отсюда мгновенно следует, что матрицу можно преобразовать путем транспонирования строк и столбцов в блочно-диагональную каждая из диагональных подматриц этой матрицы соответствует графа и содержит только единичные элементы; все остальные элементы блочно-диагональной матрицы равны нулю. Для приведенного ранее примера матрица преобразованная соответствующим образом, имеет вид