4551
правка
Лес Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Родственные задачи
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Задача построения [[обобщенная сеть Штейнера|обобщенной сети Штейнера]], также известная как задача проектирования сети с повышенной живучестью (survivable network), представляет собой обобщение задачи | Задача построения [[обобщенная сеть Штейнера|обобщенной сети Штейнера]], также известная как задача проектирования сети с повышенной живучестью (survivable network), представляет собой обобщение задачи построения леса Штейнера. Здесь функция требования соединения <math>r: V \times V \to \mathbb{N} \;</math> обозначает количество путей с непересекающимися ребрами, которые необходимо установить между каждой парой вершин. Иначе говоря, задача заключается в нахождении мульти-подмножества H ребер G с минимальной стоимостью (H может включать одно и то же ребро несколько раз), такого, что для каждой пары вершин <math>(x, y) \in V \;</math> имеется r(x, y) путей с непересекающимися ребрами из x в у в множестве G[H]. Задача заключается в нахождении множества H с минимальной стоимостью. | ||
Очевидно, что в случае, когда <math>r(x, y) \in \{ 0, 1 \} \;</math> для всех <math>(x, y) \in V \times V \;</math>, эта задача сводится к задаче построения леса Штейнера. | Очевидно, что в случае, когда <math>r(x, y) \in \{ 0, 1 \} \;</math> для всех <math>(x, y) \in V \times V \;</math>, эта задача сводится к задаче построения леса Штейнера. | ||
== Основные результаты == | == Основные результаты == | ||