Изменения
Нет описания правки
В дереве BFS не существует ребер между вершинами из разных поддеревьев некоторого их общего предка.
|proof=
Предположим существует, пусть ребро соединяет вершины <tex>u,v</tex> из разных поддеревьев. между соседними поддеревьями:Рассмотрим первую вершину в которую приведет наш алгоритм. , предположим это вершина <tex>u</tex>, тогда в ходе рассмотрения всех смежных вершин <tex>u</tex> мы занесем добавим в список вершину <tex>v</tex> , тем самым исключим исключив возможность попадания их в разные поддеревья.
}}
