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

Ссылки сюда (6) →

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

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

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

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

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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.