Центр (или центр Жордана [1] ) графа — это множество всех вершин с минимальным эксцентриситетом , [2] то есть множество всех вершин u , где наибольшее расстояние d ( u , v ) до других вершин v минимально. Эквивалентно, это множество вершин с эксцентриситетом, равным радиусу графа . [3] Таким образом, вершины в центре ( центральные точки ) минимизируют максимальное расстояние от других точек графа.
Это также известно как проблема вершины 1-центра и может быть расширено до проблемы вершины k-центра .
Поиск центра графика полезен в задачах размещения объектов , где цель состоит в минимизации наихудшего расстояния до объекта. Например, размещение больницы в центральной точке сокращает самое длинное расстояние, которое должна преодолеть машина скорой помощи.
Центр можно найти с помощью алгоритма Флойда–Уоршелла . [4] [5] Был предложен другой алгоритм, основанный на матричном исчислении. [6]
Понятие центра графа связано с мерой центральности близости в анализе социальных сетей , которая является обратной величиной среднего значения расстояний d ( A , B ). [1]