Алгоритми на деревах

Зміст

Діаметр дерева [ред.]

Визначення:
Діаметр дерева(англ.diameter of a tree) - максимальна довжина (в ребрах) найкоротшого шляху в дереві між будь-якими двома вершинами.

Нехай даний граф [math]G = \langle V, E \rangle [/math] . Тоді діаметром [math]d[/math] називається [math]\max\limits_ 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] .

Реалізація [ред.]

Обгрунтування коректності [ред.]

Будемо користуватися властивістю, що в будь-якому дереві більше одного листа. Винятковий випадок – дерево з однієї вершини, але алгоритм спрацює правильно і в цьому випадку.

Теорема:

Доказ:[math]\triangleright[/math]Нехай відстань — відстань між вершинами [math]a, b[/math] , де [math]b[/math] не є листом. Оскільки [math]b[/math] перестав бути листом, її ступінь більше одиниці, отже, із неї існує ребро в непосеченную вершину (двічі відвідати вершину [math]b[/math] ми можемо).[math]\triangleleft[/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_ 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 math

Алгоритм [ред.]

Наївний алгоритм [ред.]

Знайдемо центр графа з його визначення.

  • Побудуємо матрицю [math]A_[/math] ([math]n[/math] — потужність множини [math]V[/math] ), де [math]a_ = d_[/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] , потрібно обробляти листя по одному, підтримуючи у черзі два послідовних по глибині шару.