Комментарии 10
Пара рисунков в статью улучшила бы восприятие текста. Например, визуализировать разные варианты деревьев.
+4
НЛО прилетело и опубликовало эту надпись здесь
Плохое доказательство.
Какое-то месиво.
BFS, LCA
От того, что вы пишете по-инострански, вы выглядите не круто, а наоборот.
Найдем НОП этих вершин...
Что такое "общий предок" вершин?
… диаметр "перегибается"...
Что это означает?
+3
Зачем-то 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 лежит хотя бы на одном самом длинном пути.
0
Помоему это очевидно в случае дерева. Первый проход из любой вершины находит один конец диаметра, второй проход находит сам диаметр. Или я чего-то не понимаю?
0
> Сначала поймем, что искомое расстояние — расстояние между двумя листами
контрпример: A->B->C->D
диаметр 3 (A,D) при этом A не является листом
да и на вашем примере — для двух вершин — одна из них не будет листом.
контрпример: A->B->C->D
диаметр 3 (A,D) при этом A не является листом
да и на вашем примере — для двух вершин — одна из них не будет листом.
0
Здесь выполняется не поиск в ширину, а полный обход дерева в произвольном порядке. (Технически удобнее — обход в глубину).
Потому что поиск в ширину предполагает определённый порядок обхода (по возрастанию расстояния от корня) и остановку на искомой вершине.
Нам же нужно взять любую самую удалённую вершину и убедиться, что ещё более удалённых нет.
Кстати, несложно показать, что если от стартовой вершины наиболее удалены несколько вершин, то можно брать любую из них.
Потому что поиск в ширину предполагает определённый порядок обхода (по возрастанию расстояния от корня) и остановку на искомой вершине.
Нам же нужно взять любую самую удалённую вершину и убедиться, что ещё более удалённых нет.
Кстати, несложно показать, что если от стартовой вершины наиболее удалены несколько вершин, то можно брать любую из них.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Доказываем корректность поиска диаметра дерева