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

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

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

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

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

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

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

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

Примітки ред.

↑ Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019), Розділ 22: Елементарні алгоритми на графах, Вступ до алгоритмів (вид. 3), К.І.С., с. 633, ISBN 978-617-684-239-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

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.

[mit-1] Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019), Розділ 22: Елементарні алгоритми на графах, Вступ до алгоритмів (вид. 3), К.І.С., с. 633, ISBN 978-617-684-239-2

[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.

[1]

[2]