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

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

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

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

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

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

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

Алгоритм:

1. Знайти кістякове дерево для $G$
2. створити дерево $T$ з корним з кістякового дерева
3. Обійти дерево $T$ в прямому порядку і пронумеровати вершини. Тепер батьківські вершини мають меньши номери ніж дочірні.
4. Для кожної вершини з $v_1$ (листя дерева) до 1 (корінь дерева) робимо:
   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)$ в цій множині чи ні для перевірки чи є ребро мостом.