зв'язність графа - www.mathros.net.ua

Знаходження компонент сильної зв’язності орієнтованого графа

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

komponenty_sylnoi_zvjaznosti_grafa110

Орієнтований граф та його компоненти сильної зв’язності

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

Перевірка неорієнтованого графа на зв’язність та ациклічність

Після того, як з основними моментами алгоритмів обходу неорієнтованого графа в глибину та обходу в ширину розібралися, перейдемо до розгляду стандартних завдань, що вирішуються за їх допомогою. Відмітимо, що важливим застосуванням цих двох алгоритмів є перевірка графа на зв’язність та ациклічність. Оскільки дані алгоритми завершуються після того, як всі вершини заданого графа пройдені і поєднані деяким шляхом зі стартовою, то здійснити перевірку графа на зв’язність можна наступним чином. Почнемо пошук в глибину (ширину) з довільної вершини і після завершення перевіримо, чи всі вершини графа пройдені. Якщо всі, то граф зв’язний, в іншому випадку – ні. Взагалі кажучи, такий підхід можна використовувати і для визначення компонент зв’язності графа. Покажемо, яким чином це реалізується.