NP-полнота задачи о вершинном покрытии — различия между версиями
(создание странички) |
м (rollbackEdits.php mass rollback) |
||
(не показано 11 промежуточных версий 5 участников) | |||
Строка 1: | Строка 1: | ||
==Определение== | ==Определение== | ||
− | Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин | + | Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин. |
+ | |||
==Формулировка== | ==Формулировка== | ||
− | + | Языком COVER называется множество пар <tex>\langle G,k \rangle</tex>, где <math>G</math> - неориентированный граф, <math>k</math> - натуральное число. Слово принадлежит языку COVER, если ли граф <math>G</math> содержит вершинное покрытие размера <math>k</math>. Задача о вершинном покрытии является [[Понятие NP-трудной и NP-полной задачи|NP-полной]]. | |
+ | |||
==Доказательство NP-полноты== | ==Доказательство NP-полноты== | ||
− | Для доказательства NP-полноты задачи о | + | Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP. |
===Задача о вершинном покрытии является NP-трудной=== | ===Задача о вершинном покрытии является NP-трудной=== | ||
− | Для доказательства сведем по Карпу задачу о независимом множестве к нашей. | + | Для доказательства [[Сведение по Карпу|сведем по Карпу]] [[Задача о независимом множестве|задачу о независимом множестве]] к нашей. |
<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>. Данное сведение можно выполнить за полиномиальное время | ||
+ | |||
===Задача о вершинном покрытии принадлежит классу NP=== | ===Задача о вершинном покрытии принадлежит классу NP=== | ||
− | В качестве сертификата возьмем набор из <math>k</math> вершин. Если в | + | В качестве сертификата возьмем набор из <math>k</math> вершин. Если в графе <math>e</math> рёбер, то за время <math>O(ek)</math> можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе. |
+ | |||
+ | [[Категория:NP]] |
Текущая версия на 19:38, 4 сентября 2022
Определение
Вершинным покрытием графа
называется такое множество его вершин, что у любого ребра в хотя бы одна из вершин лежит в . Размер вершинного покрытия - это число входящих в него вершин.Формулировка
Языком COVER называется множество пар NP-полной.
, где - неориентированный граф, - натуральное число. Слово принадлежит языку COVER, если ли граф содержит вершинное покрытие размера . Задача о вершинном покрытии являетсяДоказательство NP-полноты
Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.
Задача о вершинном покрытии является NP-трудной
Для доказательства сведем по Карпу задачу о независимом множестве к нашей.
Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе
выбрано независимое множество вершин . Тогда у любого ребра из хотя бы одна из вершин не лежит в , так как иначе какие-то две вершины в были бы соединены ребром. Значит дополнение - вершинное покрытие. Пусть теперь в графе выбрано вершинное покрытие . Любому ребру в инциндентна хотя бы одна вершина из , значит никакое ребро не может соединять две вершины из дополнения , поэтому дополнение - независимое множество.Пусть в графе
c вершинами необходимо найти независимое множество размера . По доказанному выше оно существует тогда и только тогда, когда в есть вершинное покрытие размера . Данное сведение можно выполнить за полиномиальное времяЗадача о вершинном покрытии принадлежит классу NP
В качестве сертификата возьмем набор из
вершин. Если в графе рёбер, то за время можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.