19
правок
Изменения
Нет описания правки
'''Диаметр дерева''' — максимальная длина (в рёбрах) кратчайшего пути между любыми двумя вершинами.
Пусть дан граф <tex>G = \langle V, E \rangle </tex> . Тогда диаметром <tex>d</tex> называется <tex>\max\limits_{u, v \in V} dist(v, u)</tex>, где <tex>dist</tex> — кратчайшее расстояние между вершинами.
=== Алгоритм ===
Возьмём вершину <tex> u \in V </tex> такую, что <tex>d[u] \ge d[t]</tex> для любого <tex>t</tex>. Снова найдём расстояние от <tex>u</tex> до всех остальных вершин. Самое большое расстояние — диаметр дерева.
Расстояние до остальных вершин будем искать [[Обход_в_ширину|алгоритмом <tex>BFS</tex>]].
=== Реализация ===
Пусть нет, тогда, взяв расстояние от <tex>w</tex> до глубочайшего листа, мы можем улучшить ответ.
Таким образом мы доказали, что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого <tex>bfsBFS</tex>, очевидно, что ей в пару надо сопоставить вершину <tex>w</tex>, такую что <tex>dist(u, w)</tex> максимально. Вершину <tex>w</tex> можно найти запуском <tex>bfsBFS</tex> из <tex>u</tex>.
=== Оценка производительности ===
<tex>BFS</tex> работает за линейное время, запускаем мы его 2 раза. Получаем <tex>O(V + E)</tex>.
== Центр дерева ==
== См. также ==
*[[Дерево,_эквивалентные_определения|Дерево, эквивалентные определения]]
*[[Дополнительный,_самодополнительный_граф|Дополнительный, самодополнительный граф]]
== Источники информации ==
