Изменения

|definition=Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]] <tex> G </tex>. Найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в <tex> G </tex> за время <tex> O(|V| + |E|).</tex>

{{Теорема|statement=== Описание алгоритма ===Пусть <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=[[ФайлЗаметим следующий факт:Joint_point_1.png|48px |thumb|‎ | Рисунок к <tex>\Leftarrow</tex>]]<tex>\Leftarrow</tex>

#Удалим <tex>u</tex> из <tex>G</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>Tto</tex>(в силу единственности пути в дереве) <tex>\Rightarrow (w, x)</tex> — обратное ребротаково, что противоречит условию.#Пусть у из вершины <tex>rootto</tex> хотя бы два сына. Тогда при удалении и из любого её потомка в дереве обхода в глубину нет обратного ребра в вершину <tex>rootv</tex> не существует пути между его поддеревьямиили какого-либо её предка, так как не существует перекрестных ребер <tex>\Rightarrow root</tex> — точка то эта вершина является точкой сочленения. <tex>\Rightarrow</tex>#Докажем что из отрицания второго утверждения следует отрицание первогоВ противном случае она ей не является. Обозначим через <tex>G'</tex> граф(В самом деле, мы этим условием проверяем, состоящий нет ли другого пути из вершин, не являющихся потомками <tex>uv</tex>. Удалим вершину в <tex>uto</tex>. Очевидно, что граф кроме как спуск по ребру (<tex>G'</tex> и все поддеревья вершины <tex>uv</tex> останутся связными, кроме того из каждого поддерева есть ребро в <tex>G' \Rightarrow G \backslash uto</tex> — связный <tex>\Rightarrow u</tex> — не точка сочленения.#Пусть <tex>root</tex> — точка сочленения и у него есть только один сын. Тогда при удалении <tex>root</tex> остается дерево с корнем ) дерева обхода в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен — противоречие с тем, что <tex>root</tex> — точка сочлененияглубину.}})

Таким образом, если для текущей вершины <tex>v u \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>up[v] \geqslant tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения, в противном случае она точкой сочленения не является.

=== Псевдокод ===

'''function''' findCutPoints(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет поиск точек сочленения во всем графе </font>

visited[v] = ''true'' count = 0

count = count + 1 up[v] = min(up[v], tinup[u]) '''if''' p != -1 '''and''' up[tou] >= tin[v] '''&&''' p != -1 <font color=darkgreen>// если граф состоит из 2 вершин и одного ребра, то p != -1 спасёт, иначе выведет 1 точку сочленения </font>

'''if''' v p == -1 '''isand''' rootcount >= 2