Обобщения

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

1. Разбиение множества вершин или дуг на подмножества.

2. Решение задачи размещения для каждого подмножества.

Методы, применяемые для решения этих задач весьма сложны, однако стоит отметить результат, относящийся к нахождению абсолютной p-медианы. Предположим, мы ищем такое размещение p абсолютных медиан, что каждая вершина приписана к ближайшей медиане и суммарное расстояние от каждой вершины до ближайшей к ней медиане минимально.

Теорема 2.

Существует абсолютная p-медиана, которая состоит только из вершин графа.

Доказательство.

Поскольку расстояние точка-вершина является вогнутой функцией, и любая сумма вогнутых функций тоже вогнута, то p-медианой являются p вершин.

В общем случае задачи о p-медиане и p-центре являются NP – полными. Приведем точные формулировки этих задач.

ЗАДАЧА О P-МЕДИАНЕ

УСЛОВИЕ. Заданы граф G=<V, E>, целый неотрицательный вес w(v) каждой вершины vV, целая неотрицательная длина A(e) каждого ребра eE, положительное целое число K|V| и положительное рациональное число B.

ВОПРОС. Существует ли такое множество P мощности K , состоящее из точек на G (точкой на G называется либо вершина графа G, либо точка на ребре eE, где e рассматривается как прямолинейный отрезок длины A(e)), что если D(v) – длина кратчайшего пути от вершины v до ближайшей к ней точке из P, то

D(v)  w(v)B?

vV

Комментарий. При PV (выборе медианы среди вершин) задача остается NP-полной. Если граф G – дерево, или K – фиксировано, то задача разрешима за полиномиальное время.

Задача о p-центре

УСЛОВИЕ. Заданы граф G=<V, E>, целый неотрицательный вес w(v) каждой вершины vV, целая неотрицательная длина A(e) каждого ребра eE, положительное целое число K|V| и положительное рациональное число B.

ВОПРОС. Существует ли такое множество P мощности K , состоящее из точек на G (точкой на G называется либо вершина графа G, либо точка на ребре eE, где e рассматривается как прямолинейный отрезок длины A(e)), что если D(v) – длина кратчайшего пути от вершины v до ближайшей к ней точке из P, то

Max{D(v)  w(v)}B?

vV

Комментарий. При PV (выборе центра среди вершин) задача остается NP-полной. Если граф G – дерево, или K – фиксировано, то задача разрешима за полиномиальное время.