1
правка
Изменения
м
Похоже, был копипаст из статьи про мосты. Слово "мосты" заменено на "точки сочленения".
Запустим [[Обход в глубину, цвета вершин|обход в глубину]] из произвольной вершины графа; обозначим её через <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>) дерева обхода в глубину.)
Теперь осталось научиться проверять этот факт для каждой вершины эффективно. Для этого воспользуемся "временами входа в вершину", вычисляемыми алгоритмом поиска в глубину.
Тогда из вершины <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] \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
'''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 p == -1 '''isand''' rootcount >= 2
v — cutpoint
