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

Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связны. Две вершины s и t любого графа сильно связны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы.

Определения

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

Любая вершина орграфа сильно связна сама с собой.

Алгоритмы

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

1. При помощи транзитивного замыкания проверяем, достижима ли t из s, и s из t, для всех пар s и t.
2. Затем определяем такой неориентированный граф, в котором для каждой такой пары содержится ребро.
3. Поиск компонент связности такого неориентированного графа даст нам компоненты сильной связности нашего орграфа.

Очевидно основное время работы данного алгоритма приходится на реализацию транзитивного замыкания.

Также существует три алгоритма, решающих данную задачу за линейное время, то есть в V раз быстрее, чем приведенный выше алгоритм. Это алгоритмы Косарайю, Габова и Тарьяна.

Пример

На данном примере изображен орграф, для которого найдены все три компоненты сильной связности (закрашенные области, обведенные пунктиром).

Ссылки

• [rain.ifmo.ru/cat/view.php/vis/graph-general/scc-2008/ Визуализатор алгоритмов поиска компонент сильной связности]

Литература

• Роберт Седжвик. Алгоритмы на графах = Graph algorithms. — 3-е изд. — Россия, Санкт-Петербург: «ДиаСофтЮП», 2002. — С. 496. — ISBN 5-93772-054-7.

Отрывок, характеризующий Компонента сильной связности в орграфе

В это время в девичьей не только был известен приезд министра с сыном, но внешний вид их обоих был уже подробно описан. Княжна Марья сидела одна в своей комнате и тщетно пыталась преодолеть свое внутреннее волнение.
«Зачем они писали, зачем Лиза говорила мне про это? Ведь этого не может быть! – говорила она себе, взглядывая в зеркало. – Как я выйду в гостиную? Ежели бы он даже мне понравился, я бы не могла быть теперь с ним сама собою». Одна мысль о взгляде ее отца приводила ее в ужас.
Маленькая княгиня и m lle Bourienne получили уже все нужные сведения от горничной Маши о том, какой румяный, чернобровый красавец был министерский сын, и о том, как папенька их насилу ноги проволок на лестницу, а он, как орел, шагая по три ступеньки, пробежал зa ним. Получив эти сведения, маленькая княгиня с m lle Bourienne,еще из коридора слышные своими оживленно переговаривавшими голосами, вошли в комнату княжны.
– Ils sont arrives, Marieie, [Они приехали, Мари,] вы знаете? – сказала маленькая княгиня, переваливаясь своим животом и тяжело опускаясь на кресло.
Она уже не была в той блузе, в которой сидела поутру, а на ней было одно из лучших ее платьев; голова ее была тщательно убрана, и на лице ее было оживление, не скрывавшее, однако, опустившихся и помертвевших очертаний лица. В том наряде, в котором она бывала обыкновенно в обществах в Петербурге, еще заметнее было, как много она подурнела. На m lle Bourienne тоже появилось уже незаметно какое то усовершенствование наряда, которое придавало ее хорошенькому, свеженькому лицу еще более привлекательности.
– Eh bien, et vous restez comme vous etes, chere princesse? – заговорила она. – On va venir annoncer, que ces messieurs sont au salon; il faudra descendre, et vous ne faites pas un petit brin de toilette! [Ну, а вы остаетесь, в чем были, княжна? Сейчас придут сказать, что они вышли. Надо будет итти вниз, а вы хоть бы чуть чуть принарядились!]