Изменения
Нет описания правки
'''Диаметр дерева''' - максимальная длина кратчайшего пути между любыми двумя вершинами.
Алгоритм в этой статье находил диаметр в дереве,при чём причём очень простым алгоритмом.
'''Алгоритм:'''
'''Обоснование корректности:'''
{{Будем пользоваться свойством,что в любом дереве >= 2 висячих вершин(степерь степень у них = 1)
|statement=Искомое расстояние - есть расстояние между двумя листами.
|proof=пусть нет, пусть искомое расстояние - есть расстояние между вершина a, b, где b - не является листом.Т.к. b не является листом, то значит её степень > 1 => из неё существует ребро в непосещенную вершину (дважды посетить вершину b мы не можем). Лемма доказана.
}}
