Минимальные k-связные геометрические сети

Ключевые слова и синонимы

Геометрические графы; евклидовы графы

Постановка задачи

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

Нотация

Пусть G = (V, E) – геометрическая сеть, множество вершин V которой соответствует множеству из n точек в [math]\displaystyle{ \mathbb{R}^d \; }[/math] для определенного целого числа [math]\displaystyle{ d \ge 2 \; }[/math], а множество ребер E – множеству прямолинейных сегментов, соединяющих пары точек из V. Сеть G называется полной, если E соединяет все пары точек из V.

Стоимость [math]\displaystyle{ \delta(x, y) \; }[/math] дуги, соединяющей пару точек [math]\displaystyle{ x, y \in \mathbb{R}^d \; }[/math], равна евклидовому расстоянию между точками x и y. Иначе говоря, [math]\displaystyle{ \delta(x, y) = \sqrt{ \sum^d_{i=1} (x_i - y_i)^2} }[/math], где [math]\displaystyle{ x = (x_1, ..., x_d) \; }[/math] и [math]\displaystyle{ y = (y_1, ..., y_d) \; }[/math]. В более общем виде стоимость можно определить с использованием других норм – таких как lp-нормы для любого p > 1, т.е. [math]\displaystyle{ \delta(x, y) = ( \sum_{i=1}^p (x_i - y_i)^p)^{1/p} \; }[/math]. Стоимость сети представляет собой сумму стоимостей всех ребер сети: [math]\displaystyle{ cost(G) = \sum_{x, y \in e} \delta(x, y) \; }[/math].

Сеть G = (V, E) служит остовом множества точек S, если V = S. Сеть G является k-вершинно-связной, если для любого множества [math]\displaystyle{ U \subseteq \; }[/math], состоящего из менее чем k вершин, сеть [math]\displaystyle{ (V \backslash U; E \cap ((V \backslash U) \times (V \backslash U)) }[/math] является связной. Подобным же образом G является k-реберно-связной, если [math]\displaystyle{ \mathcal{E} \subseteq E \; }[/math] с количеством ребер менее k сеть [math]\displaystyle{ (V, E \backslash \mathcal{E}) \; }[/math] является связной.

(Евклидова) задача нахождения k-вершинно-связной остовной сети минимальной стоимости

Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] найти k-вершинно-связную сеть минимальной стоимости, охватывающую все точки S.

(Евклидова) задача нахождения k-реберно-связной остовной сети минимальной стоимости

Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую все точки S. Рассматривается также вариант, допускающий наличие параллельных ребер:

(Евклидова) задача нахождения k-реберно-связной остовной мультисети минимальной стоимости

Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую точки S (в случае мультисети она может содержать параллельные ребра).

Понятие k-связности с минимальной стоимостью естественным образом расширяется на k-связность евклидова дерева Штейнера, если разрешить использование дополнительных вершин, называемых точками Штейнера. Для заданного набора точек S в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] геометрическая сеть G представляет собой k-вершинно-связную (или k-реберно-связную) сеть Штейнера для S, если множество вершин G является надмножеством S и для каждой пары точек из S существует k внутренних вершинно-непересекающихся (реберно-непересекащихся, соответственно) путей, соединяющих их в G.

(Евклидова) задача нахождения k-вершинно(реберно)-связной сети Штейнера минимальной стоимости

Найти сеть минимальной стоимости на надмножестве S, являющуюся k-вершинно(реберно)-связной сетью Штейнера для S.

Заметим, что при k = 1 эта задача представляет собой просто задачу построения минимального дерева Штейнера, которой посвящено множество работ (см., например, [14]).

В более общей формулировке задач о многосвязности в графах следует учитывать ограничения неоднородной связности.