Поиск мостов и точек сочленения: различия между версиями
KiKoS (обсуждение | вклад) (Новая страница: «Сформулируем задачу о поиске мостов и точек сочленения. Мостом в связном неориентирова...») |
KiKoS (обсуждение | вклад) м |
||
Строка 7: | Строка 7: | ||
Ребро $u \rightarrow v$ будет являться мостом, если из его поддерева нет ребер, которые ведут выше, чем $v$. Для того, чтобы узнать о существовании таких, для каждой вершины храним величину $fup_v$ -- минимальная высота вершины, в которую можно добраться из поддерева вершины $v$. | Ребро $u \rightarrow v$ будет являться мостом, если из его поддерева нет ребер, которые ведут выше, чем $v$. Для того, чтобы узнать о существовании таких, для каждой вершины храним величину $fup_v$ -- минимальная высота вершины, в которую можно добраться из поддерева вершины $v$. | ||
− | $$fup_v = \min(h_v, \displaystyle \min_{to \in subtree(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$. Кроме этого, это условие не будет работать для корневой вершины остовного дерева --- там надо проверить, что количество переходов в детей было больше одного. | ||
+ | |||
+ | {Автор:Константин Амеличев:kik0s} |
Версия 18:18, 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$. Кроме этого, это условие не будет работать для корневой вершины остовного дерева --- там надо проверить, что количество переходов в детей было больше одного.
{Автор:Константин Амеличев:kik0s}