Изменения

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

Пусть <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>vroot</tex>, являющейся непосредственным сыном <tex>u</tex> в дереве поиска.Заметим следующий факт:

* Пусть мы находимся в обходе в глубину, просматривая сейчас все рёбра из вершины <tex>v</tex>. Тогда, если текущее ребро (<tex>v</tex>,<tex>to</tex>) таково, что из вершины <tex>uto</tex> или и из любого её потомка есть обратное ребро в дереве обхода в глубину нет обратного ребра в вершину <tex>v</tex> или какого-либо её предка , то эта вершина является точкой сочленения. В противном случае она ей не является. (В самом деле, мы этим условием проверяем, нет ли другого пути из <tex>\Leftrightarrow \existsv</tex> такой сын в <tex>vto</tex>, что кроме как спуск по ребру (<tex>up[v] < tin[u]/tex>,<tex>to</tex>) дерева обхода в глубину.)

Таким образом, если Теперь осталось научиться проверять этот факт для текущей каждой вершины <tex>v \ne root \, \exists</tex> непосредственный сын <tex>v</tex>: <tex>up[v] \ge tin[u]</tex>эффективно. Для этого воспользуемся "временами входа в вершину", то вершина <tex>u</tex> является точкой сочленения; вычисляемыми алгоритмом поиска в противном случае она точкой сочленения не являетсяглубину.

[[Файл:Joint_point_2_rsz.png‎|280px|thumb|left| <font color=red>Красным</font> цветом обозначены точки сочленения<br><font color= Реализация ==blue>Синим</font> — ребра по которым идет DFS]] bool usedПусть <tex>tin[u]; int </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> в дереве поиска.  int Тогда из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v]&lt;tin[u]</tex>.  bool answerТаким образом, если для текущей вершины <tex>u \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>up[v]; \geqslant tin[u]</tex>, то вершина <tex>u</для каждой вершины содержится булево значение - tex> является точкой сочленения, в противном случае она точкой сочленения или нетне является. изначально все значения false int time;<br clear="all"> === Псевдокод ===

void '''function''' findCutPoints(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет поиск точек сочленения во всем графе </font> visited = array[n, ''false''] '''function''' dfs(v: '''int u''', p: '''int prev'''): { time = time + 1 used up[uv] = true; tin[uv] = uptime visited[uv] = time++; //задание времени входа tin и начального значения up для вершины u''true'' int count = 0; //счетчик количества детей вершины u в дереве обхода '''for ''' u: (v : uv из E, u)'''in''' G { '''if (v ''' u == prev)p '''continue;''' '''if (used''' visited[vu]) //v - предок вершины u, uv - обратное ребро up[uv] = min(up[uv], tin[vu]); '''else //v - ребенок вершины u { ++count;''' dfs(u, v, u); count = count + 1 up[uv] = min(up[uv], up[vu]); '''if (''' p != -1 '''and''' up[u] >= tin[v] v — cutpoint '''if''' p == -1 '''and''' count >= tin2 v — cutpoint '''for''' i = 1 '''to''' n '''if''' '''not''' visited[ui] dfs(i, -1) answer=== Доказательство корректности ==={{Теорема|statement=Пусть <tex>T</tex> — дерево [[Обход в глубину, цвета вершин|обхода в глубину]], <tex>root</tex> — корень <tex>T</tex>. * Вершина <tex>u] = true; \ne root</tex> — точка сочленения <tex>\Leftrightarrow \exists v \in T</tex> — сын <tex>u</не существует обратного ребра tex> : из вершины <tex>v </tex> или ее любого потомка вершины <tex>v</tex> нет обратного ребра в предка вершины <tex>u</tex>. вершина u - * <tex>root</tex> — точка сочленения<tex>\Leftrightarrow root</tex> имеет хотя бы двух сыновей в дереве поиска в глубину. }|proof=[[Файл:Joint_point_1.png|48px |thumb|‎ | Рисунок к <tex>\Leftarrow</tex>]]<tex>\Leftarrow</tex> } if #Удалим <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>(p == -1w, x) </tex> — не ребро дерева <tex>T</является ли u корнем дерева обхода answer[u] = tex>(count в силу единственности пути в дереве) <tex> 1\Rightarrow (w, x); </tex> — обратное ребро, что противоречит условию.#Пусть у <tex>root</tex> хотя бы два сына. Тогда при удалении <tex>root</проверка количества детей у корня дереваtex> не существует пути между его поддеревьями, так как не существует перекрестных ребер <tex>\Rightarrow root</tex> — точка сочленения. } <tex>\Rightarrow</tex> int main() { #Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через <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">  time = 0;== Асимптотика === Оценим время работы алгоритма. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ \mathrm{begin(root, -1e); return 0; }Для поиска точек сочленения = v\}</tex>. Всего таких ребер для всех вершин в несвязном графе, необходимо модифицировать функцию main следующим образом: int main<tex>O(E) { ... for </tex>, следовательно, время работы алгоритма оценивается как <tex>O(root из V+E) if (!used</tex>. Такое же, как у [[rootОбход в глубину, цвета вершин|обхода в глубину]]). { time = 0;= См. также ==* [[Использование обхода в глубину для поиска мостов]] dfs(root* [[Обход в глубину, -1);цвета вершин]] } return 0;* [[Обход в ширину]] }== Источники информации==* Асанов М., Баранский В., Расин В. - — Дискретная математика: Графы, матроиды, алгоритмы — ИжевскЛань, 2010. — 368 с. — ISBN 978-5-8114-1068-2* [http: ННЦ "Регулярная //e-maxx.ru/algo/cutpoints MAXimal :: algo :: Поиск точек сочленения] [[Категория: Алгоритмы и хаотическая динамика", 2001, 288 стр.структуры данных]][[Категория: Обход в глубину]]