Лес Штейнера: различия между версиями

Специальный случай задачи о лесе Штейнера представляет собой построение дерева Штейнера. Здесь все пары полюсов имеют общую корневую вершину r 2 V, т.е. r 2 FSI; для всех пар полюсов (si, ti) 2 R. Иными словами, исходными данными задачи являются множество вершин полюсов КУ и корневая вершина r 2 V, а цель состоит в соединении полюсов из R с корневой вершиной r самым экономичным образом. Решением с минимальной стоимостью является дерево.

Задача построения обобщенной сети Штейнера, также известная как задача проектирования сети с повышенной живучестью (survivable network), представляет собой обобщение задачи нахождения леса Штейнера. Здесь функция требования соединения r: V x V ! N обозначает количество путей с непересекающимися ребрами, которые необходимо установить между каждой парой вершин. Иначе говоря, задача заключается в нахождении мульти-подмножества H ребер G с минимальной стоимостью (H может включать одно и то же ребро несколько раз), такого, что для каждой пары вершин (x, y) 2 V имеется r(x, y) путей с непересекающимися ребрами из x в у в множестве G[H]. Задача заключается в нахождении множества H с минимальной стоимостью.

Очевидно, что в случае, когда r(x, y) 2 {0, 1} для всех (x, y) 2 V x V, эта задача сводится к задаче построения леса Штейнера.