4551
правка
Редукция данных для доминирования в графах: различия между версиями
Перейти к навигации
Перейти к поиску
Редукция данных для доминирования в графах (посмотреть исходный код)
Версия от 01:13, 25 марта 2013
, 25 марта 2013нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 4: | Строка 4: | ||
NP-полная задача поиска доминирующего множества (DOMINATING SET), как известно, представляет значительную сложность. | NP-полная задача поиска доминирующего множества (DOMINATING SET), как известно, представляет значительную сложность. | ||
Дано: неориентированный граф <math>G = (V, E) \; </math> и целое число <math>k \ge 0 \; </math>. | |||
Дано: неориентированный граф G = (V, E) и целое число k > | |||
Вопрос: существует ли подграф S С V с jSj < k, такой, что каждая вершина v 2 V входит в S, либо по крайней мере один из ее соседей входит в S? | Вопрос: существует ли подграф S С V с jSj < k, такой, что каждая вершина v 2 V входит в S, либо по крайней мере один из ее соседей входит в S? | ||