Эксцентриситет вершины графа: определение и расчёт

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

Что такое эксцентриситет вершины

Эксцентриситет вершины $v$ в связном графе $G = (V, E)$ - это наибольшее из расстояний от $v$ до всех остальных вершин:

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

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

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

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

Как посчитать эксцентриситет вручную

Расчёт опирается на расстояния, поэтому порядок действий такой.

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

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

Обратите внимание: при движении от центра к краю пути эксцентриситет растёт ровно на единицу за шаг - это прямое следствие свойства смежных вершин, о котором ниже. Если в ваших вычислениях соседние вершины отличаются по $\varepsilon$ больше чем на $1$, где-то закралась ошибка в расстояниях.

Эксцентриситет через матрицу расстояний

Когда нужны эксцентриситеты всех вершин сразу, удобнее построить матрицу кратчайших расстояний $D$, где элемент $D_{ij} = d(v_i, v_j)$. Тогда эксцентриситет вершины - это максимум по её строке:

$\varepsilon(v_i) = \max_j D_{ij}.$

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

Свойства эксцентриситета

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

• Эксцентриситет всегда конечен в связном графе и равен $\infty$, если из вершины недостижима хотя бы одна другая (граф несвязен).
• Соседние вершины отличаются по эксцентриситету не больше чем на $1$: $|\varepsilon(u) - \varepsilon(v)| \le 1$ для смежных $u$ и $v$. Это следствие неравенства треугольника и удобный тест на ошибку.
• Минимум и максимум эксцентриситетов по всем вершинам дают, соответственно, радиус $r(G) = \min_v \varepsilon(v)$ и диаметр $\operatorname{diam}(G) = \max_v \varepsilon(v)$.
• Связь с диаметром: для любой вершины $\varepsilon(v) \ge \operatorname{diam}(G) / 2$, поскольку любые две вершины удалены не более чем на сумму их расстояний до $v$.

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

Центр и периферия через эксцентриситет

Эксцентриситет естественно делит вершины на особые группы.

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

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

Вершины с промежуточными эксцентриситетами не относят ни к центру, ни к периферии - границы строго привязаны к радиусу и диаметру.

Эксцентриситет в ориентированном графе

В орграфе расстояние несимметрично: $d(u, v)$ и $d(v, u)$ могут различаться или одно из них быть бесконечным. Поэтому различают два варианта эксцентриситета:

$\varepsilon^{+}(v) = \max_{u} d(v, u), \qquad \varepsilon^{-}(v) = \max_{u} d(u, v).$

Первый ($\varepsilon^{+}$, исходящий) измеряет, насколько далеко можно уйти из $v$; второй ($\varepsilon^{-}$, входящий) - насколько далеко находится самая удалённая вершина, из которой можно добраться в $v$. В сильно связном орграфе оба конечны, но в общем случае нужно явно указывать, какое направление вы считаете.

Эксцентриситет и центральность в сетях

В анализе социальных и инженерных сетей на основе эксцентриситета строят меру центральности по близости в наихудшем случае - eccentricity centrality:

$C_E(v) = \frac{1}{\varepsilon(v)}.$

Чем меньше эксцентриситет, тем выше эта центральность: вершина с малым $\varepsilon(v)$ гарантирует короткую дистанцию до любого узла. В отличие от степени вершины (число соседей) или центральности по близости (сумма расстояний), эксцентриситет учитывает именно худший случай - это важно, когда критична максимальная задержка, а не средняя. Например, при выборе узла для кэш-сервера или координатора в распределённой системе минимизируют именно эксцентриситет: так гарантируется верхняя граница на отклик для любого клиента сети.

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

• Считают эксцентриситет как сумму расстояний до всех вершин. Это другая метрика (близость); эксцентриситет - именно $\max$, а не сумма.
• Берут расстояние «по прямой» или число рёбер на произвольном пути вместо кратчайшего. В определении $d(v, u)$ - длина именно кратчайшего пути.
• Для несвязного графа возвращают конечное число, посчитав максимум только по достижимым вершинам. Если есть недостижимая вершина, $\varepsilon(v) = \infty$.
• В орграфе считают $d(u, v) = d(v, u)$. Расстояние там несимметрично, нужно фиксировать направление ($\varepsilon^{+}$ или $\varepsilon^{-}$).
• Путают вершину с минимальным эксцентриситетом и вершину с максимальной степенью. Высокая степень не гарантирует малый эксцентриситет.

FAQ

Чему равен эксцентриситет в полном графе? В полном графе $K_n$ любые две вершины соседние, поэтому расстояние между ними равно $1$, и эксцентриситет каждой вершины тоже равен $1$. Радиус и диаметр такого графа совпадают и равны $1$.

Может ли эксцентриситет быть равен нулю? Только в тривиальном графе из одной вершины: тогда единственное расстояние - это $d(v, v) = 0$, и максимум равен $0$. В любом графе с двумя и более вершинами эксцентриситет не меньше $1$.

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

Коротко

Эксцентриситет вершины $v$ - это максимум расстояний от неё до остальных вершин: $\varepsilon(v) = \max_{u} d(v, u)$. Считают его построчным максимумом матрицы кратчайших расстояний, которую строят через BFS, Дейкстру или Флойда - Уоршелла. Минимум эксцентриситетов даёт радиус, максимум - диаметр; вершины минимального эксцентриситета образуют центр, максимального - периферию. В орграфе различают входящий и исходящий эксцентриситет, а в анализе сетей на нём строят меру центральности $C_E(v) = 1/\varepsilon(v)$.