Центр графа

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

Центр (или центр Жордана) графа — это множество всех вершин с минимальным эксцентриситетом. То есть множество всех вершин A, для которой максимальное расстояние d(A,B) до других вершин B минимально. Эквивалентно, это множество вершин с эксцентриситетом, равным радиусу графа.

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

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

Литература

• Stanley Wasserman, Katherine Faust. . Social Network Analysis: Methods and Applications. — Cambridge: Cambridge University Press, 1994. — ISBN 0-521-38269-6. — P. 185.