ЕГЭОГЭЕНТ
РУҚА
Задание № 13 · ЕГЭ

Центр графа

Вершины графа, равноудалённые от остальных ближе всего
2 мин чтенияСложность: Обновлено 29 сентября 2026

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

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

Формула

Пусть \(d(v,u)\) — расстояние между вершинами \(v\) и \(u\). Эксцентриситет вершины \(v\) обозначают \(e(v)\).

\[e(v)=\max_{u\in V} d(v,u)\]

Если \(r\) — наименьший эксцентриситет среди всех вершин, то центр графа состоит из всех вершин, для которых \(e(v)=r\):

\[C(G)=\{v\in V\mid e(v)=r\},\qquad r=\min_{v\in V} e(v)\]
№
Пример

Пусть для четырёх вершин получились эксцентриситеты: \(e(A)=4\), \(e(B)=3\), \(e(C)=3\), \(e(D)=5\). Минимальное значение равно \(3\), поэтому центр графа — вершины B и C. Центр может состоять не из одной вершины.

!
Не путайте с диаметром

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

  1. Для каждой вершины просмотрите её строку или столбец в таблице расстояний.
  2. Запишите максимальное расстояние в этой строке — это эксцентриситет вершины.
  3. Найдите наименьшее из записанных значений.
  4. Выберите все вершины, у которых эксцентриситет равен этому минимуму.
Проверьте себя

Эксцентриситеты вершин равны: \(e(A)=2\), \(e(B)=4\), \(e(C)=2\), \(e(D)=3\). Каков центр графа?

Главное за минуту

Главное

  • Эксцентриситет вершины — максимальное расстояние от неё до остальных вершин.
  • Центр графа состоит из всех вершин с минимальным эксцентриситетом.
  • Для поиска центра достаточно найти максимумы в строках таблицы расстояний и выбрать наименьшие из них.