19
правок
Изменения
Нет описания правки
{{Теорема
|statement=
Искомое расстояние — это расстояние между двумя листами.
|proof=
Пусть искомое расстояние — расстояние между вершинами <tex>a, b</tex>, где <tex>b</tex> не является листом. Так как <tex>b </tex> не является листом, то значит её степень больше единицы, следовательно , из неё существует ребро в непосещённую вершину (дважды посетить вершину <tex>b</tex> мы не можем). Лемма доказана.
}}
{{Теорема
|statement=
В дереве <tex>BFS </tex> не существует ребер между вершинами из разных поддеревьев некоторого их общего предка.
|proof=
Предположим , существует ребро <tex>u, v</tex> между соседними поддеревьями:Рассмотрим первую вершину, в которую приведет наш алгоритм, предположим, пусть это вершина <tex>u</tex>, тогда в ходе рассмотрения всех смежных вершин <tex>u</tex> мы добавим в список вершину <tex>v</tex>, тем самым исключив возможность попадания их в разные поддеревья.
}}
Пусть нет, тогда, взяв расстояние от <tex>w</tex> до глубочайшего листа, мы можем улучшить ответ.
Таким образом мы доказали, что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого <tex>bfs</tex>, очевидно , что ей в пару надо сопоставить вершину <tex>w</tex>, такую что <tex>dist(u, w)</tex> максимально. Очевидно, что проблема решается Вершину <tex>w</tex> можно найти запуском <tex>bfs </tex> из <tex>u</tex>.
=== Оценка производительности ===
Все операции кроме <tex>BFS</tex> — <tex>O(1)</tex>.
<tex>BFS</tex> работает за линейное время, запускаем мы его 2 раза. Получаем <tex>O(V + E)</tex>.
