Изменения
Нет описания правки
Алгоритм в этой статье находил диаметр в дереве,при чём очень простым алгоритмом.
'''Алгоритм:'''
Возьмём любую вершину V и найдём расстояния до всех других вершин.
d = max{<tex> v </tex>,<tex> u </tex> <tex> \subset graph, </tex> <tex> v \ne u </tex>} dist(<tex> v, u </tex>)
Возьмём вершину <tex> u </tex> такую,что d[u] >= d[t] для $\forall$ любого t.Снова найдём расстояние до всех остальных вершин.Самое большое расстояние-диаметр дерева.
Расстояние до остальных вершин удобно искать алгоритмом BFS.
'''Реализация:'''
'''Обоснование корректности:'''
Будем пользоваться свойством,что в любом дереве >= 2 висячих вершин(степерь у них = 1)
Докажем вспомогательную лемму:
Таким образом мы доказали, что нам нужно взять наиглубочайшую вершину t после первого bfs, очевидно что ей в пару надо сапоставить вершину p , что dist(t, p) - max . Очевидно, что проблема решается запуском bfs из t.
'''Оценка производительности:'''
Все операции кроме bfs - О(1)
BFS работает линейное время,запускаем мы его 2 раза.Получаем O(V+E)
