148
правок
Изменения
Нет описания правки
Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]]. Требуется найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в нем.
Пусть <tex>T</tex> - дерево [[Обход в глубину, цвета вершин|обхода в глубину]], <tex>root</tex> - корень <tex>T</tex>. Вершина <tex>u \ne root</tex> - точка сочленения <tex>\Leftrightarrow \exists v \in T</tex> - сын <tex>u</tex> : из <tex>v</tex> или любого потомка вершины <tex>v</tex> нет обратного ребра в предка вершины <tex>u</tex>. <tex>root</tex> - точка сочленения <tex>\Leftrightarrow root</tex> имеет хотя бы двух сыновей в дереве поиска в глубину.
|proof=
[[Файл:Поиск точек сочелнения.png|thumb|80px|<tex>\Leftarrow</tex> пункт 150px]]
<tex>\Leftarrow</tex>
#Удалим <tex>u</tex> из <tex>G</tex>. Докажем, что <tex>\nexists</tex> пути из <tex>v</tex> в любого предка вершины <tex>u</tex>. Пусть это не так. Тогда <tex>\exists x \in T</tex> - предок <tex>u</tex> : <tex>\exists</tex> путь из <tex>v</tex> в <tex>x</tex> в <tex>G \backslash u</tex>. Пусть <tex>w</tex> - предпоследняя вершина на этом пути, <tex>w</tex> - потомок <tex>v</tex>. <tex>(w, x)</tex> - не ребро дерева <tex>T</tex>(в силу единственности пути в дереве) <tex>\Rightarrow (w, x)</tex> - обратное ребро, что противоречит условию.
#Пусть <tex>root</tex> - точка сочленения и у него есть только 1 сын. Тогда при удалении <tex>root</tex> остается дерево с корнем в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен - противоречие с тем, что <tex>root</tex> - точка сочленения.
<tex>\Rightarrow</tex>
#Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через <tex>G'</tex> граф, состоящий из вершин, не являющихся потомками <tex>u</tex>. Удалим вершину <tex>u</tex>. Очевидно, что граф <tex>G'</tex> и все поддеревья вершины <tex>u</tex> останутся связными, кроме того из каждого поддерева есть ребро в <tex>G' \Rightarrow G \backslash u</tex> - связный <tex>\Rightarrow u</tex> - не точка сочленения.
Таким образом, если для текущей вершины <tex>v \ne root \, \exists</tex> непосредственный сын <tex>v</tex>: <tex>up[v] \ge tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения; в противном случае она точкой сочленения не является.
=Время Работы = Реализация == bool used[]; int tin[]; int up[]; bool answer[]; Время работы алгоритма совпадает с временем работы <tex> dfs </tex>. Он равен <tex> O(V + E) </для каждой вершины содержится булево значение - является она точкой сочленения или нет. изначально все значения falsetex> int time;= Реализация =
else //v - ребенок вершины u
...
for (<tex>root </tex> из <tex>V</tex>) if (!used[<tex>root]</tex> не посещен) { <tex>time = \leftarrow 0;</tex> dfs(<tex>root</tex>, -1); } return 0; }
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
