Участник:Rechique/vcover-clique

Материал из DISCOPAL
< Участник:Rechique
Версия от 20:27, 15 мая 2019; Rechique (обсуждение | вклад) (Новая страница: «Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Vcover-clique|: На проверку…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

: На проверку

Будем работать со следующими задачами:

1)Clique = {(G, k)| в графе есть клика размером k}

2)IndSet = {(G, k)| в графе есть независимое множество из k вершин}

3)VertexCover = {(G, k)| в графе есть вершинное покрытие из k вершин}

Задачу Clique можно свести по карпу к задаче о клике (просто перебором k). Аналогично с задачей о вершинном покрытии.

Далее сводим Clique к Indset взятием дополнения графа. А Indset и VertexCover сводятся к друг другу заменой k на n - k, где n - число вершин: если вершинное покрытие задело все ребра, то между оставшиеся вершинами ребер быть не может, иначе эти ребра не были бы задеты. И наоборот, если между оставшимися ребер нет, то все ребра покрыты взятыми.