1
правка
Изменения
м
{{Теорема|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>T</tex>(в силу единственности пути в дереве) <tex>\Rightarrow (w, x)</tex> — обратное ребро, что противоречит условию.#Пусть у <tex>root</tex> хотя бы два сына. Тогда при удалении <tex>root</tex> не существует пути между его поддеревьями, так как не существует перекрестных ребер <tex>\Rightarrow root</tex> — точка сочленения.
Похоже, был копипаст из статьи про мосты. Слово "мосты" заменено на "точки сочленения".
{{Задача|definition=Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]] <tex> G </tex>. Найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в <tex> G </tex> за время <tex> O(|V| + |E|).</tex>}}
== Алгоритм ==
* Пусть мы находимся в обходе в глубину, просматривая сейчас все рёбра из вершины <tex>\Rightarrowv</tex>#Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через Тогда, если текущее ребро (<tex>G'v</tex> граф, состоящий из вершин, не являющихся потомками <tex>u</tex>. Удалим вершину <tex>uto</tex>. Очевидно) таково, что граф из вершины <tex>G'to</tex> и все поддеревья вершины из любого её потомка в дереве обхода в глубину нет обратного ребра в вершину <tex>uv</tex> останутся связнымиили какого-либо её предка, кроме того то эта вершина является точкой сочленения. В противном случае она ей не является. (В самом деле, мы этим условием проверяем, нет ли другого пути из каждого поддерева есть ребро в <tex>G' \Rightarrow G \backslash uv</tex> — связный в <tex>\Rightarrow uto</tex> — не точка сочленения.#Пусть , кроме как спуск по ребру (<tex>rootv</tex> — точка сочленения и у него есть только один сын. Тогда при удалении ,<tex>rootto</tex> остается дерево с корнем ) дерева обхода в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен — противоречие с тем, что <tex>root</tex> — точка сочлененияглубину.}})
Теперь осталось научиться проверять этот факт для каждой вершины эффективно. Для этого воспользуемся "временами входа в вершину", вычисляемыми алгоритмом поиска в глубину.
[[Файл:Joint_point_2Joint_point_2_rsz.png|300px280px|thumb|left| <font color=red>Красным </font> цветом обозначены точки сочленения<br><font color=blue>Синим </font> — ребра по которым идет DFS]]
Пусть <tex>tin[u]</tex> — время входа поиска в глубину в вершину <tex>u</tex>. Через <tex>up[u]</tex> обозначим минимум из времени захода в саму вершину <tex>tin[u]</tex>, времен захода в каждую из вершин <tex>p</tex>, являющуюся концом некоторого обратного ребра <tex>(u,p)</tex>, а также из всех значений <tex>up[v]</tex> для каждой вершины <tex>v</tex>, являющейся непосредственным сыном <tex>u</tex> в дереве поиска.
Тогда из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v] < \geqslant tin[u]</tex>.
Таким образом, если для текущей вершины <tex>v u \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>up[v] \ge geqslant tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения, в противном случае она точкой сочленения не является.
<br clear="all">
== Реализация = Псевдокод ===
'''function''' findCutPoints(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет поиск точек сочленения во всем графе </font>
visited = array[n, ''false'']
time = time + 1
up[v] = tin[v] = time
visited[v] = ''true'' count = 0
'''for''' u: (v, u) '''in''' G
'''if''' u == p
'''continue''' '''if''' visited[u] == ''true''
up[v] = min(up[v], tin[u])
'''else'''
dfs(u, v)
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>
v — cutpoint
'''if''' v — rootp == -1 '''and''' count >= 2
v — cutpoint
'''for''' i = 1 '''to''' n
'''if''' '''not''' visited[i] == ''false''
dfs(i, -1)
=== Доказательство корректности ===
{{Теорема
|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>T</tex>(в силу единственности пути в дереве) <tex>\Rightarrow (w, x)</tex> — обратное ребро, что противоречит условию.
#Пусть у <tex>root</tex> хотя бы два сына. Тогда при удалении <tex>root</tex> не существует пути между его поддеревьями, так как не существует перекрестных ребер <tex>\Rightarrow 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>root</tex> — точка сочленения и у него есть только один сын. Тогда при удалении <tex>root</tex> остается дерево с корнем в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен — противоречие с тем, что <tex>root</tex> — точка сочленения.
}}
<br clear="all">
=== Асимптотика ===
Оценим время работы алгоритма. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ \mathrm{begin(e)} = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>. Такое же, как у [[Обход в глубину, цвета вершин|обхода в глубину]].
== См. также ==
