Как найти радиус диаметр центр графа

1. Основные
   определения

Граф
– это совокупность двух множеств: вершини ребер,
между которыми определено отношениеинцидентности.

Каждое ребро e
из E
инцидентно ровно двум вершинам
и,
которые оно соединяет. При этом вершинаи реброe
называются инцидентными
друг другу, а вершины
иназываютсясмежными.

Принято обозначение
n
для числа вершин графа (мощность множества
):иm
для числа его ребер:
.
Говорят, что графG
есть (n,
m)
граф, где n
– порядок графа, m
– размер графа.

Если все ребра
графа неориентированные, т.е. пары
вершин, определяющие элементы множестваE,
неупорядочены, то такой граф называется
неориентированным графом, или неографом.
На рис. 12.1 показан пример неографа. Этот
граф имеет пять вершин и шесть ребер.

Рис. 12.1

Маршрут
– последовательность ребер, в которой
каждые два соседних ребра имеют общую
вершину. Граф связен,
если любые две вершины соединены хотя
бы одним маршрутом. Число ребер маршрута
определяет его длину.

Ребра, инцидентные
одной паре вершин, называются параллельными
или кратными.
Граф с кратными ребрами называется
мультиграфом.

Ребро
называетсяпетлей
(концевые вершины совпадают). Граф,
содержащий петли и кратные ребра,
называется псевдографом.
На рис. 12.2 показан псевдограф.

Рис. 12.2

Степень
deg(v)
вершины – это число ребер, инцидентных
v.
В неографе
сумма степеней всех вершин равна
удвоенному числу ребер
(лемма о рукопожатиях):

. (12.1)

Петля дает вклад,
равный 2, в степень вершины.

Степенная
последовательность
– последовательность степеней всех
вершин графа, записанная в определенном
порядке (по возрастанию или убыванию).

Пример
12.1. Степенная
последовательность неографа, изображенного
на рис. 12.1, записанная по возрастанию,
выглядит так:

=1,
=2,=3,=3,=3.

Сумма степеней
всех вершин графа равна:

.

Этот результат
не противоречит лемме о рукопожатиях,
поскольку граф имеет шесть ребер (m
= 6).

Матрица
смежности
графа – квадратная матрица A
порядка n,
где элемент
равен числу ребер, соединяющих вершиныi
и j.

Пример 12.2.
Граф, показанный на рис. 12.1, имеет
следующую матрицу смежности

.

Матрица
инцидентности
I
– еще один способ описания графа. Число
строк этой матрицы равно числу вершин,
число столбцов – числу ребер;
=1,
если вершинаv
инцидентна ребру e;
в противном случае
=0.
В каждом столбце матрицы инцидентности
простого графа (без петель и без кратных
ребер) содержится по две единицы. Число
единиц в строке равно степени
соответствующей вершины.

Пример 12.3.
Граф, показанный на рис. 12.1, имеет
следующую матрицу инцидентности

.

Граф
называетсяподграфом
графа
,
еслии.
Если,
то подграф называетсяостовным.

Компонента
связности
графа – максимальный по включению
вершин и ребер связной подграф.

Ранг
графа
,
гдеk
– число компонент связности.

Дерево
– связной граф, содержащий n
– 1 ребро.

Пример 12.4.
На рис. 12.3 показано дерево, которое
одновременно является остовным подграфом
графа, показанного на рис. 12.1.

Рис. 12.3

1. Радиус, диаметр
   и центр графа

Вычисление
расстояний и определение маршрутов в
графе являются одной из наиболее
очевидных и практичных задач, которые
возникают в теории графов. Введем
некоторые необходимые определения.

Эксцентриситет
вершины графа – расстояние до максимально
удаленной от нее вершины. Для графа, для
которого не определен вес
его ребер, расстояние определяется в
виде числа ребер.

Радиус
графа – минимальный эксцентриситет
вершин, а диаметр
графа – максимальный эксцентриситет
вершин.

Центр
графа образуют вершины, у которых
эксцентриситет равен радиусу. Центр
графа может состоять из одной, нескольких
или всех вершин графа.

Периферийные
вершины имеют эксцентриситет, равный
диаметру.

Простая цепь с
длиной, равной диаметру графа, называется
диаметральной.

Теорема 12.1.
В связном графе диаметр не больше ранга
его матрицы смежности.

Теорема 12.2.
(Жордана) Каждое дерево имеет центр,
состоящий из одной или двух смежных
вершин.

Теорема 12.3.
Если диаметр дерева четный, то дерево
имеет единственный центр, и все
диаметральные цепи проходят через него,
если диаметр нечетный, то центров два
и все диаметральные цепи содержат ребро,
их соединяющее.

Очевидно практическое
значение центра графа. Если, например,
речь идет о графе дорог с вершинами-городами,
то в математическом центре целесообразно
размещать административный центр,
складские помещения и т.п. Этот же подход
можно применять и для взвешенного графа,
где расстояния – это веса ребер. В
качестве веса можно брать евклидовое
расстояние, время или стоимость
передвижения между пунктами.

Пример 12.5.
Найти радиус, диаметр и центр графа,
изображенного на рис. 12.1.

Решение.
В данной задаче удобно использовать
матрицу
расстояний S.
Элемент этой квадратной симметричной
матрицы
равен расстоянию между вершинойi
и вершиной j.
Для графа, показанного на рис. 12.1, матрица
расстояний имеет следующий вид:

. (12.2)

Вычислим
эксцентриситет
каждой вершины. Эту величину можно
определить как максимальный элемент
соответствующего столбца матрицы
расстояний (или строки – поскольку
матрицаS
симметрична).
Получаем

Радиус графа r
– минимальный эксцентриситет вершин.
В данном случае r
= 2. Такой эксцентриситет имеют вершины
№ 2, № 4 и № 5. Эти вершины образуют центр
графа. Диаметр графа d
– максимальный эксцентриситет вершин.
В данном случае d
= 3. Такой эксцентриситет имеют вершины
№ 1 и № 3, это периферия графа. В
исследованном графе вершины оказались
либо центральными, либо периферийными.
В графах большего порядка существуют
и другие вершины.

Эксцентриситеты
вершин небольшого графа легко вычислять
непосредственным подсчетом по рисунку.
Однако не всегда граф задан своим
рисунком. Кроме того, граф может иметь
большой размер. Поэтому необходим другой
способ решения предыдущей задачи.
Известна следующая теорема.

Теорема
12.4. Пусть
– матрица смежности графаG
без петель и
,
где.
Тогдаравно числу маршрутов длиныk
от вершины
к вершине.

Решение задач
теории графов с помощью различных
преобразований матрицы смежности
называют алгебраическим
методом.

Пример 12.6.
Найти матрицу расстояний графа,
изображенного на рис. 12.1, алгебраическим
методом.

Решение.
Матрица смежности данного графа равна:

.

Будем заполнять
матрицу расстояний, рассматривая степени
матрицы смежности. Единицы матрицы
смежности показывают пары вершин,
расстояние между которыми равно единице
(т.е. они соединены одним ребром).

.

Диагональные
элементы матрицы расстояний – нули.
Умножаем матрицу смежности на себя:

.

Согласно теореме
между вершинами 2 и 3, 1 и 4 и т.д. имеется
некоторое число маршрутов длиной 2
(поскольку степень матрицы равна двум).
Число маршрутов здесь не используется,
важен сам факт наличия маршрута и его
длина, на что и указывает ненулевой
элемент степени матрицы, не совпадающий
с элементом, отмеченным при вычислении
маршрута меньшей длины. Проставляем 2
в незаполненные элементы матрицы
расстояний и получаем следующее
приближение:

.

Осталось неизвестным
расстояние между вершинами 1 и 3. Будем
умножать матрицу смежности

саму на себя до тех пор, пока в матрице


не появится ненулевой элемент
.
Тогда соответствующий элемент матрицы
расстояний равен степени матрицы
смежности:
.
На следующем шаге получаем

,

следовательно,
,
и окончательно

.

Полученная матрица
совпадает с матрицей расстояний S
(12.2), найденной непосредственными
вычислениями по рисунку.

1. Эйлерова цепь

Маршрут в неографе,
в котором все ребра разные, называется
цепью.
Цепь в графе называется эйлеровой,
если она содержит все ребра и все вершины
графа.

Рис. 12.4. Схема
Кенигсбергских мостов

Теория графов
многократно переоткрывалась разными
авторами при решении различных прикладных
задач. В их ряду – знаменитый математик
Леонард Эйлер (1707-1783). К созданию теории
графов его подтолкнула задача о
Кенигсберских мостах, которую он решил
в 1736 году. По условию задачи требовалось
пройти по всем семи мостам города
Кенигсберга через реку Преголь по одному
разу и вернуться к исходной точке. На
рис. 12.4 показана схема этих мостов (один
из них соединяет между собой два острова,
а остальные – острова с берегами). Этой
схеме соответствует приведенный на
следующем рисунке мультиграф с четырьмя
вершинами.

Рис. 12.5

Эйлер решил задачу
о Кенигсбергских мостах в отрицательном
смысле. Он доказал, что данная задача
не имеет решения. Для этого ему пришлось
доказать следующую теорему.

Теорема 12.5
(Эйлера).
Мультиграф обладает эйлеровой цепью
тогда и только тогда, когда он связен и
число вершин нечетной степени равно 0
или 2.

Вершины нечетной
степени в этой теореме, очевидно, являются
началом и концом цепи. Если таких вершин
нет, то эйлерова цепь становится эйлеровым
циклом.
Граф, обладающий эйлеровым циклом,
называется эйлеровым.
Если граф имеет эйлерову цепь, но не
обладает эйлеровым циклом (число вершин
нечетной степени равно 2), то он называется
полуэйлеровым
графом.

Предположим, что
граф имеет эйлеров цикл. Двигаясь по
нему, будем подсчитывать степени вершин,
полагая их до начала прохождения
нулевыми. Прохождение каждой вершины
вносит 2 в степень этой вершины. Поскольку
эйлеров цикл содержит все ребра, то
когда обход будет закончен, будут учтены
все ребра, а степени вершин – четные.

Все четыре вершины
мультиграфа, показанного на рис. 12.5,
имеют нечетные степени. Поэтому этот
граф не обладает эйлеровым циклом, а
задача о Кенигсбергских мостах не имеет
решения.

Рассмотрим для
сравнения граф, обладающий эйлеровой
цепью. В графе на рис. 12.6 только две
вершины имеют нечетную степень,
следовательно, эйлерова цепь есть.

Рис. 12.6

Цепей может быть
несколько. Например, граф на рис. 12.6
имеет две эйлеровы цепи: 1-2-3-4-1-3 и
1-2-3-1-4-3.

1. Реберный граф

Рассмотрим два
графа G
и L(G).
Граф G
имеет произвольную форму, а вершины
графа L(G)
расположены на ребрах графа G.
В этом случае граф L(G)
называется реберным
графом по
отношению к графу G.

Английское название
реберного графа – line
graph,
отсюда и обозначение графа – L(G).
На рис. 12.7 показан реберный граф (он
выделен жирными линиями), построенный
для графа с рис. 12.1.

Рис. 12.7. Реберный
граф

Теорема 12.6.
Если
– степенная последовательность (n,
m)
графа G,
то L(G)
является (m,
)-графом,
где

. (12.3)

Для графа G,
показанного на рис. 12.7 (и рис. 12.1), его
степенная последовательность: 1-3-2-3-3.
Поэтому

.

1. Раскраска графа,
   хроматический полином

Предположим, что
перед нами стоит задача: раскрасить
карту мира так, чтобы каждая страна
имела свой собственный цвет. Поскольку
на свете существует несколько сотен
государств, то, естественно, потребуется
достаточно много разных красок.

Упростим задачу.
Будем использовать меньшее количество
красок, но при этом не будем допускать,
чтобы соседние страны, имеющие общие
границы, были окрашены в один цвет.
Возникает вопрос: какое минимальное
количество красок требуется, чтобы
удовлетворить этому условию?

Ответить на этот
вопрос можно с помощью теории графов.
Для этого нужно представить карту мира
в виде графа, каждая вершина которого
соответствует отдельной стране, а ребро
между смежными вершинами соответствует
наличию между странами общей границы.

Произвольная
функция

на множестве вершин графа называется
раскраской
графа. Раскраска называется правильной,
если

для любых смежных вершин
и.
Минимальное числоk,
при котором граф G
является k-раскрашиваемым
называется хроматическим
числом
графа
.

Граф называется
пустым,
если в нем удалены все ребра и вершины
изолированы друг от друга. Граф называется
полным,
если в нем нельзя добавить новое ребро,
не добавив при этом одновременно новую
вершину.

Теорема 12.7
(Брукса).
Для любого графа G,
не являющегося полным,
,
если–максимальная
из степеней вершин графа.

Для определения
количества способов раскраски графа в
x
цветов, необходимо составить хроматический
полином
P(G,
x).
Значение полинома при некотором
конкретном
равно числу правильных раскрасок графа
вцветов.

Существует лемма,
утверждающая, что хроматический
полином графа имеет вид

,(12.4)

где
– граф, полученный изG
добавлением ребра (u,
v),
а граф
получается изG
отождествлением вершин u
и v.

Другой вариант
леммы:

, (12.5)

где
– граф, полученный изG
удалением ребра (u,
v),
а граф
получается изG
отождествлением вершин u
и v.

Операцию
отождествления вершин u
и
v
называют также стягиванием ребра (u,
v).

Оба варианта леммы
составляют основу для хроматической
редукции графа (reduction
– «сокращение» на английском).
Хроматическая редукция графа –
представление графа в виде нескольких
пустых или полных графов, сумма
хроматических полиномов которых равна
хроматическому полиному графа. Очевидно,
что хроматический полином пустого графа
равен(каждая вершина может быть раскрашена
независимо от других), а для полного
графа.
Последнее выражение называютфакториальной
степенью
переменной x:
.

Разложения по
пустым и полным графам связаны.
Факториальную степень можно представить
в виде полинома:

, (12.6)

где
– числа Стирлинга первого рода. И
наоборот, степеньможно выразить через факториальные
степени:

, (12.7)

где
– числа Стирлинга второго рода, обладающие
следующими свойствами:

при
, (12.8)

при
,при.

При получении
хроматического полинома могут быть
полезны следующие теоремы.

Теорема 12.8.
Коэффициенты хроматического полинома
составляют знакопеременную
последовательность.

Теорема 12.9.
Абсолютная величина второго коэффициента
хроматического полинома равна числу
ребер графа.

Теорема 12.10.
Наименьшее число i,
для которого отличен от нуля коэффициент
при

в хроматическом полиноме графа G,
равно числу компонент связности графа
G.

Кроме вершинной
раскраски, существует еще реберная
раскраска и раскраска граней.

Пример 12.7.
Найти хроматический полином графа,
показанного на рис. 12.8.

Рис. 12.8

Решение.
В зависимости от числа ребер графа можно
использовать разложение (12.4) или (12.5).
Если граф почти полный, то, добавив
несколько ребер по разложению (12.4),
получим хроматический полином в виде
суммы факториальных степеней. Если же
ребер мало и для получения пустого графа
требуется удалить только несколько
ребер, то следует использовать разложение
(12.5) с удалением ребер. Такие действия
называются хроматической редукцией.

1. Хроматическая
редукция по пустым графам.
Воспользуемся вначале леммой (12.5). Удаляя
ребра и отождествляя соответствующие
вершины (стягивая ребра), сведем исходный
граф к пустым графам. Сначала разложим
граф на два, убрав, а затем стянув ребро
1-3. Выполненное действие запишем в виде
условного равенства:

Здесь
операция вычитания относится не к самому
графу, а к его хроматическому полиному.
Таким образом, последнее равенство
означает, что
.
Для сокращения записи обозначениеP(…)
будем опускать. Далее разложим каждый
из графов

и
,
пользуясь той же леммой.

Приведем подобные
члены:

(12.9)

В итоге получим
искомый хроматический полином:

. (12.10)

Разложение (12.9)
называется хроматической редукцией
графа по пустым графам.

Очевидно, что
результат соответствует утверждениям
теорем 12.8-12.10. Коэффициенты в (12.10) образуют
знакопеременную последовательность,
а коэффициент при
равен четырем – числу ребер. Наименьшая
степеньx
в полиноме равна 1, т.е. числу компонент
связности графа.

2. Хроматическая
редукция по полным графам.
Добавив к изображенному на рис. 12.8 графу
ребро 1–4, получим граф с большим числом
ребер. Затем в исходном графе отождествим
вершины 1 и 4. В результате получим два
графа.

Отождествление
вершин приводит к уменьшению порядка
и иногда размера графа. Второй граф –
это полный граф
,
его преобразовывать больше не требуется.
К первому графу добавим ребро 1–2 и
отождествим вершины 1 и 2:

В итоге получим

(12.11)

Хроматический
полином примет вид

(12.12)

Разложение (12.11)
называется хроматической редукцией
графа по полным графам.

Оба способа дали
один результат, и из редукции по полным
графам легко получить редукцию по
пустым. Для этого достаточно раскрыть
скобки и привести подобные члены, как
в (12.12). Однако обратное действие не
очевидно. Для того чтобы полином
,
полученный из пустых графов, выразить
в виде суммы факториальных степеней,
необходимы числа Стирлинга 2-го рода.
Согласно рекуррентным формулам (12.8)
имеем следующие числа:

,

,

,

.

Пользуясь (12.7) и
найденными числами Стирлинга 2-го рода,
получим

,

,

.

Произведем
преобразование хроматического полинома:

Хроматическое
число
графа лучше всего получить, разложив
хроматический полином на множители:

.

Минимальное
натуральное число x,
при котором
не обращается в нуль, равно 3. Отсюда
следует.
Так как максимальная степень вершин
графа,
выполняется оценка.

1. Ранг-полином
   графа

Ранг графа
определяется как
,
гдеn
– число вершин, k
– число компонент связности графа.
Коранг графа, или цикломатический ранг,
есть
,
гдеm
– число ребер.

Ранг-полином графа
G
имеет вид

,

где
– ранг графаG
, а
– корангостовного
(т.е. включающего в себя все вершины
графа) подграфа H,
а
– его ранг. Суммирование ведется по
всем остовным подграфам графаG.

Ранг полином
служит для анализа множества остовных
подграфов. Так, например, коэффициент
при
весть число подграфов размераk,
а значение
равно числу подграфов (включая
несобственный подграф), ранг которых
равен рангу самого графа.

Пример
12.8. Найти
ранг-полином графа, изображенного на
рис. 12.8.

Решение.
Найдем все 16 остовных подграфов графа
G
(рис. 12.9). Множество представим в виде
четырех графов размера 1 (т.е. с одним
ребром), шести графов размера 2, четырех
графов размера 3 и двух несобственных
графов (пустой граф и граф G).

Рис. 12.9

Учитывая, что ранг
графа равен 3, получаем сумму:

1. Циклы

Маршрут, в котором
начало и конец совпадают, – циклический.
Циклический маршрут называется циклом,
если он – цепь.

Остовом
графа G
называется граф, не содержащий циклов
и состоящий из ребер графа G
и всех его вершин. Остов графа определяется
неоднозначно.

Ребра графа, не
входящие в остов, называются хордами.
Цикл, получающийся при добавлении к
остову графа его хорды, называется
фундаментальным
относительно
этой хорды.

Теорема 12.11.
Число ребер неографа, которые необходимо
удалить для получения остова, не зависит
от последовательности их удаления и
равно цикломатическому рангу графа.

Пример 12.8.
По заданной матрице смежности:

,

определить число
циклов длины 3 ()
и длины 4 ().
Записатьматрицу
фундаментальных циклов.

Решение.
Матрица смежности данного графа
симметричная, поэтому ей соответствует
неориентированный граф. Сумма ненулевых
элементов матрицы равна 12, следовательно,
по лемме о рукопожатиях в графе 6 ребер.
Построим этот граф (рис. 12.10). Очевидно,
в нем два цикла (3–4–5 и 1–3–5) длиной 3 и
один цикл (1–3–4–5) длиной 4. В данной
задаче решение получено прямым подсчетом
по изображению графа. Для более сложных
случаев существует алгоритм решения
задачи по матрице смежности.

Известно, что след
(trace)
матрицы смежности, возведенный в k-ю
степень, равен числу циклических
маршрутов длины k
(см. теорему 12.4). Это число включает в
себя и искомое число циклов. Цикл
отличается от циклического маршрута
тем, что в нем не повторяются ребра.
Кроме того, предполагается, что искомые
циклы не помечены, а в след матрицы
входят именно помеченные маршруты.

Рис. 12.10

Непомеченных
циклов длиной 3 в 6 раз меньше, чем
помеченных, так как каждый помеченный
цикл может отличаться началом (а их в
данном случае три) и двумя направлениями
обхода (по и против часовой стрелки).
Возведем заданную матрицу смежности в
третью степень:

,

и получим

.

Поскольку
циклических маршрутов длиной 3, отличных
от циклов длиной 3, не существует,
найденное число и есть ответ в поставленной
задаче.

С циклами длиной
4 немного сложнее. В след четвертой
степени матрицы смежности графа

,

входят не только
циклы, но и циклические маршруты с
двойным и четырехкратным прохождением
ребер. Обозначим количество таких
маршрутов через
исоответственно. Очевидно, число маршрутов
с четырехкратным прохождением одного
ребра для вершиныравно степени этой вершины:.
Число маршрутов с двукратным прохождением
ребра складывается из числас висячей вершинойи числамаршрутов с вершинойв центре.

Легко заметить,
что
.
Числозависит от степеней вершин, соседних с:

,

где
– ребро, инцидентное вершинамi
и k.

Для графа на рис.
12.10 получим

,

,

,

.

С учетом того, что
непомеченных циклов длиной 4 в 8 раз
меньше, получим

.

После преобразований
формула примет вид

.

Для нахождения
матрицы фундаментальных циклов
пронумеруем ребра графа, начиная
нумерацию с хорд, как показано на рис.
12.11 (а).

Рис. 12.11

Двум хордам, 1 и 2,
соответствуют два фундаментальных
цикла: 1–4–5 и 2–4–6 (рис. 12.11 (б и в)).
Матрица фундаментальных циклов имеет
две строки (число циклов) и шесть столбцов
(число ребер).

В первой строке
матрицы единицами отмечены столбцы с
номерами ребер, входящих в первый цикл,
а во второй строке – номера ребер из
второго цикла.

Диаметр дерева

Пусть дан граф . Тогда диаметром называется , где — кратчайшее расстояние между вершинами.

Алгоритм

• Возьмём любую вершину и найдём расстояния до всех других вершин.

• Возьмём вершину такую, что для любого . Снова найдём расстояние от до всех остальных вершин. Самое большое расстояние — диаметр дерева.

Расстояние до остальных вершин будем искать алгоритмом .

Реализация

//граф g представлен списком смежности 
int diameterTree(list<list<int>> g):        
    v = u = w = 0
    d = bfs(g, v)
    for i = 0, i < n, i++
         if d[i] > d[u]
              u = i
    d = bfs(g, u)
    for i = 0, i < n, i++
          if d[i] > d[w]
               w = i
    return d[w]

Обоснование корректности

Будем пользоваться свойством, что в любом дереве больше одного листа. Исключительный случай — дерево из одной вершины, но алгоритм сработает верно и в этом случае.

После запуска алгоритма получим дерево .

Мы свели задачу к нахождению вершины , такой что сумма глубин поддеревьев максимальна.

Докажем, что одно из искомых поддеревьев содержит самый глубокий лист.
Пусть нет, тогда, взяв расстояние от до глубочайшего листа, мы можем улучшить ответ.

Таким образом мы доказали, что нам нужно взять вершину с наибольшей глубиной после первого , очевидно, что ей в пару надо сопоставить вершину , такую что максимально. Вершину можно найти запуском из .

Оценка времени работы

Все операции кроме — .
работает за линейное время, запускаем мы его два раза. Получаем .

Центр дерева

Определения

Алгоритм

Наивный алгоритм

Найдём центр графа исходя из его определения.

• Построим матрицу ( — мощность множества ), где , то есть матрицу кратчайших путей. Для её построения можно воспользоваться алгоритмом Флойда-Уоршелла или Дейкстры.
• Подсчитаем максимум в каждой строчке матрицы . Таким образом, получим массив длины .
• Найдём наименьший элемент в этом массиве. Эта вершина и есть центр графа. В том случае, когда вершин несколько, все они являются центрами.

Асимптотика зависит от используемого способа подсчета кратчайших путей. При Флойде это будет , а при Дейкстре — максимум из асимптотики конкретной реализации Дейкстры и , за которую мы находим максимумы в матрице.

Алгоритм для дерева за O(n)

Собственно, алгоритм нахождения центра описан в доказательстве теоремы.

• Пройдёмся по дереву обходом в глубину и пометим все висячие вершины числом .
• Обрежем помеченные вершины.
• Образовавшиеся листья пометим числом и тоже обрежем.
• Будем повторять, пока на текущей глубине не окажется не более двух листьев, и при этом в дереве будет тоже не более двух листьев.

Оставшиеся листья являются центром дерева.

Для того, чтобы алгоритм работал за , нужно обрабатывать листья по одному, поддерживая в очереди два последовательных по глубине слоя.

См. также

• Дерево, эквивалентные определения
• Дополнительный, самодополнительный граф

Источники информации

• Wikipedia — Distance (graph theory)
• Ф. Харари: Теория графов
• А. Клебанов: Центры графов(нерабочая ссылка)

Hello, CodeForces!

From time to time some people ask questions related to center, radius and diameter of graph (I could google only about tree). In this topic you can find their definitions and algorithms for finding them.

Problem: you are given graph G = (V, E), where V is set of nodes and E is set of edges. You have to find its center, radius and diameter.

Let’s denote d_i, j as shortest distance between nodes . Then diameter of graph is denoted as the greatest possible among all possible shortest distances between two nodes:

Also we can define eccentricity of node as maximal distance from that node to other:

Having values of eccentricity of all nodes, we can define radius of graph as minimal one among them:

Also we can observe that diameter of graph is maximal eccentricity of node:

Center of graph is set of nodes with eccentricity equal to the radius of graph:

After these basic definitions we can find radius, diameter and center of graph using Floyd-Warshall’s algorithm:

const int   N = ...; // Number of nodes in graph
const int   INF = ...; // Infinity
int         d[N][N]; // Distances between nodes
int         e[N]; // Eccentricity of nodes
set <int>   c; // Center of graph
int         rad = INF; // Radius of graph
int         diam; // Diamater of graph

// Floyd-Warshall's algorithm
for (int k = 0; k < N; k++) {
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

// Counting values of eccentricity
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        e[i] = max(e[i], d[i][j]);
    }
}

for (int i = 0; i < n; i++) {
    rad = min(rad, e[i]);
    diam = max(diam, e[i]);
}

for (int i = 0; i < n; i++) {
    if (e[i] == rad) {
        c.insert(i);
    }
}

Now let’s try to change problem statement: suppose that G is a tree. There is one interesting fact about trees: number of nodes in the center of tree is equal to one or two.

Possible algorithm for finding center of tree is the following: using BFS from any node (denote it as v1) find the farthest from v1 node (denote as v2), then run BFS from v2, choose the farthest node from v2 (call it v3). Nodes in the middle of the path between v2 and v3 are center of graph, distance between them is diameter. Radius of graph is half of diameter rounded up: (diam(G) + 1) / 2. I will not provide implementation of that algorithm because it look quiet bulky. Instead, I will show another algorithm which is much easier to implement.

Theorem: Let L be set of leaves of G. If |V| ≤ 2 then L is center of G, otherwice center of graph remains the same after removing of L:

This theorem brings us to the following algorithm: remove leaves, level by level, until there are  ≤ 2 nodes. These nodes will be center of graph. Implementation of this algorithm is similar to BFS:

const int   N = ...; // Number of nodes in graph
int         maxlevel = 0; // Level of center of graph
int         level[N]; // Level of node
int         degree[N]; // Degree of node
int         g[N][N]; // Adjacency matrix
set <int>   c; // Center of graph
queue <int> q; // Queue for algo

