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

Связать^?

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

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

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

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

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

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

Пусть $X_p$ — подмножество множества вершин X графа $G = (X, \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$.

Если $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.

Литература

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

Ссылки

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

Для улучшения этой статьи желательно?: Исправить статью согласно стилистическим правилам Википедии. Проставить интервики в рамках проекта Интервики.