Категорія: Компоненти зв’язності, кліки, точки сполучення

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

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

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

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

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

Читати далі

Знаходження точок сполучення зв’язного неорієнтованого графа та перевірка його на двозв’язність

Точкою сполучення неорієнтованого графа називається вершина, при видаленні якої, разом з усіма суміжними її ребрами, збільшується кількість компонент зв’язності графа. Відповідно, для зв’язного графа точкою сполучення називається вершина, при видаленні якої граф перестає бути зв’язним. Наприклад, точками сполучення для графа, який зображено на малюнку що міститься нижче, є вершини і . Якщо видалити вершину , то граф, який складається з однієї компоненти зв’язності, розбивається на два підграфи і . Якщо видалити вершину , то граф розбивається на підграфи і . Але якщо видалити будь-яку іншу його вершину, то в цьому випадку, розбити зв’язну компоненту з якої складається даний граф на кілька частин, не вдасться. Зв’язний граф, який не має точок сполучення, називається двозв’язним.

Точки сполучення неорієнтованого графа

Графічне представлення алгоритму пошуку точок сполучення в неорієнтованому графі

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

Читати далі

Пошук мостів та компонент реберної двозв’язності в неорієнтованому графі

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

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

Між двома компонентами реберної двозв’язності не може бути більше одного ребра – в іншому випадку, вони утворюватимуть одну компоненту реберної двозв’язності. Якщо дві різні компоненти реберної двозв’язності з’єднані ребром, то це ребро – міст.

Читати далі

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

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

Читати далі