Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/NPC «k бригад обслуживания» — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
все вершины графа без повторений.
 
все вершины графа без повторений.
  
[[Category:Решенные задачи]]
+
[[Category:Нерешенные задачи]]
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->

Версия 07:49, 24 апреля 2014

Задача о k бригадах обслуживания

Докажите NP-полноту следующей задачи:

Дан граф, в нем

  • выделена одна вершина B (база)
  • и дано число k.

Требуется определить, существуют ли k вершинно непересекаюшихся (кроме как в вершине B) циклов в графе (все содержащие вершину B), в объединении содержащие все вершины графа?

Здесь каждый цикл соответствует маршруту одной бригады обслуживания, которые вместе должны посетить все вершины графа без повторений.