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

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

В центр (или Иордания центр[1]) из график - множество всех вершин минимума эксцентриситет,[2] то есть множество всех вершин ты где наибольшее расстояние d(ты,v) в другие вершины v минимально. Эквивалентно, это множество вершин с эксцентриситетом, равным графу радиус.[3] Таким образом, вершины в центре (центральные точки) минимизировать максимальное расстояние от других точек графика.

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

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

Центр можно найти с помощью Алгоритм Флойда-Уоршолла.[4][5] Предложен другой алгоритм, основанный на матричном исчислении.[6]

Понятие центра графа связано с центральность близости измерять в анализ социальных сетей, которая обратна среднему значению расстояний d(А,B).[1]

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

  1. ^ а б Вассерман, Стэнли, и Фауст, Кэтрин (1994), Анализ социальных сетей: методы и приложения, стр. 185. Кембридж: Издательство Кембриджского университета. ISBN  0-521-38269-6
  2. ^ МакХью, Джеймс А., Алгоритмическая теория графов В архиве 01.08.2010 в 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. ^ https://hal.archives-ouvertes.fr/hal-02304090