Компонента сильної зв'язності графа
Орієнтований граф називається сильно зв'язним, якщо існує шлях з будь-якої вершини графа до кожної з інших вершин. Зокрема, це означає наявність шляхів в обох напрямках: з a в b і з b в a.
Компонента сильної зв'язності орієнтованого графа G — це найбільший сильно зв'язаний підграф. Якщо кожну компонента сильної зв'язності стягнути до однієї вершини, отримаємо орієнтований ациклічний граф, ущільнення (англ. condensation) G. Орієнтований граф є ациклічним тоді і лише тоді, коли він не має компонент сильної зв'язності з більш як однією вершиною, бо орієнтований цикл є сильно зв'язним і кожна нетривіальна компонента сильної зв'язності містить щонайменше один орієнтований цикл.
Алгоритм Косараджу, алгоритм Тар'яна і алгоритм компонент сильної зв'язності по шляхах всі дієво знаходять компоненти сильної зв'язності орієнтованого графа, але алгоритм Тар'яна і алгоритм базований на шляхах сприятливіші на практиці, бо вони потребують лише один пошук у глибину замість двох.
Відповідно до теореми Роббінса, неорієнтований граф можна зорієнтувати таким чином, що він стане сильно зв’язним, тоді і тільки тоді, коли він 2-реберно-зв'язний.
Див. також[ред. | ред. код]
Джерела[ред. | ред. код]
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. Розділ 22.5: Компоненти сильнї зв'язності. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.