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

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

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


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


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


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

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


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

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


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

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


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


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

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


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


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