19
правок
Изменения
Нет описания правки
__TOC__
'''Диаметр дерева''' — максимальная длина (в рёбрах) кратчайшего пути между любыми двумя вершинами. Пусть дан граф <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> v \in V </tex> и найдём расстояния до всех других вершин.
<tex>d[i] = \min\limits_{u, i \in V} dist(u, i)</tex>
Возьмём вершину <tex> u \in V </tex> такую, что <tex>d[u] \ge d[t]</tex> для любого <tex>t</tex>.Снова найдём расстояние от <tex>u</tex> до всех остальных вершин. Самое большое расстояние {{---}} — диаметр дерева.
Расстояние до остальных вершин будем искать алгоритмом <tex>BFS</tex>.
=== Реализация ===
'''int ''' diameterTree(graph g) {
v = u = w = 0;
d = bfs(g, v);
'''for (''' i = 0; i < n; i++) '''if (''' d[i] > d[u])
u = i;
bfs(g, u);
'''for (''' i = 0; i < n; i++) '''if (''' d[i] > d[w])
w = i;
'''return ''' d[w]; } == Обоснование корректности ==Будем пользоваться свойством, что в любом дереве больше одного листа. Исключительный случай-дерево из одной вершины,но алгоритм сработает верно и в этом случае.
=== Обоснование корректности ===
Будем пользоваться свойством, что в любом дереве больше одного листа. Исключительный случай — дерево из одной вершины, но алгоритм сработает верно и в этом случае.
{{Теорема
|statement=
Искомое расстояние - есть — это расстояние между двумя листами.
|proof=
Пусть искомое расстояние - есть — расстояние между вершинами <tex>a, b</tex> , где <tex>b</tex> - не является листом. Т.к. Так как b не является листом, то значит её степень больше еденицыединицы, следовательно из неё существует ребро в непосещенную непосещённую вершину (дважды посетить вершину <tex>b</tex> мы не можем). Лемма доказана.
}}
После запуска алгоритма получим дерево <tex>BFS</tex>.
|proof=
Предположим существует ребро <tex>u, v</tex> между соседними поддеревьями:
Рассмотрим первую вершину , в которую приведет наш алгоритм, предположим , это вершина <tex>u</tex>, тогда в ходе рассмотрения всех смежных вершин <tex>u</tex> мы добавим в список вершину <tex>v</tex>, тем самым исключив возможность попадания их в разные поддеревья.
}}
Мы свели задачу к нахождению вершины <tex>w</tex>, такой, что сумма глубин поддеревьев максимальна.
Докажем, что одно из искомых поддеревьев содержит самый глубокий лист.
Пусть нет, тогда , взяв расстояние от <tex>w</tex> до глубочайшего листа , мы можем улучшить ответ. Таким образом мы доказали, что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого <tex>bfs</tex>, очевидно что ей в пару надо сопоставить вершину <tex>w</tex> , что <tex>dist(u, w)</tex> {{---}} максимально. Очевидно, что проблема решается запуском bfs из <tex>u</tex>.
Таким образом мы доказали, что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого <tex>bfs</tex>, очевидно что ей в пару надо сопоставить вершину <tex>w</tex>, такую что <tex>dist(u, w)</tex> максимально. Очевидно, что проблема решается запуском bfs из <tex>u</tex>.
=== Оценка производительности ===Все операции кроме <tex>BFS</tex> {{---}} — <tex>O(1)</tex>.<tex>BFS</tex> работает за линейное время, запускаем мы его 2 раза.Получаем <tex>O(V + E)</tex>.
