Центр графа
Центр ( или Иорданский центр [1] ) графа — это множество всех вершин минимального эксцентриситета , [2] то есть набор всех вершин u , где наибольшее расстояние d ( u , v ) до других вершин v минимально. графа Эквивалентно, это набор вершин с эксцентриситетом, равным радиусу . [3] Таким образом, вершины в центре ( центральные точки ) минимизируют максимальное расстояние от других точек графа.
Это также известно как проблема вершинного 1-центра и может быть расширено до проблемы вершинного k-центра .
Поиск центра графа полезен в задачах размещения объектов , где цель состоит в том, чтобы минимизировать расстояние до объекта в наихудшем случае. Например, размещение больницы в центральной точке сокращает максимальное расстояние, которое должна преодолеть машина скорой помощи.
Центр можно найти с помощью алгоритма Флойда–Уоршалла . [4] [5] Был предложен другой алгоритм, основанный на матричном исчислении. [6]
Понятие центра графа связано с мерой центральности близости в анализе социальных сетей , которая является обратной величиной среднего значения расстояний d ( A , B ). [1]
Ссылки
[ редактировать ]- ^ Jump up to: а б Вассерман, Стэнли , и Фауст, Кэтрин (1994), Анализ социальных сетей: методы и приложения , стр. 185. Кембридж: Издательство Кембриджского университета. ISBN 0-521-38269-6
- ^ Макхью, Джеймс А., Теория алгоритмических графов. Архивировано 1 августа 2010 г. в Wayback Machine.
- ^ Вайсштейн, Эрик В. «Графический центр» . Математический мир .
- ^ Флойд, Роберт В. (июнь 1962 г.). «Алгоритм 97: Кратчайший путь». Коммуникации АКМ. 5 (6): 345 https://doi.org/10.1145/367766.368168
- ^ Уоршалл, Стивен (январь 1962 г.). «Теорема о булевых матрицах». Журнал АКМ. 9 (1): 11–12 https://doi.org/10.1145/321105.321107
- ^ «Новый алгоритм вычисления центра графа и разбиения графа по расстоянию до центра» . Октябрь 2019.