NP-полнота задачи о вершинном покрытии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формулировка)
Строка 12: Строка 12:
 
<math>IND \le_{k} COVER</math>
 
<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> выбрано независимое множество вершин <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>. Данное сведение можно выполнить за полиномиальное время
 
Пусть в графе <math>G</math> c <math>n</math> вершинами необходимо найти независимое множество размера <math>k</math>. По доказанному выше оно существует тогда и только тогда, когда в <math>G</math> есть вершинное покрытие размера <math>n-k</math>. Данное сведение можно выполнить за полиномиальное время

Версия 16:05, 30 мая 2010

Определение

Вершинным покрытием графа [math]G[/math] называется такое множество [math]V[/math] его вершин, что у любого ребра в [math]G[/math] хотя бы одна из вершин лежит в [math]V[/math]. Размер вершинного покрытия - это число входящих в него вершин.

Формулировка

Языком COVER называется множество пар [math]\langle G,k \rangle[/math], где [math]G[/math] - неориентированный граф, [math]k[/math] - натуральное число. Слово принадлежит языку COVER, если ли граф [math]G[/math] содержит вершинное покрытие размера [math]k[/math]. Задача о вершинном покрытии является NP-полной.

Доказательство 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] можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.