Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Vcover-clique
Материал из DISCOPAL
< Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC | Задачи
Версия от 15:49, 1 декабря 2014; Tsyganova (обсуждение | вклад)
Задача vcover-clique
Цыганова Светлана, 974 гр.
Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач
- о поиске максимального по числу вершин полного подграфа (клики) в графе
- и задачи о вершинном покрытии
Решение
1) Вершинное покрытие -> максимальный по числу вершин полный подграф.
Заметим, что если есть полный подграф, то все, кроме одной вершины лежат в вершинном покрытии. Воспользуемся этим фактом.
Из вершинного покрытия будем находить полный подграф следующим образом:
a) Найдем все полные подграфы, состоящие из вершин вершинного покрытия
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.