Изменения

Пусть дан граф <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] \ge 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) {{Теорема v |statement= u = w Искомое расстояние — расстояние между двумя листами.|proof= 0; d = bfs(gПусть искомое расстояние — расстояние между вершинами <tex>a, b</tex>,v); for(i = 0; i где <tex>b</tex> не является листом. Так как <tex>b< n; i++) if (d[i] /tex> d[u]) u = i; bfs(gне является листом, то её степень больше единицы, следовательно,u); forиз неё существует ребро в непосещённую вершину (i = 0; i дважды посетить вершину <tex>b< n; i++) if (d[i] /tex> d[w]мы не можем). w = i; return d[w]; }}

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

{{Теорема|statement=Искомое расстояние - есть расстояние между двумя листами.|proof=Пусть искомое расстояние - есть расстояние между вершинами Таким образом мы доказали, что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого <tex>BFS</tex>a,bочевидно, что ей в пару надо сопоставить вершину <tex>w</tex> где , такую что <tex>bdist(u, w)</tex> - не является листоммаксимально. Т.к. b не является листом, то значит её степень Вершину <tex>w</tex>можно найти запуском <tex>BFS</tex> 1 => из неё существует ребро в непосещенную вершину (дважды посетить вершину <tex>bu</tex> мы не можем). Лемма доказана.}}

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

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

Мы свели задачу к нахождению вершины <tex>w</tex>, такой, что сумма глубин поддеревьев максимальна.== Источники информации ==* [[wikipedia:Distance_(graph_theory)|Wikipedia {{---}} Distance (graph theory)]]Докажем, что одно из искомых поддеревьев содержит самый глубокий лист* ''Ф. Харари'': Теория графовПусть нет, тогда взяв расстояние от <tex>w<* [http:/tex> до глубочайшего листа мы можем улучшить ответ/rain.ifmo.  Таким образом мы доказали, что нам нужно взять вершину <tex>u<ru/tex> с наибольшей глубиной после первого <tex>bfs<cat/tex>, очевидно что ей в пару надо сопоставить вершину <tex>w<data/tex> , что <tex>dist(u, w)<theory/tex> {{graph-location/centers--}} максимально2006/article. Очевидно, что проблема решается запуском bfs из <tex>u</tex>pdf ''А. Клебанов'': Центры графов(нерабочая ссылка)]