Изменения

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

[[Файл:Поиск точек сочелненияJoint_point_1.png|48px |thumb|80px‎ |Рисунок к <tex>\Leftarrow</tex> пункт 1]]

#Удалим <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>\Rightarrow root</tex> - — точка сочленения.<br><br>

#Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через <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 \, \nexists</tex> пути между остается дерево с корнем в его поддеревьямисыне, содержащее все остальные вершины графа, то есть оставшийся граф связен — противоречие с тем, так как не существует перекрестных ребер что <tex>\Rightarrow 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\ |\ \mathrm{begin(e)} = v\exists}</tex> такой сын . Всего таких ребер для всех вершин в графе <tex>vO(E)</tex>, что следовательно, время работы алгоритма оценивается как <tex>up[v] < tin[u]O(V+E)</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[]; //для каждой вершины содержится булево значение - является она точкой сочленения или нет* Асанов М., Баранский В. изначально все значения false int time; void dfs(int u, int prev) { used[u] = true; tin[u] = up[u] = time++; //задание времени входа tin и начального значения up для вершины u int count = 0; //счетчик количества детей вершины u в дереве обхода for (v Расин В. — Дискретная математика: uv из E) { if (v == prev) continue; if (used[v]) //v - предок вершины uГрафы, uv - обратное ребро up[u] = min(up[u]матроиды, tin[v]); else //v - ребенок вершины u { ++count; dfs(vалгоритмы — Лань, u); up[u] = min(up[u], up[v]); if (up[v] >= tin[u]) answer[u] = true; //не существует обратного ребра из вершины v или ее потомка в предка вершины u2010. — 368 с. вершина u — ISBN 978-5-8114- точка сочленения } } if (prev == 1068-1) //является ли u корнем дерева обхода2 answer* [u] = (count > 1); http://проверка количества детей у корня дерева } int main() { e-maxx... ru/algo/инициализация графа, выбор корня дерева обхода root time = 0; dfs(root, -1); return 0; }Для поиска cutpoints MAXimal :: algo :: Поиск точек сочленения в несвязном графе, необходимо модифицировать функцию main следующим образом: int main() { ... for (root из V) if (!used[root]) { time = 0; dfs(root, -1); } return 0; }

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