1
правка
Изменения
м
Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]]. Требуется найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в нем.
<br clear="all">
[[Файл:Joint_point_2.png|400px|thumb|Красным цветом обозначены точки сочленения<br>Синим — ребра по которым идет DFS]]=== Асимптотика ===Пусть <tex>tin[u]</tex> — Оценим время входа поиска в глубину в вершину работы алгоритма. Процедура <tex>u\mathrm{dfs}</tex>. Через <tex>upвызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[uОсновные определения теории графов|ребра]]</tex> обозначим минимум из времени захода в саму вершину <tex>tin[u]\{e\ |\ \mathrm{begin(e)} = v\}</tex>, времен захода . Всего таких ребер для всех вершин в каждую из вершин графе <tex>pO(E)</tex>, являющуюся концом некоторого обратного ребра следовательно, время работы алгоритма оценивается как <tex>O(u,pV+E)</tex>. Такое же, а также из всех значений <tex>upкак у [[v]</tex> для каждой вершины <tex>v</tex>Обход в глубину, являющейся непосредственным сыном <tex>u</tex> цвета вершин|обхода в дереве поискаглубину]].
Тогда из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v] < tin[u]</tex>. Таким образом, если для текущей вершины <tex>v \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>up[v] \ge tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения, в противном случае она точкой сочленения не является. <br clear="all"> == Реализация См. также == dfs(<tex>u</tex>, <tex>prev</tex>) Помечаем вершину <tex>u</tex>, как посещенную <tex>tin* [u] \leftarrow up[u] \leftarrow time</tex>++ <tex>count \leftarrow</tex> 0 for (<tex>v</tex> : <tex>uv</tex> из <tex>E</tex>) if (<tex>v</tex> родитель <tex>u</tex>) Переходим к следующей итерации цикла if (<tex>v</tex> посещено) //<tex>v</tex> — предок вершины <tex>u</tex>, <tex>uv</tex> — обратное ребро <tex>up[u] \leftarrow min(up[uИспользование обхода в глубину для поиска мостов], tin[v])</tex> else //<tex>v</tex> — ребенок вершины <tex>u</tex> <tex>count</tex>++ dfs(<tex>v, u</tex>) <tex>up* [u] \leftarrow min(up[u]Обход в глубину, up[v])</tex> if (<tex>up[v]</tex> >= <tex>tin[u]</tex>) <tex>answer[uцвета вершин] \leftarrow true</tex> if (<tex>u</tex> корень) <tex>answer[u] \leftarrow (count > 1)</tex> main() ... for (<tex>root</tex> из <tex>V</tex>) if (<tex>root</tex> не посещен) <tex>time \leftarrow 0</tex> dfs(<tex>root</tex>, -1);<br>Время работы алгоритма совпадает с * [[Обход в глубину, цвета вершин#Время работы|временем работыширину]] <tex> dfs </tex>.
Похоже, был копипаст из статьи про мосты. Слово "мосты" заменено на "точки сочленения".
{{Задача
|definition=Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]] <tex> G </tex>. Найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в <tex> G </tex> за время <tex> O(|V| + |E|).</tex>
}}
== Алгоритм ==
=== Описание алгоритма ===
Запустим [[Обход в глубину, цвета вершин|обход в глубину]] из произвольной вершины графа; обозначим её через <tex>root</tex>. Заметим следующий факт:
* Пусть мы находимся в обходе в глубину, просматривая сейчас все рёбра из вершины <tex>v</tex>. Тогда, если текущее ребро (<tex>v</tex>,<tex>to</tex>) таково, что из вершины <tex>to</tex> и из любого её потомка в дереве обхода в глубину нет обратного ребра в вершину <tex>v</tex> или какого-либо её предка, то эта вершина является точкой сочленения. В противном случае она ей не является. (В самом деле, мы этим условием проверяем, нет ли другого пути из <tex>v</tex> в <tex>to</tex>, кроме как спуск по ребру (<tex>v</tex>,<tex>to</tex>) дерева обхода в глубину.)
Теперь осталось научиться проверять этот факт для каждой вершины эффективно. Для этого воспользуемся "временами входа в вершину", вычисляемыми алгоритмом поиска в глубину.
[[Файл:Joint_point_2_rsz.png|280px|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>u \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>up[v] \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'']
'''function''' dfs(v: '''int''', p: '''int'''):
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]
up[v] = min(up[v], tin[u])
'''else'''
dfs(u, v)
count = count + 1
up[v] = min(up[v], up[u])
'''if''' p != -1 '''and''' up[u] >= tin[v]
v — cutpoint
'''if''' p == -1 '''and''' count >= 2
v — cutpoint
'''for''' i = 1 '''to''' n
'''if''' '''not''' visited[i]
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>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> — не точка сочленения.
}}
<br clear="all">
== Источники информации==* Асанов М., Баранский В., Расин В. - — Дискретная математика: Графы, матроиды, алгоритмы — ИжевскЛань, 2010. — 368 с. — ISBN 978-5-8114-1068-2* [http: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр//e-maxx.ru/algo/cutpoints MAXimal :: algo :: Поиск точек сочленения]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
