Центр графика - Graph center

График с центральными точками красного цвета. Эти три вершины  таким образом, что d ( ,  B ) ≤ 3 для всех вершин  B . Каждая черная вершина находится на расстоянии не менее 4 от другой вершины.

Центр (или Джордан в центре) из графа является множеством всех вершин минимального эксцентриситета , то есть множество всех вершин U , где наибольшее расстояние d ( U , V ) с другими вершинами v является минимальным. Эквивалентно, это набор вершин с эксцентриситетом, равным радиусу графа . Таким образом, вершины в центре ( центральные точки ) минимизируют максимальное расстояние от других точек на графике.

Это также известно как проблема вершинного 1-центра и может быть расширена до вершинной проблемы k-центра .

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

Центр можно найти с помощью алгоритма Флойда – Уоршалла . Предложен другой алгоритм, основанный на матричном исчислении.

Концепция центра графа связана с мерой центральности близости в анализе социальных сетей , которая является обратной величиной среднего расстояния d ( A , B ).

использованная литература

  1. ^ a b Вассерман, Стэнли и Фауст, Кэтрин (1994), Анализ социальных сетей: методы и приложения , стр. 185. Кембридж: Издательство Кембриджского университета. ISBN  0-521-38269-6
  2. ^ Мак, Джеймс А., алгоритмическая Теория графы архивация 2010-08-01 в Wayback Machine
  3. ^ Вайсштейн, Эрик В. "Графический центр" . MathWorld .
  4. ^ Флойд, Роберт В. (июнь 1962 г.). «Алгоритм 97: кратчайший путь». Коммуникации ACM. 5 (6): 345 https://doi.org/10.1145/367766.368168
  5. ^ Воршалл, Стивен (январь 1962). «Теорема о булевых матрицах». Журнал ACM. 9 (1): 11–12 https://doi.org/10.1145/321105.321107
  6. ^ «Новый алгоритм вычисления центра графа и разбиения графа в зависимости от расстояния до центра» . Октябрь 2019.