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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 17: Строка 17:
  
 
[[Категория:Решенные задачи]]
 
[[Категория:Решенные задачи]]
 +
[[Категория:Теоретические задачи]]

Текущая версия на 06:50, 4 мая 2023

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

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

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

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

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

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