Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Vcover-clique

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

Задача vcover-clique

Цыганова Светлана, 974 гр.

Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач

• о поиске максимального по числу вершин полного подграфа (клики) в графе
• и задачи о вершинном покрытии

Решение

1) Вершинное покрытие -> максимальный по числу вершин полный подграф.

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

Из вершинного покрытия будем находить полный подграф следующим образом:

a) Найдем все полные подграфы, состоящие из вершин вершинного покрытия

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

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

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