4551
правка
Сложность ядра: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 82: | Строка 82: | ||
Теорема 3. Пусть имеются игра на дереве Штейнера | '''Теорема 3. Пусть имеются игра на дереве Штейнера <math>\Gamma_s = (N, \gamma)</math>, заданная на сети <math>G = (V, E; \omega)</math>, и вектор <math>\mathbf{x}: N \to R^+</math>, <math>\mathbf{x}(N) = \gamma(N)</math>. Задача о существовании коалиции <math>S \subset N</math>, такой, что <math>\mathbf{x}(S) > \gamma(S)</math>, является <math>\mathcal{NP}</math>-сложной. Другими словами, проверка принадлежности к ядру для игр на дереве Штейнера является <math>\mathcal{NP}</math>-сложной.''' | ||
| Строка 88: | Строка 88: | ||
Пусть даны игра | Пусть даны игра на дереве Штейнера <math>\Gamma_s = (N, \gamma)</math>, заданная на сети <math>G = (V, E; \omega)</math>, и подмножество <math>S \subseteq N</math>. Тогда в подигре <math>(S, \gamma_s)</math> значение <math>\gamma(S') \; (S' \subseteq S)</math> является весом минимального дерева Штейнера G относительно подмножества <math>S\ \cup \{ v_0 \}</math>, где все вершины в N \ S рассматриваются как коммутаторы, но не потребители. Далее, в работе Фанга и др. [4] было показано, что проверка полной сбалансированности игры на дереве Штейнера также является <math>\mathcal{NP}</math>-сложной. Это первый пример NP-сложности задачи для условия полной сбалансированности. | ||