Однажды на зачете мне попалась следующая задача. Придумайте алгоритм, находящий две вершины дерева с максимальным расстоянием друг от друга, и докажите его корректность. В тот момент я в принципе не знала, что у деревьев есть диаметр, радиус и много прочих вещей. Уже после зачета друг просветил меня, рассказав, что это за алгоритм, но без доказательства. Именно вопросом о доказательстве долгое время была забита моя голова. После прочтения нескольких статей, стало понятно, что материал не уляжется, пока самостоятельно себе не объясню все практически на пальцах (может, и читателю придется по вкусу). Перейдем от демагогии к сути.
Диаметр дерева — это максимальное расстояние между двумя вершинами в дереве. Алгоритм поиска состоит в двух запусках BFS. Первый идет от произвольной вершины дерева, во время обхода насчитываются расстояния от текущей вершины до всех других. Затем из них выбирается самая удаленная. Из нее делается второй запуск BFS. Насчитываются новые расстояния. Максимальное среди них и будет диаметром.
Почему этот простой с виду алгоритм работает корректно?
Чтобы избежать подводных камней при доказательстве, сразу обговорим случай с деревом из одной вершины и из двух вершин. Если вершина одна, то ребер у нас нет, первый BFS сообщит, что стартовая вершина имеет максимальную глубину, второй — тоже. По сути это и есть так, алгоритм сработает верно. Если имеется две вершины, то первый обход придет во вторую вершину, а второй — в стартовую, что корректно для данного случая.
Сначала поймем, что искомое расстояние — расстояние между двумя листами. На самом деле, пусть вершина на конце найденного максимального путь не является листом. Одновременно мы не можем увеличить искомое расстояние по предположению. Тем не менее, это означает, что BFS не посетил вершины, «расположенные за» текущей, что противоречит корректности BFS. Получается, что обе найденные вершины будут листьями. Прекрасно.
Подвесим наше дерево за вершину v, из которой запускаем первый обход.
Рассмотрим отдельный случай, когда вершина v сама является листом. В случае, если она и есть первый конец диаметра, то очевидно, что первый BFS найдет второй конец, а второй вернется в стартовую вершину. Иначе диаметр не будет проходить через v и также будет «перегибаться», так как не может содержать более двух листьев.
Пусть мы нашли диаметр и две вершины, ему соответствующие. Найдем LCA этих вершин a и b, назовем эту вершину c. Очевидно, что D = d[a,c] + d[c,b]. Фактически диаметр это сумма двух наиболее глубоких поддеревьев некоторой вершины, если она принадлежит длиннейшему пути. Диаметр дерева — это максимальный диаметр среди всех поддеревьев. Первый обход в ширину даст нам максимальную по глубине вершину (так как мы подвесили за стартовую вершину). Обозначим вершину на конце найденного пути w. Докажем, что w будет принадлежать искомому длиннейшему пути. Пусть диаметр «перегибается» в вершине c(он будет «перегибаться», так как соединяет два листа, а дерево подвешено за вершину v, не являющуюся листом). Пускай вершина w принадлежит одному из поддеревьев вершины c. Тогда просто заменим некоторую часть пути (c, x), где x — один из концов, на (c, w). d[c,x] < d[c,w]. Мы улучшили ответ. Значит, первоначальный путь не был диаметром. Если w является предком c, то w не является листом, поэтому этот случай отпадает. Если же w находится где-то в другом поддереве, то пусть e = LCA(c, w). d[w,e] — максимальная глубина поддерева e. Тогда так как e — предок c, то d[x, e] > d[x,c]. d[w,e] > d[y,e] > d[y,c]. Поэтому D0 = d[x,c] + d[y,c] < d[x, e] + d[w, e] = D. Значит, первоначально диаметр был найден неверно и вершина w принадлежит диаметру.
Примечание:
В данной части доказательства мы использовали свойство, что лист w имеет наибольшую глубину в любом поддереве данного дерева, которому принадлежит w. Докажем по индукции. База — один лист w. Очевидно, что утверждение верно. Пусть для некоторого поддерева это тоже верно, тогда поднимемся на уровень выше. Допустим, существует вершина, у которой глубина в текущем поддереве больше, чем у w. Назовем текущую вершину a, вершину с предполагаемой большей глубиной x, корень дерева v.
d[v,x] = d[v,a] + d[a,x];
d[v,w] = d[v,a] + d[a,w];
d[v,x] < d[v,w] в силу корректности работы BFS;
d[a,x] > d[a,w] по предположению;
В итоге получаем противоречие. Поэтому вершина w обладает наибольшей глубиной в любом поддереве.
Получаем, что вершина w принадлежит диаметру, а также является одним из его концов. Тогда очевидно, что остается лишь найти наиболее удаленную от w вершину, что и делает второй BFS.
При написании статьи использовались материалы:
neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BD%D0%B0_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F%D1%85
Автор: Romanchenko28
