148
правок
Изменения
→Алгоритм
Пусть <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> имеет хотя бы двух сыновей в дереве поиска в глубину.
|proof=
<tex>\Leftarrow</tex>