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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определения[править | править вики-текст]

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

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

Алгоритмы[править | править вики-текст]

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

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

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

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

Пример[править | править вики-текст]

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

 Ориентированный граф с найденными компонентами сильной связности.

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

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