Алгоритмы на деревьях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 130 промежуточных версий 10 участников)
Строка 1: Строка 1:
'''Диаметр дерева''' - максимальная длина кратчайшего пути между любыми двумя вершинами.
+
__TOC__
Алгоритм в этой статье находил диаметр в дереве,при чём очень простым алгоритмом.
 
  
Алгоритм:
+
== Диаметр дерева ==
Возьмём любую вершину V и найдём расстояния до всех других вершин.
+
{{Определение
 +
|id = tree
 +
|definition =
 +
'''Диаметр дерева''' (англ. ''diameter of a tree'') — максимальная длина (в рёбрах) кратчайшего пути в дереве между любыми двумя вершинами.
 +
}}
  
d = max{<tex> v </tex>,<tex> u </tex> <tex> \subset graph, </tex> <tex> v \ne u </tex>} dist(<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> u </tex> такую,что d[u] >= d[t] для $\forall$ t.Снова найдём расстояние до всех остальных вершин.Самое большое расстояние-диаметр дерева.
+
=== Алгоритм ===
Расстояние до остальных вершин удобно искать алгоритмом BFS.
+
* Возьмём любую вершину <tex> v \in V </tex> и найдём расстояния до всех других вершин. <tex>d[i] = dist(v, 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]
  
void diameter(graph g)             
+
=== Обоснование корректности ===
{
+
Будем пользоваться свойством, что в любом дереве больше одного листа. Исключительный случай — дерево из одной вершины, но алгоритм сработает верно и в этом случае.
    v = u = w = 0;
 
    bfs(v); // заполняет массив d[n] расстояниями до всех вершин.
 
    for(i = 0; i < n; i++)
 
          if (d[i] > d[u])
 
              u = i;
 
    bfs(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> не является листом. Так как <tex>b</tex> не является листом, то её степень больше единицы, следовательно, из неё существует ребро в непосещённую вершину (дважды посетить вершину <tex>b</tex> мы не можем).
 +
}}
  
Обоснование корректности:
+
После запуска алгоритма получим дерево <tex>BFS</tex>.
Будем пользоваться свойством,что в любом дереве >= 2 висячих вершин(степерь у них = 1)
 
Докажем вспомогательную лемму:
 
Искомое расстояние - есть расстояние между двумя листами.
 
Доказательство: пусть нет, пусть искомое расстояние - есть расстояние между вершина a, b, где b - не является листом.Т.к. b не является листом, то значит её степень > 1 => из неё существует ребро в непосещенную вершину (дважды посетить вершину b мы не можем). Лемма доказана.
 
  
Запустив BFS от произвольной вершины. Мы получим дерево BFS.
+
{{Теорема
Теорема. В дереве BFS не существует ребер между вершинами из разных поддеревьев некоторого из общего предка.
+
|statement=
Доказательство как про дерево DFS.
+
В дереве <tex>BFS</tex> не существует ребер между вершинами из разных поддеревьев некоторого их общего предка.
 +
|proof=
 +
Предположим, существует ребро <tex>u, v</tex> между соседними поддеревьями:
 +
Рассмотрим первую вершину, в которую приведет наш алгоритм, пусть это вершина <tex>u</tex>, тогда в ходе рассмотрения всех смежных вершин <tex>u</tex> мы добавим в список вершину <tex>v</tex>, тем самым исключив возможность попадания их в разные поддеревья.
 +
}}
  
Мы свели задачу к нахождению вершины v, такой, что сумма глубин поддеревьев максимальна.
+
 
 +
Мы свели задачу к нахождению вершины <tex>w</tex>, такой что сумма глубин поддеревьев максимальна.
  
 
Докажем, что одно из искомых поддеревьев содержит самый глубокий лист.  
 
Докажем, что одно из искомых поддеревьев содержит самый глубокий лист.  
Пусть нет, тогда взяв расстояние от v до глубочайшего листа мы можем улучшить ответ.  
+
Пусть нет, тогда, взяв расстояние от <tex>w</tex> до глубочайшего листа, мы можем улучшить ответ.  
 +
 
 +
Таким образом мы доказали, что нам нужно взять вершину <tex>u</tex> с наибольшей глубиной после первого <tex>BFS</tex>, очевидно, что ей в пару надо сопоставить вершину <tex>w</tex>, такую что <tex>dist(u, w)</tex> максимально. Вершину <tex>w</tex> можно найти запуском <tex>BFS</tex> из <tex>u</tex>.
 +
 
 +
=== Оценка времени работы ===
 +
Все операции кроме <tex>BFS</tex> — <tex>O(1)</tex>.
 +
<tex>BFS</tex> работает за линейное время, запускаем мы его два раза. Получаем <tex>O(|V| + |E|)</tex>.
 +
 
 +
== Центр дерева ==
 +
=== Определения ===
 +
{{Определение
 +
|id = tree
 +
|definition =
 +
'''Эксцентриситет вершины <tex>e(v)</tex>''' (англ. ''eccentricity of a vertex'') — <tex>\max\limits_{u\in V} dist(v, u)</tex>, где <tex>V</tex> — множество вершин связного графа <tex>G</tex>.
 +
}}
 +
{{Определение
 +
|id = tree
 +
|definition =
 +
'''Радиус <tex>r(G)</tex>''' (англ. ''radius'') — наименьший из эксцентриситетов вершин графа <tex>G</tex>.
 +
}}
 +
{{Определение
 +
|id = tree
 +
|definition =
 +
'''Центральная вершина''' (англ. ''central vertex'') — вершина графа <tex>G</tex>, такая что <tex>e(v) = r(G)</tex>
 +
}}
 +
{{Определение
 +
|id = tree
 +
|definition =
 +
'''Центр графа <tex>G</tex>''' (англ. ''center of a graph'') — множество всех центральных вершин графа <tex>G</tex>.
 +
}}
 +
[[Файл:Центральные_вершины.png|300px|thumb|left|Примеры деревьев с одной и двумя центральными вершинами]]
 +
[[Файл:Эксцентриситеты.png|400px|thumb|center|Графы, у которых показан эксцентриситет каждой вершины]]
 +
 
 +
=== Алгоритм ===
 +
==== Наивный алгоритм ====
 +
Найдём центр графа исходя из его определения.
 +
* Построим матрицу <tex>A_{n \times n}</tex> (<tex>n</tex> — мощность множества <tex>V</tex>), где <tex>a_{ij} = d_{ij}</tex>, то есть матрицу кратчайших путей. Для её построения можно воспользоваться [[Алгоритм_Флойда|алгоритмом Флойда-Уоршелла]] или [[Алгоритм_Дейкстры|Дейкстры]].
 +
* Подсчитаем максимум в каждой строчке матрицы <tex>A</tex>. Таким образом, получим массив длины <tex>n</tex>.
 +
* Найдём наименьший элемент в этом массиве. Эта вершина и есть центр графа. В том случае, когда вершин несколько, все они являются центрами.
 +
Асимптотика зависит от используемого способа подсчета кратчайших путей. При Флойде это будет <tex>O(V^3)</tex>, а при Дейкстре — максимум из асимптотики конкретной реализации Дейкстры и <tex>O(V^2)</tex>, за которую мы находим максимумы в матрице.
 +
 
 +
==== Алгоритм для дерева за O(n) ====
 +
 
 +
{{Теорема
 +
|statement=
 +
Каждое дерево имеет центр, состоящий из одной вершины или из двух смежных вершин.
 +
|proof=
 +
Утверждение очевидно для деревьев с одной и двумя вершинами. Покажем, что у любого другого дерева <tex>T</tex> те же центральные вершины, что и у дерева <tex>T'</tex>, полученного из <tex>T</tex> удалением всех его висячих вершин. Расстояние от данной вершины дерева <tex>u</tex> до любой другой вершины <tex>v</tex> достигает наибольшего значения, когда <tex>v</tex> – висячая вершина. Таким образом, эксцентриситет каждой вершины дерева <tex>T'</tex> точно на единицу меньше эксцентриситета этой же вершины в дереве <tex>T</tex>, следовательно, центры этих деревьев совпадают. Продолжим процесс удаления и получим требуемое.
 +
}}
 +
 
 +
Собственно, алгоритм нахождения центра описан в доказательстве теоремы.
 +
 
 +
* Пройдёмся по дереву [[Обход_в_глубину,_цвета_вершин|обходом в глубину]] и пометим все висячие вершины числом <tex>0</tex>.
 +
* Обрежем помеченные вершины.
 +
* Образовавшиеся листья пометим числом <tex>1</tex> и тоже обрежем.
 +
* Будем повторять, пока на текущей глубине не окажется не более двух листьев, и при этом в дереве будет тоже не более двух листьев.
 +
 
 +
Оставшиеся листья являются центром дерева.
 +
 
 +
Для того, чтобы алгоритм работал за <tex>O(n)</tex>, нужно обрабатывать листья по одному, поддерживая в [[Очередь|очереди]] два последовательных по глубине слоя.
 +
 
 +
== См. также ==
 +
*[[Дерево,_эквивалентные_определения|Дерево, эквивалентные определения]]
 +
*[[Дополнительный,_самодополнительный_граф|Дополнительный, самодополнительный граф]]
  
Таким образом мы доказали, что нам нужно взять наиглубочайшую вершину t после первого bfs, очевидно что ей в пару надо сапоставить вершину p , что dist(t, p) - max . Очевидно, что проблема решается запуском bfs из t.  
+
== Источники информации ==
 +
* [[wikipedia:Distance_(graph_theory)|Wikipedia {{---}} Distance (graph theory)]]
 +
* ''Ф. Харари'': Теория графов
 +
* [http://rain.ifmo.ru/cat/data/theory/graph-location/centers-2006/article.pdf ''А. Клебанов'': Центры графов(нерабочая ссылка)]
  
Оценка производительности:
+
[[Категория: Дискретная математика и алгоритмы]]
Все операции кроме bfs - О(1)
+
[[Категория: Основные определения теории графов]]
BFS работает линейное время,запускаем мы его 2 раза.Получаем O(V+E)
 

Текущая версия на 19:11, 4 сентября 2022

Диаметр дерева

Определение:
Диаметр дерева (англ. diameter of a tree) — максимальная длина (в рёбрах) кратчайшего пути в дереве между любыми двумя вершинами.


Пусть дан граф [math]G = \langle V, E \rangle [/math]. Тогда диаметром [math]d[/math] называется [math]\max\limits_{u, v \in V} dist(v, u)[/math], где [math]dist[/math] — кратчайшее расстояние между вершинами.

Алгоритм

  • Возьмём любую вершину [math] v \in V [/math] и найдём расстояния до всех других вершин. [math]d[i] = dist(v, i)[/math]
  • Возьмём вершину [math] u \in V [/math] такую, что [math]d[u] \geqslant d[t][/math] для любого [math]t[/math]. Снова найдём расстояние от [math]u[/math] до всех остальных вершин. Самое большое расстояние — диаметр дерева.

Расстояние до остальных вершин будем искать алгоритмом [math]BFS[/math].

Реализация

//граф g представлен списком смежности 
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]

Обоснование корректности

Будем пользоваться свойством, что в любом дереве больше одного листа. Исключительный случай — дерево из одной вершины, но алгоритм сработает верно и в этом случае.

Теорема:
Искомое расстояние — расстояние между двумя листами.
Доказательство:
[math]\triangleright[/math]
Пусть искомое расстояние — расстояние между вершинами [math]a, b[/math], где [math]b[/math] не является листом. Так как [math]b[/math] не является листом, то её степень больше единицы, следовательно, из неё существует ребро в непосещённую вершину (дважды посетить вершину [math]b[/math] мы не можем).
[math]\triangleleft[/math]

После запуска алгоритма получим дерево [math]BFS[/math].

Теорема:
В дереве [math]BFS[/math] не существует ребер между вершинами из разных поддеревьев некоторого их общего предка.
Доказательство:
[math]\triangleright[/math]

Предположим, существует ребро [math]u, v[/math] между соседними поддеревьями:

Рассмотрим первую вершину, в которую приведет наш алгоритм, пусть это вершина [math]u[/math], тогда в ходе рассмотрения всех смежных вершин [math]u[/math] мы добавим в список вершину [math]v[/math], тем самым исключив возможность попадания их в разные поддеревья.
[math]\triangleleft[/math]


Мы свели задачу к нахождению вершины [math]w[/math], такой что сумма глубин поддеревьев максимальна.

Докажем, что одно из искомых поддеревьев содержит самый глубокий лист. Пусть нет, тогда, взяв расстояние от [math]w[/math] до глубочайшего листа, мы можем улучшить ответ.

Таким образом мы доказали, что нам нужно взять вершину [math]u[/math] с наибольшей глубиной после первого [math]BFS[/math], очевидно, что ей в пару надо сопоставить вершину [math]w[/math], такую что [math]dist(u, w)[/math] максимально. Вершину [math]w[/math] можно найти запуском [math]BFS[/math] из [math]u[/math].

Оценка времени работы

Все операции кроме [math]BFS[/math][math]O(1)[/math]. [math]BFS[/math] работает за линейное время, запускаем мы его два раза. Получаем [math]O(|V| + |E|)[/math].

Центр дерева

Определения

Определение:
Эксцентриситет вершины [math]e(v)[/math] (англ. eccentricity of a vertex) — [math]\max\limits_{u\in V} dist(v, u)[/math], где [math]V[/math] — множество вершин связного графа [math]G[/math].


Определение:
Радиус [math]r(G)[/math] (англ. radius) — наименьший из эксцентриситетов вершин графа [math]G[/math].


Определение:
Центральная вершина (англ. central vertex) — вершина графа [math]G[/math], такая что [math]e(v) = r(G)[/math]


Определение:
Центр графа [math]G[/math] (англ. center of a graph) — множество всех центральных вершин графа [math]G[/math].
Примеры деревьев с одной и двумя центральными вершинами
Графы, у которых показан эксцентриситет каждой вершины

Алгоритм

Наивный алгоритм

Найдём центр графа исходя из его определения.

  • Построим матрицу [math]A_{n \times n}[/math] ([math]n[/math] — мощность множества [math]V[/math]), где [math]a_{ij} = d_{ij}[/math], то есть матрицу кратчайших путей. Для её построения можно воспользоваться алгоритмом Флойда-Уоршелла или Дейкстры.
  • Подсчитаем максимум в каждой строчке матрицы [math]A[/math]. Таким образом, получим массив длины [math]n[/math].
  • Найдём наименьший элемент в этом массиве. Эта вершина и есть центр графа. В том случае, когда вершин несколько, все они являются центрами.

Асимптотика зависит от используемого способа подсчета кратчайших путей. При Флойде это будет [math]O(V^3)[/math], а при Дейкстре — максимум из асимптотики конкретной реализации Дейкстры и [math]O(V^2)[/math], за которую мы находим максимумы в матрице.

Алгоритм для дерева за O(n)

Теорема:
Каждое дерево имеет центр, состоящий из одной вершины или из двух смежных вершин.
Доказательство:
[math]\triangleright[/math]
Утверждение очевидно для деревьев с одной и двумя вершинами. Покажем, что у любого другого дерева [math]T[/math] те же центральные вершины, что и у дерева [math]T'[/math], полученного из [math]T[/math] удалением всех его висячих вершин. Расстояние от данной вершины дерева [math]u[/math] до любой другой вершины [math]v[/math] достигает наибольшего значения, когда [math]v[/math] – висячая вершина. Таким образом, эксцентриситет каждой вершины дерева [math]T'[/math] точно на единицу меньше эксцентриситета этой же вершины в дереве [math]T[/math], следовательно, центры этих деревьев совпадают. Продолжим процесс удаления и получим требуемое.
[math]\triangleleft[/math]

Собственно, алгоритм нахождения центра описан в доказательстве теоремы.

  • Пройдёмся по дереву обходом в глубину и пометим все висячие вершины числом [math]0[/math].
  • Обрежем помеченные вершины.
  • Образовавшиеся листья пометим числом [math]1[/math] и тоже обрежем.
  • Будем повторять, пока на текущей глубине не окажется не более двух листьев, и при этом в дереве будет тоже не более двух листьев.

Оставшиеся листья являются центром дерева.

Для того, чтобы алгоритм работал за [math]O(n)[/math], нужно обрабатывать листья по одному, поддерживая в очереди два последовательных по глубине слоя.

См. также

Источники информации