4511
правок
Сложность ядра: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 46: | Строка 46: | ||
(1) N – это команда игроков; | (1) N – это команда игроков; | ||
(2) – вес минимального дерева Штейнера на G относительно множества S | (2) <math>\forall S \subseteq N, \gamma(S)</math> – вес минимального дерева Штейнера на G относительно множества <math>S \cup \{ v_0 \}</math>, то есть <math>\gamma(S) = min \{ \sum_{e \in E_S} \omega(e) : T_S = (V_S, E_S)</math> является поддеревом G с <math>V_S \supseteq S \cup \{ v_0 \} \}</math>. | ||