Презентация на тему Np-полнота и сложность Задачи Штейнера

n точек. Требуется соединить эти точки, используя дополнительные точки

Штейнера, таким образом, чтобы каждая точка была соединена с каждой и чтобы длина всех проведённых линий была минимальна.

и все соединения должны быть отрезками, соединяющими точки (исходные

и промежуточные).
В каждой промежуточной точке должны сходиться три отрезка
В исходных точках должны сходиться не более трёх отрезков.
Угол между отрезками, сходящимися в одной точке не должен быть меньше 120 градусов

на графах.

множество из n точек. Обозначим LМ длину минимального остовного

дерева, которое стягивает эти точки, и LS – длину минимального дерева Штейнера. Для любого конечного множества точек на плоскости

на графах является NP-полной.
Доказательство:
1. показать, что P принадлежит классу

NP;
2. Выбрать известную NP-полную задачу из P`;
3. Построить преобразование f из P` в P;
4. доказать, что f-полиномиальное преобразования.

, например принадлежит классу NP.
В этом случае, существует такое решение , и мы можем проверить за полиномиальное время, что:
T действительно дерево: оно не содержит циклов и оно связно;
дерева T касается всех терминалов указанного множества R;
число ребер, которые включает дерево не более k.

множества X с |X| = 3q;
Множество C состоящее из

3-элементных подмножеств


Вопрос:
Существует ли такое подсемейство С C`, которое соответствует и
члены решения C` образуют разбиение множества X;
.

покрытия трёхэлементными множествами , которое определяется множеством

и группой трёхэлементных множеств Необходимо построить ST такое, что множество терминалов графа G = (V, E) будет равно R и длина остовного дерева не будет превосходить k.

Штайнера:
T действительно дерево: оно не содержит циклов и оно

связно;
дерево T касается всех терминалов указанного множества R;
число ребер, которые включает дерево не более k.

Установим K равное 4q, где q - количество трёхэлементных подмножеств задачи Х3С.

ДШ, Т содержит {Х} , v и не более

q С-узлов -> Но если V ≤4q+1, С-узлы не охватят все 3q x-узлов
V=4q+1
K=4q

Дан граф G = (V, E;cost), STP - любое

дерево из G : GS представляет собой полный граф с множеством вершин S.
Пусть MST (GS) минимальное остовное дерево GS.
Для любого графа H, cost(H) является суммой весов всех ребер в H.
Обозначаем Стоимость минимального остовного дерева Н как mst(H).
Дерево Штейнера на подмножество S`, в котором все терминалы листья называется Полной компонентой.
T – дерево, соединяющие каждую вершину Штейнера с терминалом.
Пусть T(H) граф минимальной стоимости в , который содержит H и покрывает все терминалы. Прирост H по отношению к Т определяется
loss(K) является стоимостью подключения точек Штейнера из K к терминалам.

= (V;E; cost) с весом рёбер, удовлетворяющих неравенству треугольника,

набором терминалов и целым
ВЫХОД: k-ограниченное дерево Штайнера графа G, включающее все терминалы из S

T = MST(GS)
H = GS
Repeat forever
Поиск k-ограниченной полной компоненты K с максимальным r=gainT(K)/loss(K)
If r≤0 then exit repeat
H = H U K
T = MST(T U C[K])
Output дерево MST(H)

алгоритм может быть реализован за общее время работы
O

(n2m) ,
где m и n - количество терминалов и нетерминалов соответственно