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

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

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

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

poshuk_mostiv_v_neorijentovanomu_grafi23

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

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

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

І на останньому кроці, залишається тільки вибрати ребра заданого графа, що з'єднують вершини різних дерев пошуку. Відмітим, що саме вони і будуть мостами графа .

Пошук мостів в неорієнтованому графі — приклад:

Знайти мости для неорієнтованого графа наступного вигляду.

Неорієнтований граф задачі

Починаючи з вершини під номером «1», проходимо по ребрах і , орієнтуючи їх проти напрямку руху. З вершини «3» не виходять ребра, які ведуть у не пройдені вершини. Тому, повертаємося у вершину «2», проходимо по ребрах , , і . Далі, повертаємося у вершину «1» і проходимо по ребру . Після цього, знову-таки повертаємося у вершину «1» і на цьому перший пошук в глибину завершуємо.

Знаходження мостів в неорієнтованому графі

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

Далі, залишається тільки вибрати ребра заданого графа, що з'єднують вершини, які належать до різних дерев обходу, тобто визначити мости графа. У нашому випадку це будуть ребра  та .

Блок-схема алгоритму пошуку мостів в неорієнтованому графі

Пошук мостів в неорієнтованому графі блок-схема

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар