Радиус и диаметр графа: как считать эксцентриситет

Радиус и диаметр графа - это две числовые характеристики, которые описывают, насколько граф «растянут»: как далеко в худшем случае отстоят друг от друга вершины и насколько компактно его можно охватить из удачно выбранного центра. Эти величины встречаются и в курсе дискретной математики, и в анализе сетей - от компьютерных топологий до социальных графов. Разберём, как они определяются через эксцентриситет, чем отличаются и как посчитать их вручную на конкретном примере.

Расстояние в графе

Всё строится на понятии расстояния. Расстояние $d(u, v)$ между вершинами $u$ и $v$ - это длина кратчайшего пути между ними. В невзвешенном графе длина пути равна числу рёбер на нём, поэтому соседние вершины находятся на расстоянии $1$, а вершина сама от себя - на расстоянии $0$.

Расстояние симметрично для неориентированного графа: $d(u, v) = d(v, u)$. Если из $u$ в $v$ вообще нельзя дойти (граф несвязен), то $d(u, v) = \infty$. Это важная оговорка: радиус и диаметр определены только для связного графа, иначе они обращаются в бесконечность.

Эксцентриситет вершины

Чтобы перейти к радиусу и диаметру, сначала введём характеристику отдельной вершины. Эксцентриситет вершины $v$ - это расстояние до самой далёкой от неё вершины:

$\varepsilon(v) = \max_{u \in V} d(v, u).$

Иными словами, мы стоим в вершине $v$ и смотрим, до какой вершины графа добираться дольше всего. Это число и есть эксцентриситет. Вершина с маленьким эксцентриситетом «удобно расположена» - она близка ко всем остальным; вершина с большим эксцентриситетом, наоборот, торчит на краю.

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

Определение радиуса и диаметра

Когда эксцентриситеты всех вершин посчитаны, радиус и диаметр получаются почти автоматически.

Радиус графа - это наименьший из эксцентриситетов:

$r(G) = \min_{v \in V} \varepsilon(v).$

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

$\operatorname{diam}(G) = \max_{v \in V} \varepsilon(v) = \max_{u, v \in V} d(u, v).$

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

Связь радиуса и диаметра

Радиус и диаметр не независимы. Для любого связного графа выполняется двойное неравенство:

$r(G) \le \operatorname{diam}(G) \le 2\,r(G).$

Левая часть очевидна: минимум по эксцентриситетам не превосходит максимума. Правая часть менее очевидна, но доказывается через неравенство треугольника. Возьмём центральную вершину $c$ с $\varepsilon(c) = r(G)$ и любые две вершины $u, v$. Тогда

$d(u, v) \le d(u, c) + d(c, v) \le r(G) + r(G) = 2\,r(G).$

Поскольку это верно для любой пары, максимум расстояний - то есть диаметр - тоже не превосходит $2r(G)$. Эта оценка точная: например, у простой цепи (пути) диаметр ровно вдвое больше радиуса, а у полного графа радиус и диаметр совпадают и равны $1$.

Центр и периферия графа

Эксцентриситет естественно делит вершины на два особых множества.

Центр графа - множество вершин с минимальным эксцентриситетом, то есть тех, у кого $\varepsilon(v) = r(G)$. Это «самые удобные» точки: из них до любой другой вершины не дальше радиуса. У дерева центр состоит из одной или двух вершин - это классический результат, удобный для проверки.

Периферия - вершины с максимальным эксцентриситетом, $\varepsilon(v) = \operatorname{diam}(G)$. Это самые «окраинные» вершины; концы диаметрального пути всегда лежат в периферии.

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

Как считать на практике

Алгоритм прямолинеен и опирается на матрицу кратчайших расстояний.

1. Для каждой вершины запускаем обход в ширину (BFS) - он за один проход даёт расстояния $d(v, u)$ до всех остальных вершин в невзвешенном графе.
2. По строке матрицы для вершины $v$ берём максимум - это $\varepsilon(v)$.
3. Минимум по всем эксцентриситетам даёт радиус, максимум - диаметр.
4. Вершины, на которых достигается минимум, образуют центр; на которых максимум - периферию.

Для взвешенного графа BFS заменяется на алгоритм Дейкстры, а для случая с произвольными весами используют алгоритм Дейкстры на взвешенном графе из каждой вершины. Если граф плотный, вместо $n$ запусков BFS иногда удобнее посчитать все попарные расстояния алгоритмом Флойда - Уоршелла за $O(n^3)$.

Сложность всей процедуры через BFS - $O(n \cdot (n + m))$, где $n$ - число вершин, $m$ - число рёбер. Это вполне приемлемо для учебных задач и графов средних размеров. Для очень больших сетей точное вычисление диаметра дорого, и тогда переходят к приближённым оценкам: например, делают несколько BFS из случайно выбранных вершин и берут максимум найденных расстояний как нижнюю границу диаметра.

Псевдокод вычисления

Базовый алгоритм через матрицу расстояний выглядит так:

для каждой вершины v:
    dist[v] = BFS(v)              # расстояния от v до всех вершин
    ecc[v]  = max(dist[v])        # эксцентриситет v

radius   = min(ecc)
diameter = max(ecc)
center   = { v : ecc[v] == radius }
periphery = { v : ecc[v] == diameter }

Здесь BFS(v) возвращает массив расстояний от $v$; если в нём остался $\infty$ (какая-то вершина недостижима), граф несвязен и метрики не определены конечным числом. Этот же каркас лежит в основе инструмента выше - он просит модель построить матрицу расстояний и вывести все промежуточные величины, чтобы решение можно было проверить руками.

Пример вручную

Возьмём граф-путь из пяти вершин $A - B - C - D - E$. Матрица расстояний даёт эксцентриситеты: $\varepsilon(A) = \varepsilon(E) = 4$ (от конца до конца четыре ребра), $\varepsilon(B) = \varepsilon(D) = 3$, а $\varepsilon(C) = 2$.

Тогда радиус $r = \min = 2$, диаметр $\operatorname{diam} = \max = 4$. Центр - единственная вершина $C$, периферия - концы $A$ и $E$. Заметьте, неравенство $\operatorname{diam} \le 2r$ обращается здесь в равенство: $4 = 2 \cdot 2$.

Частые ошибки

• Считают эксцентриситет как сумму расстояний до всех вершин, а не максимум. Эксцентриситет - это именно $\max$, сумма дала бы другую характеристику (близость).
• Забывают, что для несвязного графа радиус и диаметр равны $\infty$, и пытаются вернуть конечное число по одной компоненте.
• Путают радиус с «половиной диаметра». Неравенство $\operatorname{diam} \le 2r$ верно, но равенство $r = \operatorname{diam}/2$ выполняется не всегда.
• В ориентированном графе берут $d(u, v)$ симметрично. Для орграфа расстояние несимметрично, и эксцентриситет считают по исходящим путям.
• Включают в центр все вершины «примерно посередине». В центр входят только те, у кого эксцентриситет в точности равен радиусу.

FAQ

Может ли радиус равняться диаметру? Да. У полного графа $K_n$ все эксцентриситеты равны $1$, поэтому $r = \operatorname{diam} = 1$. В общем случае равенство означает, что у графа нет «удобной» центральной вершины - все одинаково удалены от периферии.

Чем эксцентриситет отличается от степени вершины? Степень - это число рёбер, инцидентных вершине (локальная величина). Эксцентриситет - расстояние до самой далёкой вершины (глобальная). Вершина высокой степени может иметь большой эксцентриситет и наоборот.

Как радиус и диаметр меняются при добавлении ребра? Добавление ребра не может увеличить расстояния, поэтому радиус и диаметр либо уменьшаются, либо остаются прежними. Это монотонное свойство удобно использовать для проверки решений.

Коротко

Радиус и диаметр графа выражаются через эксцентриситет вершины - максимум расстояния до остальных. Радиус $r(G) = \min_v \varepsilon(v)$, диаметр $\operatorname{diam}(G) = \max_v \varepsilon(v)$, и всегда $r \le \operatorname{diam} \le 2r$. Вершины минимального эксцентриситета образуют центр, максимального - периферию. На практике всё считается из одной матрицы кратчайших расстояний, построенной обходами в ширину из каждой вершины.