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

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

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

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

Алгоритм знаходження мостів[ред. | ред. код]

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

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

Знайти кістякове дерево для $G$
Створити дерево $T$ з коренем з кістякового дерева
Обійти дерево $T$ в прямому порядку і пронумеровати вершини. Тепер номери батьківських вершин менші за номери нащадків.
Для кожної вершини $v$ $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)$ в цій множині чи ні для перевірки чи є ребро мостом.