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

Материал из Викиконспекты
Перейти к: навигация, поиск
(создание странички)
 
м (Задача о вершинном покрытии является NP-трудной)
Строка 6: Строка 6:
 
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
 
Для доказательства NP-полноты задачи о независимом множестве покажем, что она является NP-трудной и принадлежит классу NP.
 
===Задача о вершинном покрытии является NP-трудной===
 
===Задача о вершинном покрытии является NP-трудной===
Для доказательства сведем по Карпу задачу о независимом множестве к нашей.
+
Для доказательства сведем по Карпу [[Задача о независимом множестве|задачу о независимом множестве]] к нашей.
  
 
<math>IND \le_{k} COVER</math>
 
<math>IND \le_{k} COVER</math>
Строка 13: Строка 13:
  
 
Пусть в графе <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>. Данное сведение можно выполнить за полиномиальное время
 +
 
===Задача о вершинном покрытии принадлежит классу NP===
 
===Задача о вершинном покрытии принадлежит классу NP===
 
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в  графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.
 
В качестве сертификата возьмем набор из <math>k</math> вершин. Если в  графе <math>e</math> ребер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.

Версия 18:41, 15 марта 2010

Определение

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