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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

1. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 22: Елементарні алгоритми на графах. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
2. Tarjan, R. Endre (1974), A note on finding the bridges of a graph, Information Processing Letters, 2 (6): 160—161, doi:10.1016/0020-0190(74)90003-9, MR 0349483.

Посилання

•  Bridges and Articulation points Algorithm на YouTube