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

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

Діаметр дерева - це максимальна відстань між двома вершинами в дереві. Алгоритм пошуку полягає в двох запусках 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