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

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

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

Задача о p-медианеПравить

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

p-медиана графаПравить

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

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

$d(X_p,x_j)=min[d(x_i,x_j)]$$d(X_{p},x_{j})=min[d(x_{i},x_{j})]$ 

$d(x_j,X_p)=min[d(x_j,x_i)]$$d(x_{j},X_{p})=min[d(x_{j},x_{i})]$ , где минимум ищется по всем $x_i\in <!--\; \in \; -->X_P$$x_{i}\in X_{P}$ .

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

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

${\mathrm{\sigma <!--\; \sigma \; -->}}_o(x_i)=\sum <!--\; \sum \; -->v_{j}d(X_p,x_j)$$\sigma _{o}(x_{i})=\sum v_{j}d(X_{p},x_{j})$  — внешнее передаточное число,

${\mathrm{\sigma <!--\; \sigma \; -->}}_t(x_i)=\sum <!--\; \sum \; -->v_{j}d(x_j,X_p)$$\sigma _{t}(x_{i})=\sum v_{j}d(x_{j},X_{p})$  — внутреннее передаточное число.

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

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

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

ЛитератураПравить

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

СсылкиПравить

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