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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Граф з позначеними компонентами сильної зв'язності

Орієнтований граф називається сильно зв'язним, якщо існує шлях з будь-якої вершини графу до кожної з інших вершин. Зокрема, це означає наявність шляхів в обоз напрямках: з a в b і з b в a.

Компонента сильної зв'язності орієнтованого графу G — це найбільший сильно зв'язаний підграф. Якщо кожну компонента сильної зв'язності стягнути до однієї вершини, отримаємо орієнтований ациклічний граф, ущільнення (англ. condensation) G. Орієнтований граф є ациклічним тоді і лише тоді, коли він не має компонент сильної зв'язності з більш як однією вершиною, бо орієнтований цикл є сильно зв'язним і кожна нетривіальна компонента сильної зв'язності містить щонайменше один орієнтований цикл.

Алгоритм Косараджу, алгоритм Тарджана і алгоритм компонент сильної зв'язності по шляхах всі дієво знаходять компоненти сильної зв'язності орієнтованого графу, але Алгоритм Тарджана і алгоритм базований на шляхах сприятливіші на практиці, бо вони потребують лише один пошук у глибину натомість двох.

Відповідно до теореми Роббінса, неорієнтований граф можна зорієнтувати таким чином, що він стане сильно зв’язним, тоді і тільки тоді, коли він 2-реберно-зв'язний.

Див. також[ред.ред. код]

Посилання[ред.ред. код]

  • Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), «A linear-time algorithm for testing the truth of certain quantified boolean formulas», Information Processing Letters 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4 .
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp. 552–557.