4446
правок
Сложность ядра: различия между версиями
Материал из WEGA
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
'''ИГРА НА ДЕРЕВЕ ШТЕЙНЕРА (STEINER TREE GAME)'''. Пусть G = (V, E; <math>\omega</math>) – граф с взвешенными ребрами, | '''ИГРА НА ДЕРЕВЕ ШТЕЙНЕРА (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> определяется следующим образом: | ||
(1) N – это команда игроков; | (1) N – это команда игроков; | ||
| Строка 52: | Строка 52: | ||
Задача 2 (проверка сбалансированности игры на дереве Штейнера) | '''Задача 2''' (проверка сбалансированности игры на дереве Штейнера) | ||
Дано: граф с взвешенными ребрами G = (V, E, | Дано: граф с взвешенными ребрами G = (V, E; <math>\omega</math>), <math>V = \{ v_0 \} \cup N \cup M</math>. | ||
Вопрос: существует ли вектор x: N | Вопрос: существует ли вектор <math>x: N \to R^+</math>, такой, что <math>x(N) = \gamma(N)</math> и <math>x(S) \le \gamma(S)</math> для всех подмножеств <math>S \subset N</math>? | ||
Задача 3 (проверка принадлежности для игры на дереве Штейнера) | '''Задача 3''' (проверка принадлежности для игры на дереве Штейнера) | ||
Дано: граф с взвешенными ребрами G = (V, E, | Дано: граф с взвешенными ребрами G = (V, E; <math>\omega</math>), <math>V = \{ v_0 \} \cup N \cup M</math> и <math>x : N \to R^+</math>. | ||
Вопрос: верно ли, что x(N) = | Вопрос: верно ли, что <math>x(N) = \gamma(N)</math> и <math>x(S) \le \gamma(S)</math> для всех подмножеств <math>S \subset N</math>? | ||
== Основные результаты == | == Основные результаты == | ||
