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

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

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

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

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

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

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

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

Мости в неорієнтованому графі – приклад знаходження:

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

Знаходження мостів в неорієнтованому графі - приклад

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

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

Знаходження мостів в неорієнтованому графі - приклад

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

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

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

Блок-схема алгоритму знаходження мостів в неорієнтованому графі

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

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *

*