4446
правок
Сложность ядра: различия между версиями
Материал из WEGA
м
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
Алгоритмическое исследование ядра представляет собой сложную задачу, поскольку на его определение накладывается экспоненциальное число ограничений. Следующие вопросы о вычислительной сложности привлекли значительное внимание исследователей: | Алгоритмическое исследование ядра представляет собой сложную задачу, поскольку на его определение накладывается экспоненциальное число ограничений. Следующие вопросы о вычислительной сложности привлекли значительное внимание исследователей: | ||
(1) Проверка сбалансированности: можно ли за полиномиальное время проверить, имеет ли данный экземпляр игры непустое ядро? | (1) ''Проверка сбалансированности'': можно ли за полиномиальное время проверить, имеет ли данный экземпляр игры непустое ядро? | ||
(2) Проверка принадлежности: можно ли за полиномиальное время проверить, принадлежит ли ядру данный дележ? | (2) ''Проверка принадлежности'': можно ли за полиномиальное время проверить, принадлежит ли ядру данный дележ? | ||
(3) Поиск члена ядра: можно ли за полиномиальное время найти дележ ядра? | (3) ''Поиск члена ядра'': можно ли за полиномиальное время найти дележ ядра? | ||
| Строка 25: | Строка 25: | ||
ИГРА О ПОВЕДЕНИИ ПОТОКА. Пусть D = (V, E, !, s, t) – ориентированная сеть, где V – множество вершин, E – множество дуг, a ): E ! R+ – функция пропускной способности дуги, s и t – источник и сток сети, соответственно. Предположим, что каждый игрок контролирует одну дугу сети. Значение максимального потока можно рассматривать как прибыль, получаемую игроками при сотрудничестве. Тогда игра о поведении потока Ff = (E; v), связанная с сетью D, определяется следующим образом: | '''ИГРА О ПОВЕДЕНИИ ПОТОКА (FLOW GAME)'''. Пусть D = (V, E, !, s, t) – ориентированная сеть, где V – множество вершин, E – множество дуг, a ): E ! R+ – функция пропускной способности дуги, s и t – источник и сток сети, соответственно. Предположим, что каждый игрок контролирует одну дугу сети. Значение максимального потока можно рассматривать как прибыль, получаемую игроками при сотрудничестве. Тогда игра о поведении потока Ff = (E; v), связанная с сетью D, определяется следующим образом: | ||
(1) E – это команда игроков; | (1) E – это команда игроков; | ||
