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

Шаг 1. G = (X, V) – данный граф. Определение сильных компонент графа (СК) начать с произвольной вершины х_i Î Х. Найти R (x_i) и Q (x_i). Положить СК(х_i) = .

Шаг 2. Рассмотреть множество и для произвольной вершины x_k Î найти СК(х_i) на . Перейти к шагу 3.

Шаг 3. Если ¹0, то перейти к шагу 2, иначе останов, так как все сильные компоненты определены.

Граф G*= (X*,V *) определяется так: каждая его вершина представляет множество вершин некоторой сильной компоненты графа G, дуга (x_i *, x_j *) существует в G * тогда и только тогда, когда в G существует дуга (x_i, x_j), такая, что x_i принадлежит ком­поненте, соответствующей вершине x_i *, а x_j –компоненте, соответствующей вершине x_j*. Граф G* называют конденсацией графа G.

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

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

Найдем СК в G, содержащую вершину x ₁.

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

R (x ₁) ={ x ₁, x ₂, x ₄, x ₅, x ₆ , x ₇, x ₈, x ₉, x ₁₀ }

Q (x ₁) ={ x ₁, x ₂, x ₃, x ₅, x ₆ }

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

R (x ₁) Q (x ₁) = ({ x ₁, x ₂, x ₅, x ₆ })

Аналогично, СК, содержащая вершину x ₈, есть порожденный подграф ({ x ₈, x ₁₀}), СК содержащая x ₇ – подграф ({ x ₄, x ₇, x ₉}), СК, содержащая x ₁₁, –подграф ({ x ₁₁, x ₁₂, x ₁₃ }) и СК, содержащая x ₃, – подграф ({ x ₃}). Следует отметить, что последняя СК со­стоит из единственной вершины графа G. Конденсация G* приведена на рис. 4.26.

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

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

	x 1 x 2 x 5 x 6	x 8 x 10	x 4 x 7 x 9	x 11 x 12 x 13	x 3
x 1 x 2 x 5 x 6	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
x 8 R Ä Q = x 10		1 1   1 1
x 4 x 7 x 9			1 1 1 1 1 1 1 1 1
x 11 x 12 x 13				1 1 1 1 1 1 1 1 1
x 3

Дата добавления: 2014-12-27