Алгоритмы на деревьях
Содержание
Диаметр дерева
Диаметр дерева — максимальная длина (в рёбрах) кратчайшего пути между любыми двумя вершинами.
Пусть дан граф . Тогда диаметром называется , где — кратчайшее расстояние между вершинами.
Алгоритм
- Возьмём любую вершину и найдём расстояния до всех других вершин.
- Возьмём вершину такую, что для любого . Снова найдём расстояние от до всех остальных вершин. Самое большое расстояние — диаметр дерева.
Расстояние до остальных вершин будем искать алгоритмом .
Реализация
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];
Обоснование корректности
Будем пользоваться свойством, что в любом дереве больше одного листа. Исключительный случай — дерево из одной вершины, но алгоритм сработает верно и в этом случае.
| Теорема: |
Искомое расстояние — расстояние между двумя листами. |
| Доказательство: |
| Пусть искомое расстояние — расстояние между вершинами , где не является листом. Так как не является листом, то её степень больше единицы, следовательно, из неё существует ребро в непосещённую вершину (дважды посетить вершину мы не можем). |
После запуска алгоритма получим дерево .
| Теорема: |
В дереве не существует ребер между вершинами из разных поддеревьев некоторого их общего предка. |
| Доказательство: |
|
Предположим, существует ребро между соседними поддеревьями: Рассмотрим первую вершину, в которую приведет наш алгоритм, пусть это вершина , тогда в ходе рассмотрения всех смежных вершин мы добавим в список вершину , тем самым исключив возможность попадания их в разные поддеревья. |
Мы свели задачу к нахождению вершины , такой что сумма глубин поддеревьев максимальна.
Докажем, что одно из искомых поддеревьев содержит самый глубокий лист. Пусть нет, тогда, взяв расстояние от до глубочайшего листа, мы можем улучшить ответ.
Таким образом мы доказали, что нам нужно взять вершину с наибольшей глубиной после первого , очевидно, что ей в пару надо сопоставить вершину , такую что максимально. Вершину можно найти запуском из .
Оценка производительности
Все операции кроме — . работает за линейное время, запускаем мы его 2 раза. Получаем .
Центр дерева
Определения
| Определение: |
| Эксцентриситет вершины — , где — множество вершин связного графа . |
| Определение: |
| Радиус — наименьший из эксцентриситетов вершин графа . |
| Определение: |
| Центральная вершина — вершина графа , такая что |
| Определение: |
| Центр графа — множество всех центральных вершин графа . |
| Теорема: |
Каждое дерево имеет центр, состоящий из одной вершины или из двух смежных вершин. |
| Доказательство: |
| Утверждение очевидно для деревьев с одной и двумя вершинами. Покажем, что у любого другого дерева те же центральные вершины, что и у дерева , полученного из удалением всех его висячих вершин. Расстояние от данной вершины дерева до любой другой вершины достигает наибольшего значения, когда – висячая вершина. Таким образом, эксцентриситет каждой вершины дерева точно на единицу меньше эксцентриситета этой же вершины в дереве , следовательно, центры этих деревьев совпадают. Продолжим процесс удаления и получим требуемое. |
Алгоритм
- Построим матрицу ( — мощность множества ), где , то есть матрицу кратчайших путей. Для её построения можно воспользоваться алгоритмом Флойда-Уоршелла или Дейкстры.
- Подсчитаем максимум в каждой строчке матрицы . Таким образом, получим массив длины .
- Найдём наименьший элемент в этом массиве. Эта вершина и есть центр графа. В том случае, когда вершин несколько, все они являются центрами.
Асимптотика зависит от используемого способа подсчета кратчайших путей. При Флойде это будет , а при Дейкстре — максимум из асимптотики конкретной реализации Дейкстры и , за которую мы находим максимумы в матрице.
