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

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

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

Задача о p-медиане

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

p-медиана графа

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

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

$d(X_p,x_j)=min[d(x_i,x_j)]$

$d(x_j,X_p)=min[d(x_j,x_i)]$, где минимум ищется по всем $x_i\in X_P$.

Если $x_i^1$ — вершина из $X_p$, на которой достигается минимум в предыдущих формулах, то говорят, что вершина $x_j$ прикреплена $x_i^1$.

Передаточные же числа множества вершин $X_p$ определяются аналогично передаточным числам одиночной вершины:

${\sigma }_o(x_i)=\sum v_{j}d(X_p,x_j)$ — внешнее передаточное число,

${\sigma }_t(x_i)=\sum v_{j}d(x_j,X_p)$ — внутреннее передаточное число.

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

Абсолютная p-медиана

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

Литература

• Шаблон:Книга
• Шаблон:Книга

Ссылки

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