Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Vcover-clique — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(не показано 13 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
===== Задача vcover-clique =====
 
===== Задача vcover-clique =====
<big>Цыганова Светлана, 974 гр.</big>
 
  
 
Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач
 
Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач
Строка 6: Строка 5:
 
* и задачи о вершинном покрытии
 
* и задачи о вершинном покрытии
  
'''Решение'''
 
  
1) Вершинное покрытие -> максимальный по числу вершин полный подграф.
+
<!--Вообще-то, решения уже есть-->
  
Заметим, что если есть полный подграф, то все, кроме одной вершины лежат в вершинном покрытии. Воспользуемся этим фактом.
+
[[Категория:Решенные задачи]]
 
+
Из вершинного покрытия будем находить полный подграф следующим образом:
+
 
+
a) Найдем все полные подграфы, состоящие из вершин вершинного покрытия
+
 
+
[[Category:На проверку]]
+

Версия 00:41, 16 мая 2019

Задача vcover-clique

Показать конкретное полиномиальное сведение друг к другу (в обе стороны) задач

  • о поиске максимального по числу вершин полного подграфа (клики) в графе
  • и задачи о вершинном покрытии