Компонентою сильної зв’язності орієнтованого графа називається максимальна множина його вершин, в якій існують шляхи з будь-якої вершини в будь-яку іншу. Так наприклад, граф , зображений на рисунку що міститься нижче, складається з чотирьох компонент сильної зв’язності:
,
,
і
.
Орієнтований граф та його компоненти сильної зв’язності
Як видно з рисунка, кожна вершина орієнтованого графа належить певній компоненті сильної зв’язності, але деякі ребра можуть не належати жодній з них. Такі ребра з’єднують вершини з різних компонент.
Зв’язки між компонентами сильної зв’язності, зазвичай, зображаються шляхом створення конденсації графа . Відмітимо, що конденсацією орієнтованого графа називається граф, побудований наступним чином: набори вершин, що утворюють одну компоненту сильної зв’язності
вихідного графа, зливаються в одну вершину конденсації
. З вершини
у вершину конденсації
є ребро тоді і тільки тоді, коли в графі
є ребро, що веде з деякої вершини компоненти зв’язності
у деяку вершину компоненти зв’язності
. Конденсація орієнтованого графа
представлена на вказаному вище рисунку у вигляді кіл зображених пунктирною лінією. Тобто, вершини
вихідного графа, що утворюють одну компоненту сильної зв’язності, зливаються в одну вершину. Вершини
– в другу. І вершини
і
– в третю та четверту відповідно. Ребра
,
і
також відображені в конденсації, оскільки з’єднують вершини різних компонент сильної зв’язності.
Зауваження: в конденсації не може бути циклів, оскільки якби існував цикл, то всі компоненти сильної зв’язності, що входять в цей цикл, утворювали б одну компоненту сильної зв’язності.
Далі, опишемо алгоритм, що базується на обході орієнтованого графа в глибину, який і будемо в даному параграфі використовувати, для розв’язку задачі на знаходження сильно зв’язних компонент орієнтованого графа.
- Спочатку, виконуємо глибинний обхід всіх вершин вихідного графа
. Завершуючи обробку чергової вершини (присвоївши їй мітку повністю сканованована), зберігаємо її в деяку послідовність вершин графа.
- Будуємо транспонований граф
, отриманий з вихідного графа шляхом заміни орієнтації всіх його ребер на протилежні.
- Виконуємо пошук в глибину на графі
, починаючи з вершини, що міститься в кінці отриманої в пункті 1 послідовності. Якщо проведений таким чином пошук не охоплює всіх вершин, то починаємо новий пошук, і робимо це з вершини, що має найбільший порядковий номер серед вершин, що залишились не пройденими.
Відмітимо, що в результаті виконання кроку 3, кожне піддерево в отриманому дереві обходу в глибину для графа , є сильно зв’язною компонентою для орієнтованого графа
.
Знаходження компонент сильної зв’язності графа – приклад:
Використовуючи розглянутий вище алгоритм, знайти компоненти сильної зв’язності для орієнтованого графа наступного вигляду:
Орієнтований граф задачі
Для цього, вибравши в якості початкової вершину під номером «1», виконуємо глибинний обхід заданого графа. В результаті виконання даного кроку, отримаємо наступне дерево обходу в глибину.
Дерево обходу в глибину заданого орієнтованого графа
Відмітимо, що при цьому, статус повністю сканована, для кожної з вершин побудованого дерева, присвоювався у наступній послідовності: .
Далі, шляхом заміни орієнтації всіх ребер заданого графа на протилежні, будуємо для нього трансповований граф. Після цього, запускаємо другий пошук в глибину, здійснюючи, при цьому, обхід вершини відповідно до послідовності , починаючи з кінця. При цьому, вершина номер «4» складає перше піддерево пошуку, вершина «5» – друге, вершина «1» – третє, вершина «2» – четверте і вершини «6» та «3» – п’яте та шосте відповідно.
Дерево обходу в глибину транспонованого орієнтованого графа
Тобто, заданий орієнтований граф складається з шести компонент сильної зв’язності, кожна з яких включає в себе по одній з його вершин.