Сложность ядра: различия между версиями

'''ИГРА НА ДЕРЕВЕ ШТЕЙНЕРА (STEINER TREE GAME)'''. Пусть G = (V, E; <math>\omega</math>) – граф с взвешенными ребрами, с <math>V = \{ v_0 \} \cup N \cup M </math>, где <math>N, M \subseteq V \backslash \{ v_0 \}</math> – непересекающиеся множества. <math>v_0</math> представляет центрального поставщика, N – множество потребителей, M – множество коммутаторов, а <math>\omega(e)</math> обозначает стоимость соединения двух конечных точек ребра e напрямую. Требуется соединить всех потребителей в N с центральным поставщиком <math>v_0</math>. Соединение не ограничивается использованием прямых связей между двумя потребителями или потребителем и центральным поставщиком, оно может проходить через некоторые коммутаторы в M. Цель заключается в том, чтобы организовать самое дешевое соединение и справедливо распределить стоимость соединения между потребителями. В этом случае соответствующая игра на дереве Штейнера <math>\Gamma_s = (N, \gamma)</math> определяется следующим образом:

Задача 2 (проверка сбалансированности игры на дереве Штейнера)

Дано: граф с взвешенными ребрами G = (V, E, !) с V = fv0g [ N[M.

Вопрос: существует ли вектор x: N ! R+, такой, что x(N) = y(N) и x(S) < y(S) для всех подмножеств S С N?

Задача 3 (проверка принадлежности для игры на дереве Штейнера)

Дано: граф с взвешенными ребрами G = (V, E, !) с V = fv0g[N[Mandx:N!R+.

Вопрос: верно ли, что x(N) = y(N) и x(S) < y(S) для всех подмножеств S С N?