Изменения

Пусть дан граф <tex>G = <V, E></tex> Тогда диаметром <tex>d</tex> называется <tex>\max\limits_= Диаметр дерева =={{u, v \in V} distОпределение|id = tree|definition ='''Диаметр дерева''' (v, uангл. ''diameter of a tree'')</tex>, где <tex>dist</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 , u \subset graph, v \ne u \}in V </tex> и найдём расстояния до всех других вершин. <tex>d[i] = dist(v, ui) </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 |statement= u = w В дереве <tex>BFS</tex> не существует ребер между вершинами из разных поддеревьев некоторого их общего предка.|proof= 0; d = bfs(gПредположим, существует ребро <tex>u,v); </tex> между соседними поддеревьями: for(i = 0; i Рассмотрим первую вершину, в которую приведет наш алгоритм, пусть это вершина < n; i++) if (d[i] tex> d[u]) 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>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 не существует ребер между вершинами Каждое дерево имеет центр, состоящий из разных поддеревьев некоторого их общего предкаодной вершины или из двух смежных вершин.

Такое же как Утверждение очевидно для деревьев с одной и двумя вершинами. Покажем, что у любого другого дерева dfs.Такое <tex>T</tex> те же как центральные вершины, что и у дерева dfs<tex>T'</tex>, полученного из <tex>T</tex> удалением всех его висячих вершин. [http:Расстояние от данной вершины дерева <tex>u</tex> до любой другой вершины <tex>v</neerctex> достигает наибольшего значения, когда <tex>v</tex> – висячая вершина.ifmo.ruТаким образом, эксцентриситет каждой вершины дерева <tex>T'</wikitex> точно на единицу меньше эксцентриситета этой же вершины в дереве <tex>T</index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83tex>, следовательно,_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.BE.D0.B1.D1.85.D0.BE.D0.B4.D0.B0_.D0.B2_.D0.B3.D0.BB.D1.83.D0.B1.D0.B8.D0.BDцентры этих деревьев совпадают.D1Продолжим процесс удаления и получим требуемое.83]

Мы свели задачу к нахождению вершины <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>. самодополнительный граф]]