План алгоритмы на деревьях Центр дерева Наивный алгоритм

Обоснование корректности

Будем пользоваться свойством, что в любом дереве больше одного листа. Исключительный случай — дерево из одной вершины, но алгоритм сработает верно и в этом случае.

Теорема:

Искомое расстояние — расстояние между двумя листами.

Доказательство:

Пусть искомое расстояние — расстояние между вершинами a,ba,b, где bb не является листом. Так как bb не является листом, то её степень больше единицы, следовательно, из неё существует ребро в непосещённую вершину (дважды посетить вершину bb мы не можем).

После запуска алгоритма получим дерево BFSBFS.

Теорема:

В дереве BFSBFS не существует ребер между вершинами из разных поддеревьев некоторого их общего предка.

Доказательство:

Предположим, существует ребро u,vu,v между соседними поддеревьями: Рассмотрим первую вершину, в которую приведет наш алгоритм, пусть это вершина uu, тогда в ходе рассмотрения всех смежных вершин uu мы добавим в список вершину vv, тем самым исключив возможность попадания их в разные поддеревья.

Мы свели задачу к нахождению вершины ww, такой что сумма глубин поддеревьев максимальна.

Докажем, что одно из искомых поддеревьев содержит самый глубокий лист. Пусть нет, тогда, взяв расстояние от ww до глубочайшего листа, мы можем улучшить ответ.

Таким образом мы доказали, что нам нужно взять вершину uu с наибольшей глубиной после первого BFSBFS, очевидно, что ей в пару надо сопоставить вершину ww, такую что dist(u,w)dist(u,w) максимально. Вершину ww можно найти запуском BFSBFS из uu.