Изменения

Перейти к: навигация, поиск
Алгоритм
#Пусть <tex>root</tex> — точка сочленения и у него есть только один сын. Тогда при удалении <tex>root</tex> остается дерево с корнем в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен — противоречие с тем, что <tex>root</tex> — точка сочленения.
}}
[[Файл:Точки_сочленения.png‎| 200px|thumb|красным цветом обозначены точки сочленения]]
Пусть <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> в дереве поиска.
148
правок

Навигация