Изменения

Перейти к: навигация, поиск
Алгоритм
{{Теорема
|statement=
Пусть <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=
[[Файл:Joint_point_1.png|48px |thumb|‎ | Рисунок к <tex>\Leftarrow</tex>]]
Анонимный участник

Навигация