// Start from leaves
for (int i = 0; i < N; i++) {
    if (degree[i] == 1) {
        q.push(i);
    }
}

while (!q.empty()) {
    int v = q.front();
    q.pop();

    // Remove leaf and try to add its parent
    for (int i = 0; i < N; i++) {
        if (g[v][i]) {
            degree[i]--;
            
            if (degree[i] == 1) {
                q.push(i);
                level[i] = level[v] + 1;
                maxlevel = max(maxlevel, level[i]);
            }
        }
    }
}

for (int i = 0; i < N; i++) {
    if (level[i] == maxlevel) {
        c.insert(i);
    }
}

It’s not so hard to prove that after running of this algo center of graph will be in c, и rad(G) = (diam(G) + 1) / 2.

I could not fin appropriate problems to solve, feel free to post them in comments.

Problems to solve:

• IOI2013 Dreaming
• 456E — Civilization
• 592D — Super M
• Problem F from this contest

Thank you for attention, you can write about typos to private messages.

Связность и компоненты

Граф называется связным, если
в нем для любых двух вершин имеется
маршрут, соединяющий эти вершины. Заметим, что ввиду теоремы 1 можно
в этом определении заменить слово «маршрут» словами «простой
путь«.

Для произвольного графа определим на множестве вершин отношение
соединимости: вершина соединима с вершиной ,
если существует соединяющий их маршрут.
Легко видеть, что это отношение
рефлексивно, симметрично и транзитивно, то есть является отношением
эквивалентности. Классы эквивалентности называются областями
связности, а порождаемые ими подграфы — компонентами связности
графа. В связном графе имеется только одна компонента связности —
весь граф. Компоненты связности можно определить также
как максимальные по включению связные подграфы данного графа.

У графа на рис. 2.2 имеется
четыре области
связности — , , , .

Вершина называется шарниром
(или точкой
сочленения ), если при
ее удалении число компонент связности увеличивается. У графа
на рис. 2.2 имеется четыре шарнира — это вершины , , , .

Ребро, при удалении которого увеличивается число компонент связности,
называется перешейком.
Перешейками графа, изображенного
на рис. 2.2, являются ребра , , , , .

Легко доказываются следующие свойства шарниров и перешейков:

Метрические характеристики графов

Расстоянием между двумя
вершинами графа называется наименьшая длина
пути, соединяющего эти вершины. Расстояние между вершинами
и обозначается через . Если в
графе нет пути,
соединяющего и , то есть эти вершины принадлежат
разным
компонентам связности, то расстояние между ними считается бесконечным.

Функция обладает следующими свойствами:

1. , причем тогда
   и только тогда, когда ;
2. ;
3. 
   (неравенство треугольника).

В математике функцию двух переменных, определенную на некотором множестве
и удовлетворяющую условиям 1 — 3, называют метрикой, а множество, на
котором задана метрика, — метрическим пространством. Таким образом,
множество вершин любого графа можно рассматривать как метрическое
пространство.

Расстояние от данной вершины до наиболее удаленной от нее
вершины
называется эксцентриситетом вершины и обозначается
через . Таким образом,

Вершину с наименьшим эксцентриситетом называют центральной,
а вершину с наибольшим эксцентриситетом — периферийной.
Множество всех центральных вершин называется центром графа.
Сама величина наименьшего эксцентриситета
называется радиусом графа и
обозначается
через , а величина наибольшего — диаметром
и обозначается . Иначе говоря,

Наименьший диаметр имеет полный граф — его диаметр равен 1. Среди
связных
графов с вершинами наибольший диаметр, равный ,
имеет
цепь .

Если расстояние между двумя вершинами равно диаметру графа, то кратчайший
путь, соединяющий эти вершины, называется диаметральным путем,
а подграф, образованный вершинами и ребрами этого пути, — диаметральной
цепью.

Для графа, изображенного на рис. 2.3, эксцентриситеты вершин приведены в следующей таблице:

Центр этого графа составляют вершины , , ;
периферийные вершины — , и ;
радиус его
равен , а диаметр . Одна из диаметральных цепей
порождается множеством вершин .