Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 10
Пара рисунков в статью улучшила бы восприятие текста. Например, визуализировать разные варианты деревьев.
Плохое доказательство.
Какое-то месиво.
BFS, LCA
От того, что вы пишете по-инострански, вы выглядите не круто, а наоборот.
Найдем НОП этих вершин...
Что такое "общий предок" вершин?
… диаметр "перегибается"...
Что это означает?
Зачем-то LCA вводить… Дальше как в викторине: «А я могу доказать теорему за пять строчек»(на достаточно широком экране 8)):
Есть первая вершина V, есть самый длинный путь в дереве AB. U — самая удаленная от V. X — вершина в AB, ближайшая к V. Пусть d(X,A) >= d(X, B) (перестановку А и B выбираем мы)
Далее, X лежит на пути UV, т.к. иначе d(U, A) > d(B, A).
Дальше, d(U, X) >= d(X, A), т.к. иначе d(V, A) > d(V, U). Значит, d(U,A) = d(U,X) + d(X, A) >= d(B,X) + d(X,A) = d(A,B).
Значит, вершина U лежит хотя бы на одном самом длинном пути.
Есть первая вершина V, есть самый длинный путь в дереве AB. U — самая удаленная от V. X — вершина в AB, ближайшая к V. Пусть d(X,A) >= d(X, B) (перестановку А и B выбираем мы)
Далее, X лежит на пути UV, т.к. иначе d(U, A) > d(B, A).
Дальше, d(U, X) >= d(X, A), т.к. иначе d(V, A) > d(V, U). Значит, d(U,A) = d(U,X) + d(X, A) >= d(B,X) + d(X,A) = d(A,B).
Значит, вершина U лежит хотя бы на одном самом длинном пути.
Помоему это очевидно в случае дерева. Первый проход из любой вершины находит один конец диаметра, второй проход находит сам диаметр. Или я чего-то не понимаю?
> Сначала поймем, что искомое расстояние — расстояние между двумя листами
контрпример: A->B->C->D
диаметр 3 (A,D) при этом A не является листом
да и на вашем примере — для двух вершин — одна из них не будет листом.
контрпример: A->B->C->D
диаметр 3 (A,D) при этом A не является листом
да и на вашем примере — для двух вершин — одна из них не будет листом.
Здесь выполняется не поиск в ширину, а полный обход дерева в произвольном порядке. (Технически удобнее — обход в глубину).
Потому что поиск в ширину предполагает определённый порядок обхода (по возрастанию расстояния от корня) и остановку на искомой вершине.
Нам же нужно взять любую самую удалённую вершину и убедиться, что ещё более удалённых нет.
Кстати, несложно показать, что если от стартовой вершины наиболее удалены несколько вершин, то можно брать любую из них.
Потому что поиск в ширину предполагает определённый порядок обхода (по возрастанию расстояния от корня) и остановку на искомой вершине.
Нам же нужно взять любую самую удалённую вершину и убедиться, что ещё более удалённых нет.
Кстати, несложно показать, что если от стартовой вершины наиболее удалены несколько вершин, то можно брать любую из них.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Доказываем корректность поиска диаметра дерева