NP-полнота задачи о вершинном покрытии — различия между версиями
м (→Определение) |
м (→Доказательство NP-полноты) |
||
Строка 5: | Строка 5: | ||
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число. | '''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число. | ||
==Доказательство NP-полноты== | ==Доказательство NP-полноты== | ||
− | Для доказательства NP-полноты задачи о | + | Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP. |
===Задача о вершинном покрытии является NP-трудной=== | ===Задача о вершинном покрытии является NP-трудной=== | ||
Для доказательства сведем по Карпу [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. | Для доказательства сведем по Карпу [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. |
Версия 22:07, 15 марта 2010
Содержание
Определение
Вершинным покрытием графа
называется такое множество его вершин, что у любого ребра в хотя бы одна из вершин лежит в . Размер вершинного покрытия - это число входящих в него вершин.Формулировка
Задача о вершинном покрытии(COVER) состоит в нахождении вершинного покрытия размера
, где - некоторое натуральное число.Доказательство NP-полноты
Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.
Задача о вершинном покрытии является NP-трудной
Для доказательства сведем по Карпу задачу о независимом множестве к нашей.
Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе
выбрано независимое множество вершин . Тогда у любого ребра из одна из вершин не лежит в , так как иначе какие-то две вершины в были бы соединены ребром. Значит дополнение - вершинное покрытие. Пусть теперь в графе выбрано вершинное покрытие . Любому ребру в инциндентна хотя бы одна вершина из , значит никакое ребро не может соединять две вершины из дополнения , поэтому дополнение - независимое множество.Пусть в графе
c вершинами необходимо найти независимое множество размера . По доказанному выше оно существует тогда и только тогда, когда в есть вершинное покрытие размера . Данное сведение можно выполнить за полиномиальное времяЗадача о вершинном покрытии принадлежит классу NP
В качестве сертификата возьмем набор из
вершин. Если в графе ребер, то за время можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.