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