Изменения

== Диаметр дерева =={{Определение|id = tree|definition ='''Диаметр дерева''' - (англ. ''diameter of a tree'') — максимальная длина (в рёбрах) кратчайшего пути в дереве между любыми двумя вершинами.Алгоритм в этой статье находит диаметр в дереве,причём очень простой реализацией и низким временем работы.<tex>diameter = max</tex>{<tex> v </tex>,<tex> u </tex> <tex> \subset graph, </tex> <tex> v \ne u </tex>} <tex>min\_dist</tex>(<tex> v, u </tex>)}

Пусть дан граф <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>d = min\{ v </tex>,<tex> u </tex> <tex> \subset graph, </tex> == Алгоритм ===* Возьмём любую вершину <tex> v \ne u in V </tex>} и найдём расстояния до всех других вершин. <tex>d[i] = dist\(v, u\i) </tex>

* Возьмём вершину <tex> u \in V </tex> такую,что <tex>d[u] >= \geqslant d[t] </tex> для любого <tex>t</tex>.Снова найдём расстояние от <tex>u</tex> до всех остальных вершин.Самое большое расстояние - — диаметр дерева.Расстояние до остальных вершин удобно будем искать [[Обход_в_ширину|алгоритмом <tex>BFS</tex>]].

=== Реализация === <span style="color:green">//граф g представлен списком смежности</span> '''int''' diameterTree('''list<list<int>>''' g): v = u = w = 0 d = bfs(g, v) '''for''' i = 0, i < n, i++ '''if''' d[i] > d[u] u = i d = bfs(g, u) '''for''' i = 0, i < n, i++ '''if''' d[i] > d[w] w = i '''return''' d[w]

int diameterTree(graph g) После запуска алгоритма получим дерево <tex>BFS</tex>.  {{Теорема v = u |statement= w = 0; bfs(g,v); В дереве <tex>BFS<// заполняет массив d[n] кратчайшими расстояниями до всех вершинtex> не существует ребер между вершинами из разных поддеревьев некоторого их общего предка. for(i |proof= 0; i Предположим, существует ребро < n; i++) if (d[i] tex> d[u]), v</tex> между соседними поддеревьями: Рассмотрим первую вершину, в которую приведет наш алгоритм, пусть это вершина <tex>u = i; bfs(g</tex>,тогда в ходе рассмотрения всех смежных вершин <tex>u); for(i = 0; i < n; i++) if (d[i] /tex> мы добавим в список вершину <tex>v</tex> d[w]) w = i; return d[w];, тем самым исключив возможность попадания их в разные поддеревья. }}

== Обоснование корректности ==Будем пользоваться свойствомТаким образом мы доказали,что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого <tex>BFS</tex>, очевидно, что ей в любом дереве пару надо сопоставить вершину <tex>= 2 листовw</tex>, такую что <tex>dist(имеют степень одинu, w)</tex> максимально. Вершину <tex>w</tex> можно найти запуском <tex>BFS</tex> из <tex>u</tex>.

== Центр дерева ===== Определения ==={{ТеоремаОпределение|statementid =Искомое расстояние - есть расстояние между двумя листами.tree|proofdefinition =Пусть нет, пусть искомое расстояние - есть расстояние между вершинами '''Эксцентриситет вершины <tex>e(v)</tex>''' (англ. ''eccentricity of avertex'') — <tex>\max\limits_{u\in V} dist(v,bu)</tex> , где <tex>bV</tex> — множество вершин связного графа <tex>G</tex> - не является листом. Т}}{{Определение|id = tree|definition ='''Радиус <tex>r(G)</tex>''' (англ.к''radius'') — наименьший из эксцентриситетов вершин графа <tex>G</tex>. b не является листом}}{{Определение|id = tree|definition ='''Центральная вершина''' (англ. ''central vertex'') — вершина графа <tex>G</tex>, то значит её степень такая что <tex>>e(v) = r(G)</tex> 1 }}{{Определение|id =tree|definition ='''Центр графа <tex>G</tex> из неё существует ребро в непосещенную вершину ''' (дважды посетить вершину англ. ''center of a graph'') — множество всех центральных вершин графа <tex>bG</tex> мы не можем). Лемма доказана.

 Запустив BFS от произвольной вершины. Мы получим дерево BFS. ==== Алгоритм для дерева за O(n) ====

В дереве BFS не существует ребер между вершинами Каждое дерево имеет центр, состоящий из разных поддеревьев некоторого одной вершины или из общего предкадвух смежных вершин.

Такое Утверждение очевидно для деревьев с одной и двумя вершинами. Покажем, что у любого другого дерева <tex>T</tex> те же как центральные вершины, что и у дерева dfs<tex>T'</tex>, полученного из <tex>T</tex> удалением всех его висячих вершин. Расстояние от данной вершины дерева <tex>u</tex> до любой другой вершины <tex>v</tex> достигает наибольшего значения, когда <tex>v</tex> – висячая вершина. Таким образом, эксцентриситет каждой вершины дерева <tex>T'</tex> точно на единицу меньше эксцентриситета этой же вершины в дереве <tex>T</tex>, следовательно, центры этих деревьев совпадают. Продолжим процесс удаления и получим требуемое.

Мы свели задачу к нахождению вершины <tex>w</tex>Собственно, такой, что сумма глубин поддеревьев максимальнаалгоритм нахождения центра описан в доказательстве теоремы.

Докажем* Пройдёмся по дереву [[Обход_в_глубину, что одно из искомых поддеревьев содержит самый глубокий лист_цвета_вершин|обходом в глубину]] и пометим все висячие вершины числом <tex>0</tex>.* Обрежем помеченные вершины.* Образовавшиеся листья пометим числом <tex>1</tex> и тоже обрежем.* Будем повторять, пока на текущей глубине не окажется не более двух листьев, и при этом в дереве будет тоже не более двух листьев.  Оставшиеся листья являются центром дерева. Пусть нетДля того, тогда взяв расстояние от чтобы алгоритм работал за <tex>wO(n)</tex> до глубочайшего листа мы можем улучшить ответ, нужно обрабатывать листья по одному, поддерживая в [[Очередь|очереди]] два последовательных по глубине слоя.

Таким образом мы доказали, что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого bfs== См. также ==*[[Дерево, очевидно что ей в пару надо сопоставить вершину <tex>w</tex> _эквивалентные_определения|Дерево, что dist(uэквивалентные определения]]*[[Дополнительный, w) - <tex>max</tex> . Очевидно_самодополнительный_граф|Дополнительный, что проблема решается запуском bfs из <tex>u</tex>. самодополнительный граф]]