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

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

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

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

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

'''Задача конструирования сети с повышенной живучестью'''

Для заданного набора S точек в R и функции требования связности r:SxS^-N найти геометрическую сеть минимальной стоимости, охватывающую точки из S, такую, что для любой пары вершин p, q 2 S подсеть имеет грл внутренних вершинно-непересекающихся (или реберно-непересекащихся, соответственно) путей между p и q.

Во многих приложениях этой задачи, нередко считающихся наиболее интересными [9, 13], функция требования связности определяется при помощи функции от одного аргумента, присваивающей каждой вершине p ее тип связности rv 2 N. Тогда для любой пары вершин p, q 2 S требование связности Грл задается просто в виде minfrp; rqg [12, 13, 17, 18]. Этот список включает задачу о вычислении дерева Штейнера, (см., например, [ ]), в которой rp 2 f0; 1g для любой вершины p2S.

Схема аппроксимации с полиномиальным временем исполнения (PTAS) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и дает (1 + ")-аппроксимацию.