Изменения

[[Категория: Обход в глубину]]{{Задача|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] &lt; 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)

Пусть <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> имеет хотя бы двух сыновей в дереве поиска в глубину.

#Удалим <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> хотя бы два сына. Тогда при удалении <tex>root</tex> не существует пути между его поддеревьями, так как не существует перекрестных ребер <tex>\Rightarrow root</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> - — точка сочленения.

Пусть <texbr clear="all">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\mathrm{dfs}</tex> или её потомка есть обратное ребро в её предка вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\Leftrightarrow {e\ |\ \existsmathrm{begin(e)} = v\}</tex> такой сын . Всего таких ребер для всех вершин в графе <tex>vO(E)</tex>, что следовательно, время работы алгоритма оценивается как <tex>up[v] < tin[u]O(V+E)</tex>. Такое же, как у [[Обход в глубину, цвета вершин|обхода в глубину]].

Таким образом, если == См. также ==* [[Использование обхода в глубину для текущей вершины <tex>v \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>upпоиска мостов]]* [[vОбход в глубину, цвета вершин] \ge tin]* [u[Обход в ширину]]</tex>, то вершина <tex>u</tex> является точкой сочленения, в противном случае она точкой сочленения не является.

= Реализация = Источники информации== 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> посещено) //v - предок вершины uГрафы, uv - обратное ребро <tex>up[u] \leftarrow min(up[u], tin[v])</tex> else //v - ребенок вершины u <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() .2010.— 368 с.— ISBN 978-5-8114-1068-2 for (<tex>root</tex> из <tex>V</tex>) if (<tex>root</tex> не посещен) <tex>time \leftarrow 0<* [http:/tex> dfs(<tex>root</tex>, e-1);<br>Время работы алгоритма совпадает с временем работы <tex> dfs <maxx.ru/tex>, а именно <tex> O(V + E) <algo/tex>.cutpoints MAXimal :: algo :: Поиск точек сочленения]

= Источники =[[Категория: Алгоритмы и структуры данных]]Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск[[Категория: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.Обход в глубину]]