Медиана графа

Медиана — вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная.

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

Задача о нахождении p-медианы данного графа ${\displaystyle G}$ — это задача о размещении заданного числа (скажем, p) пунктов обслуживания, при которых сумма кратчайших расстояний от вершин графа ${\displaystyle G}$ до ближайших пунктов принимает минимально возможное значение.

Обобщим понятие медианы, определив p-медиану.

Пусть ${\displaystyle X_{p}}$ — подмножество множества вершин X ориентированного графа ${\displaystyle G=(X,\Gamma )}$, и положим, что ${\displaystyle X_{p}}$ содержит p вершин. Переопределим следующие обозначения:

${\displaystyle d(X_{p},x_{j})=min[d(x_{i},x_{j})]}$

${\displaystyle d(x_{j},X_{p})=min[d(x_{j},x_{i})]}$, где минимум ищется по всем ${\displaystyle x_{i}\in X_{P}}$.

Если ${\displaystyle x_{i}^{1}}$ — вершина из ${\displaystyle X_{p}}$, на которой достигается минимум в предыдущих формулах, то говорят, что вершина ${\displaystyle x_{j}}$ прикреплена ${\displaystyle x_{i}^{1}}$.

Передаточные же числа множества вершин ${\displaystyle X_{p}}$ определяются аналогично передаточным числам одиночной вершины:

${\displaystyle \sigma _{o}(x_{i})=\sum v_{j}d(X_{p},x_{j})}$ — внешнее передаточное число,

${\displaystyle \sigma _{t}(x_{i})=\sum v_{j}d(x_{j},X_{p})}$ — внутреннее передаточное число.

Множество же ${\displaystyle X_{o}^{*}}$, для которого ${\displaystyle \sigma _{o}(X_{o}^{*})=min[\sigma _{o}(x_{i})]}$ (минимум ищется по всем ${\displaystyle X_{p}\subseteq X)}$, называется внешней p-медианой графа ${\displaystyle G}$, аналогично определяется внутренняя p-медиана.

Для упрощения задачи будем далее рассматривать неориентированный граф G. Тогда индексы «t» и «o» будут отсутствовать, так как внешние и внутренние передаточные числа будут совпадать. Точку графа (вершина или точка дуги), для которой передаточное число будет принимать наименьшее значение, будем называть абсолютной медианой графа G.

• Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
• Э. Майника. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 1981. — 324 с.

• Приближенный алгоритм поиска p-медиан
• Размещение медиан