Поиск мостов и точек сочленения

Материал из Algocode wiki
Перейти к: навигация, поиск

Сформулируем задачу о поиске мостов и точек сочленения.

Мостом в связном неориентированном графе называется такое ребро $(v, u)$, что при удалении этого ребра из графа нарушается его связность. Точкой сочленения называется такая вершина $v$, что при удалении из графа вершины $v$ (и всех смежных ребер) он теряет свою связность.

Чтобы найти мосты, сделаем обход графа с помощью dfs. Этот обход построит нам какое-то остовное дерево графа (не путать с минимальным остовным деревом). Все ребра, по которым мы не сделали переход, будут вести от вершины остовного дерева к какому-то из предков. Заметим, что эти ребра не могут быть мостами --- при их удалении остовное дерево остается невредимым. Значит, мосты --- это какие-то из ребер остовного дерева.

Ребро $u \rightarrow v$ будет являться мостом, если из его поддерева нет ребер, которые ведут выше, чем $v$. Для того, чтобы узнать о существовании таких, для каждой вершины храним величину $fup_v$ -- минимальная высота вершины, в которую можно добраться из поддерева вершины $v$.

$$fup_v = \min(h_v, \displaystyle \min_{to \in subtree(v)} fup_{to}, \displaystyle \min_{to \in G(v), h_{to} < h_v, to \neq parent(v)} h_{to}))$$

Соответственно, ребро $u \rightarrow v$ является мостом, если $h_{v} = fup_{v}$.

Для проверки на точку сочленения насчитаем такую же величину. Вершина $v$ является точкой сочленения, если $fup_v = h_v$. Кроме этого, это условие не будет работать для корневой вершины остовного дерева --- там надо проверить, что количество переходов в детей было больше одного.



Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s