43
правки
Изменения
создание странички
==Определение==
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин
==Формулировка==
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства сведем по Карпу задачу о независимом множестве к нашей.
<math>IND \le_{k} COVER</math>
Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе <math>G</math> выбрано независимое множество вершин <math>V</math>. Тогда у любого ребра из <math>G</math> одна из вершин не лежит в <math>V</math>, так как иначе какие-то две вершины в <math>V</math> были бы соединены ребром. Значит дополнение <math>V</math> - вершинное покрытие. Пусть теперь в графе <math>G</math> выбрано вершинное покрытие <math>V</math>. Любому ребру в <math>G</math> инциндентна хотя бы одна вершина из <math>V</math>, значит никакое ребро не может соединять две вершины из дополнения <math>V</math>, поэтому дополнение <math>V</math> - независимое множество.
Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время
===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин
==Формулировка==
'''Задача о вершинном покрытии(COVER)''' состоит в нахождении вершинного покрытия размера <math>k</math>, где <math>k</math> - некоторое натуральное число.
==Доказательство NP-полноты==
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
===Задача о вершинном покрытии является NP-трудной===
Для доказательства сведем по Карпу задачу о независимом множестве к нашей.
<math>IND \le_{k} COVER</math>
Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе <math>G</math> выбрано независимое множество вершин <math>V</math>. Тогда у любого ребра из <math>G</math> одна из вершин не лежит в <math>V</math>, так как иначе какие-то две вершины в <math>V</math> были бы соединены ребром. Значит дополнение <math>V</math> - вершинное покрытие. Пусть теперь в графе <math>G</math> выбрано вершинное покрытие <math>V</math>. Любому ребру в <math>G</math> инциндентна хотя бы одна вершина из <math>V</math>, значит никакое ребро не может соединять две вершины из дополнения <math>V</math>, поэтому дополнение <math>V</math> - независимое множество.
Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время
===Задача о вершинном покрытии принадлежит классу NP===
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.
