Изменения

Перейти к: навигация, поиск

Алгоритмы на деревьях

18 байт добавлено, 19:24, 11 декабря 2013
Нет описания правки
Искомое расстояние - есть расстояние между двумя листами.
<tex>|proof=\begin{Proof}
'''Доказательство:''' пусть нет, пусть искомое расстояние - есть расстояние между вершина a, b, где b - не является листом.Т.к. b не является листом, то значит её степень > 1 => из неё существует ребро в непосещенную вершину (дважды посетить вершину b мы не можем). Лемма доказана.
\begin{Proof}}</tex>
Запустив BFS от произвольной вершины. Мы получим дерево BFS.
Анонимный участник

Навигация