Міст (теорія графів)

Граф із 6 мостами (позначені червоним)

В теорії графів, міст — ребро, видалення якого збільшує кількість компонент зв'язності (або, інакше кажучи, відокремлює підграф). Рівнозначне визначення, ребро є мостом тоді і тільки тоді, коли воно не є частиною будь-якого циклу.

Подвійне покриття циклами

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

Алгоритм знаходження мостів

Перший алгоритм для знаходження мостів в зв'язному графі за лінійний час $O(|V|+|E|)$ був віднайдений Робертом Тарджаном в 1974 році.

Алгоритм складається з наступних кроків:

1. Знайти кістякове дерево для $G$
2. Створити дерево $T$ з коренем з кістякового дерева
3. Обійти дерево $T$ в прямому порядку і пронумеровати вершини. Тепер номери батьківських вершин менші за номери нащадків.
4. Для кожної вершини $v$ при обході у прямому порядку робимо:
   1. Підраховуємо кількість нащадків $ND(v)$ для цієї вершини.
   2. Підраховуємо $L(v)$ і $H(v)$
   3. Для кожної $w$ такої, що $v\to w$: якщо $L(w)\geq w$ і $H(w)<w+ND(w)$, тоді ребро $(v,w)$ буде мостом.

Визначення: Ребро поза деревом між $v$ і $w$ позначається $v--w$. Ребро в дереві з батьківською $v$ позначається $v\to w$.

$ND(v)=1+\sum _{v\to w}ND(w)$ де $v$ батьківська вершина для $w$.

$ND(v)$ кількість нащадків v (включно із собою) в кістяковому дереві.

$L(v)=\min(\{v\}\cup \{L(w)\mid v\to w\}\cup \{w\mid v--w\})$

$H(v)=\max(\{v\}\cup \{H(w)\mid v\to w\}\cup \{w\mid v--w\})$

$L(v)$ і $H(v)$ позначки вершин з найменшою і найбільшою позначкою обходу прямого порядку, досяжних з $v$ проходом по піддереву з коренем у $v$, разом з щонайбільше одним ребром не в дереві.

Ребро $v\to w$ є мостом тоді і тільки тоді, коли з піддерева з коренем у $w$ неможливо потрапити у вершину, яка не є нащадком $w$. Це легко перевірити, бо піддерево з коренем у $w$ (об'єднує всіх нащадків w) містить наступні вершини $\{w,w+1,\ldots ,w+ND(w)-1\}$, тож ми можемо просто перевірити, знаходяться $L(w),H(w)$ в цій множині чи ні для перевірки чи є ребро мостом.

Посилання

•  Bridges and Articulation points Algorithm на YouTube