Час від часу на CodeForces з'являються питання про центр, радіусі та діаметрі графа (зміг нагугліть тільки про дерево. Хоча було більше). У цьому топіку дано визначення цих понять а також описані алгоритми для їх знаходження.
Завдання. даний не зважений неорієнтовані граф G = (V. E). де V це безліч вершин, а E - безліч ребер. Необхідно знайти його радіус, діаметр і центр.
Визначимо di. j як найкоротша відстань між парою вершин. Тоді діаметр графа визначається як максимально можливе серед всіх найкоротших відстаней між парою вершин:
Також введемо поняття ексцентриситету вершини як максимальна відстань від вершини до будь-якої іншої:
Знаючи ексцентриситет всіх вершин, можна визначити і радіус графа, як мінімальний з них:
Відразу можна помітити, що діаметр графа це максимальний ексцентриситет в графі, тобто:
Центром графа назвемо все вершини з ексцентриситетом, рівним радіусу графа:
Визначення дано і в голову приходить тривіальний алгоритм для знаходження центру, радіуса і діаметра для довільного графа за допомогою алгоритму Флойда-Уоршелла:
Тепер трохи змінимо постановку задачі: припустимо, що граф G є деревом. Для дерева нескладно довести наступний факт: кількість вершин в центрі дерева дорівнює одному або двом.
На CodeForces колись чув наступний алгоритм для знаходження центру дерева: за допомогою BFS-а з будь-якої вершини (позначимо її як v 1) знайти найвіддаленішу від v 1 вершину (позначимо як v 2), потім запустити BFS з v 2. вибрати будь-яку найвіддаленішу від v 2 вершину (нехай буде v 3). Вершина (-и) на середині шляху між v 2 і v 3 утворюють центр графа, відстань між ними - діаметр. Радіусом ж буде половина діаметра, округлена вгору: (diam (G) + 1) / 2. Реалізацію цього алгоритму тут наводити не буду, так як вона мені здалася дещо громіздкою. Замість цього наведу інший алгоритм, який мені здався простіше в реалізації.
Теорема: Нехай L - безліч всіх листя графа. Якщо | V | ≤ 2. то L є центром графа, інакше можна видалити всі листи і центр графа не зміниться:
Ця теорема приводить нас до наступного алгоритму: будемо видаляти листя дерева, шар за шаром, поки не залишиться ≤ 2 вершин. Ці вершини і будуть центром графа. Реалізація даного алгоритму дуже схожа на пошук в ширину:
Неважко довести, що після виконання даного алгоритму, центр дерева буде в безлічі c. і rad (G) = (diam (G) + 1) / 2.
Завдання по темі:
Дякую за увагу, щодо помилок прохання писати в личку.
діаметр. радіус. дерево. граф. центр дерева