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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
===== Задача vcover-clique =====
 
===== Задача vcover-clique =====
<big>Цыганова Светлана, 974 гр.</big>
 
  
 
Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач
 
Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач
Строка 6: Строка 5:
 
* и задачи о вершинном покрытии
 
* и задачи о вершинном покрытии
  
'''Решение'''
+
[[Category:Решенные задачи]]
 
+
<!--Вообще-то, решения уже есть-->
Докажем, что каждая задача полиномиально сводима к задаче о независимом множестве (и обратно), следовательно, они будут полиномиально сводимы друг к другу.
+
 
+
1) Вершинное покрытие <-> задача о независимом наборе.
+
 
+
Эти задачи эквивалентны. Множество вершин S является вершинным покрытием тогда и только тогда, когда его дополнение S', где (S' = V\S), а V - это множество всех вершин графа, является независимым множеством. Таким образом, найдя максимальное независимое множество и взяв дополнение от него, мы найдем максимальное вершинное покрытие графа, и наоборот.
+
 
+
2) Задача о независимом наборе <-> максимальная клика.
+
 
+
Известно, что множество независимо тогда и только тогда, когда оно является кликой в дополнении графа. Таким образом, если требуется найти максимальную клику, то нужно построить дополнение к графу, найти в дополнении максимальное независимое множество, и это множество как раз будет составлять максимальную клику в исходном графе. Чтобы найти максимальное независимое множество, нужно построить дополнение к графу, найти в дополнении максимальную клику, и эта клика будет максимальным множеством в исходном графе.
+
 
+
Итак, чтобы найти вершинное покрытие в графе, нужно построить дополнение к графу, найти в нем максимальную клику, и взять оставшиеся вершины, не вошедшие в максимальную клику.
+
 
+
Чтобы найти максимальную клику, нужно построить дополнение к графу, в дополнении найти вершинное покрытие, и взять дополнение к множеству вершин из вершинного покрытия. Это и будет максимальная клика.
+
 
+
Все операции по взятию дополнения к множеству вершин и построению дополнения делаются за полиномиальное время, поэтому задачи полиномиально сводимы.
+
 
+
PS. Все факты об эквивалентностях задач взяты из Википедии, чтобы не доказывать лишний раз.
+
 
+
 
+
[[Category:На проверку]]
+

Версия 02:24, 26 декабря 2014

Задача vcover-clique

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

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