Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Vcover-clique — различия между версиями
Tsyganova (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
'''Решение''' | '''Решение''' | ||
| − | + | Докажем, что каждая задача полиномиально сводима к задаче о независимом множестве (и обратно), следовательно, они будут полиномиально сводимы друг к другу. | |
| − | + | 1) Вершинное покрытие <-> задача о независимом наборе. | |
| − | + | Эти задачи эквивалентны. Множество вершин S является вершинным покрытием тогда и только тогда, когда его дополнение S', где (S' = V\S), а V - это множество всех вершин графа, является независимым множеством. Таким образом, найдя максимальное независимое множество и взяв дополнение от него, мы найдем максимальное вершинное покрытие графа, и наоборот. | |
| + | |||
| + | 2) Задача о независимом наборе <-> максимальная клика. | ||
| + | |||
| + | Известно, что множество независимо тогда и только тогда, когда оно является кликой в дополнении графа. Таким образом, если требуется найти максимальную клику, то нужно построить дополнение к графу, найти в дополнении максимальное независимое множество, и это множество как раз будет составлять максимальную клику в исходном графе. Чтобы найти максимальное независимое множество, нужно построить дополнение к графу, найти в дополнении максимальную клику, и эта клика будет максимальным множеством в исходном графе. | ||
| + | |||
| + | Итак, чтобы найти вершинное покрытие в графе, нужно построить дополнение к графу, найти в нем максимальную клику, и взять оставшиеся вершины, не вошедшие в максимальную клику. | ||
| + | |||
| + | Чтобы найти максимальную клику, нужно построить дополнение к графу, в дополнении найти вершинное покрытие, и взять дополнение к множеству вершин из вершинного покрытия. Это и будет максимальная клика. | ||
| + | |||
| + | Все операции по взятию дополнения к множеству вершин и построению дополнения делаются за полиномиальное время, поэтому задачи полиномиально сводимы. | ||
| + | |||
| + | PS. Все факты об эквивалентностях задач взяты из Википедии, чтобы не доказывать лишний раз. | ||
| − | |||
[[Category:На проверку]] | [[Category:На проверку]] | ||
Версия 14:23, 24 декабря 2014
Задача vcover-clique
Цыганова Светлана, 974 гр.
Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач
- о поиске максимального по числу вершин полного подграфа (клики) в графе
- и задачи о вершинном покрытии
Решение
Докажем, что каждая задача полиномиально сводима к задаче о независимом множестве (и обратно), следовательно, они будут полиномиально сводимы друг к другу.
1) Вершинное покрытие <-> задача о независимом наборе.
Эти задачи эквивалентны. Множество вершин S является вершинным покрытием тогда и только тогда, когда его дополнение S', где (S' = V\S), а V - это множество всех вершин графа, является независимым множеством. Таким образом, найдя максимальное независимое множество и взяв дополнение от него, мы найдем максимальное вершинное покрытие графа, и наоборот.
2) Задача о независимом наборе <-> максимальная клика.
Известно, что множество независимо тогда и только тогда, когда оно является кликой в дополнении графа. Таким образом, если требуется найти максимальную клику, то нужно построить дополнение к графу, найти в дополнении максимальное независимое множество, и это множество как раз будет составлять максимальную клику в исходном графе. Чтобы найти максимальное независимое множество, нужно построить дополнение к графу, найти в дополнении максимальную клику, и эта клика будет максимальным множеством в исходном графе.
Итак, чтобы найти вершинное покрытие в графе, нужно построить дополнение к графу, найти в нем максимальную клику, и взять оставшиеся вершины, не вошедшие в максимальную клику.
Чтобы найти максимальную клику, нужно построить дополнение к графу, в дополнении найти вершинное покрытие, и взять дополнение к множеству вершин из вершинного покрытия. Это и будет максимальная клика.
Все операции по взятию дополнения к множеству вершин и построению дополнения делаются за полиномиальное время, поэтому задачи полиномиально сводимы.
PS. Все факты об эквивалентностях задач взяты из Википедии, чтобы не доказывать лишний раз.