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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
==Определение==
 
==Определение==
 
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин.
 
Вершинным покрытием графа <math>G</math> называется такое множество <math>V</math> его вершин, что у любого ребра в <math>G</math> хотя бы одна из вершин лежит в <math>V</math>. Размер вершинного покрытия - это число входящих в него вершин.

Текущая версия на 19:38, 4 сентября 2022

Определение

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