Поиск мостов и точек сочленения: различия между версиями
KiKoS (обсуждение | вклад) м |
KiKoS (обсуждение | вклад) м |
||
Строка 13: | Строка 13: | ||
Для проверки на точку сочленения насчитаем такую же величину. Вершина $v$ является точкой сочленения, если $fup_v = h_v$. Кроме этого, это условие не будет работать для корневой вершины остовного дерева --- там надо проверить, что количество переходов в детей было больше одного. | Для проверки на точку сочленения насчитаем такую же величину. Вершина $v$ является точкой сочленения, если $fup_v = h_v$. Кроме этого, это условие не будет работать для корневой вершины остовного дерева --- там надо проверить, что количество переходов в детей было больше одного. | ||
− | {Автор|Константин Амеличев|kik0s} | + | {{Автор|Константин Амеличев|kik0s}} |
Текущая версия на 18:19, 17 декабря 2020
Сформулируем задачу о поиске мостов и точек сочленения.
Мостом в связном неориентированном графе называется такое ребро $(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