Доводимо коректність пошуку діаметра дерева

Одного разу на заліку мені попалася наступна задача. Придумайте алгоритм, що знаходить дві вершини дерева з максимальною відстанню один від одного, і доведіть його коректність. В той момент я в принципі не знала, що у дерев є діаметр, радіус і багато інших речей. Вже після заліку один просвітив мене, розповівши, що це за алгоритм, але без докази. Саме питанням про доказі довгий час була забита моя голова. Після прочитання кількох статей, стало зрозуміло, що матеріал не вщухне, поки самостійно собі не поясню все практично на пальцях (може, і читачеві доведеться за смаком). Перейдемо від демагогії до суті.

Діаметр дерева — це максимальна відстань між двома вершинами в дереві. Алгоритм пошуку складається в двох запусках BFS. Перший іде від довільної вершини дерева, під час обходу нараховуються відстані від поточної вершини до всіх інших. Потім з них вибирається найбільш віддалена. З неї робиться другий запуск BFS. Нараховуються нові відстані. Максимальне серед них і діаметром.

Чому цей простий на вигляд алгоритм працює коректно?

Щоб уникнути підводних каменів при доказі, відразу обговоримо випадок з деревом з однієї вершини і з двох вершин. Якщо вершина одна, то ребер у нас немає, перший BFS повідомить, що стартова вершина має максимальну глибину, другий — теж. По суті це і є так, алгоритм спрацює вірно. Якщо є дві вершини, то перший обхід прийде в другу вершину, а другий — в стартову, що коректно для даного випадку.

Спочатку зрозуміємо, що шукана відстань — відстань між двома листами. Насправді, нехай вершина на кінці знайденого максимального шлях не є листом. Одночасно ми не можемо збільшити шукану відстань по припущенню. Тим не менш, це означає, що BFS не відвідав вершини, «розташовані» за поточною, що суперечить коректності BFS. Виходить, що обидві знайдені вершини будуть листям. Чудово.

Підвісимо наше дерево за вершину v, з якої запускаємо перший обхід.

Розглянемо окремий випадок, коли вершина v сама є листом. У разі, якщо вона і є перший кінець діаметра, то очевидно, що перший BFS знайде другий кінець, а другий повернеться в стартовий вершину. Інакше діаметр не буде проходити через v і також буде «перегинатися», так як не може містити більше двох листків.

Нехай ми знайшли діаметр і дві вершини, що йому відповідають. Знайдемо LCA цих вершин a b, назвемо цю вершину c. Очевидно, що D = d[a,c] + d[c,b]. Фактично діаметр це сума двох найбільш глибоких піддерев деякої вершини, якщо вона належить найдовшого шляху. Діаметр дерева — це максимальний діаметр серед всіх піддерев. Перший обхід в ширину дасть нам максимальну по глибині вершину (так як ми підвісили за стартову вершину). Позначимо вершину на кінці знайденого шляху w. Доведемо, що w належатиме шуканого найдовшого шляху. Нехай діаметр «перегинається» у вершині c(він буде «перегинатися», так як поєднує два листа, а дерево підвішене за вершину v, яка не є листом). Нехай вершина w належить одному з піддерев вершини c. Тоді просто замінимо деяку частину шляху (c, x), x — один з кінців, на (c, w). d[c,x] < d[c,w]. Ми поліпшили відповідь. Отже, початковий шлях не був діаметром. Якщо w є предком c, w не є листом, тому цей випадок відпадає. Якщо ж w знаходиться десь в іншому поддереве, то нехай e = LCA(c, w). d[w,e] — максимальна глибина піддерево e. Тоді так як e — предок c, d[x, e] > d[x,c]. d[w,e] > d[y,e] > d[y,c]. Тому D0 = d[x,c] + d[y,c] < d[x, e] + d[w, e] = D. Отже, спочатку діаметр був знайдений невірно і вершина w належить діаметру.

Примітка:
В даній частині докази ми використовували властивість, що лист w має найбільшу глибину в будь-якому поддереве даного дерева, якому належить w. Доведемо методом математичної індукції. База — один лист w. Очевидно, що твердження вірне. Нехай для деякого піддерева це теж вірно, тоді піднімемося на вищий рівень. Припустимо, існує вершина, в якій глибина в поточному поддереве більше, ніж у w. Назвемо поточну вершину a, вершину з передбачуваної більшою глибиною x, корінь дерева v.
d[v,x] = d[v,a] + d[a,x];
d[v,w] = d[v,a] + d[a,w];

d[v,x] < d[v,w] чинності коректності роботи BFS;
d[a,x] > d[a,w] за припущенням;
У підсумку отримуємо протиріччя. Тому вершина w володіє найбільшою глибиною у будь-якому поддереве.

Отримуємо, що вершина w належить діаметру, а також є одним з його кінців. Тоді очевидно, що залишається лише знайти найбільш віддалену від w вершину, що і робить другий BFS.

При написанні статті використовувалися матеріали:
neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BD%D0%B0_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F%D1%85
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.