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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 15 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
<big>Цыганова Светлана, 974гр.</big>
 
−
 
−
'''Задача'''
 
 
Покажите, что задача об упаковке (в заданном семействе подмножеств найти максимальное число попарно непересекающихся подмножеств) полиномиально эквивалентна задаче о нахождении максимальной клики в графе.
 
Покажите, что задача об упаковке (в заданном семействе подмножеств найти максимальное число попарно непересекающихся подмножеств) полиномиально эквивалентна задаче о нахождении максимальной клики в графе.
  
−
'''Решение'''
 
−
 
−
1) Клика -> упаковка.
 
−
Пусть у нас задан граф на n вершинах, на котором необходимо найти максимальную клику. Сведем задачу к задаче нахождения максимального числа попарно несересекающихся множеств. Для этого воспользуемся тем фактом, что множество вершин независимо тогда и только тогда, когда оно является кликой в дополнении графа. Тогда будем действовать по следующему алгоритму:
 
−
 
−
a) Построим дополнение к исходному графу (Это займет полиномиальное время, например, самый простой способ займет <latex>$n^2$</latex>).
 
−
 
−
б) Найдем на графе-дополнении максимальное число попарно непересающихся подмножеств на, где каждое подмножество обозначается отдельной вершиной. Если какие-то два подмножества пересекаются, это значит, что они соединены ребром на графе.
 
−
 
−
в) Полученные непересекающиеся подмножества образуют клику в исходном графе. Очевидно, что если мы искали максимальное число попарно непересекающихся подмножеств, то и соответствующая им клика тоже будет максимальной. Итого задача о нахождении максимальной клики сводится за полиномиальное время к задаче об упаковке.
 
  
−
2) Упаковка -> клика.
+
<!--Вообще-то, решения уже есть-->
  
−
[[Category:На проверку]]
+
[[Категория:Решенные задачи]]
 +
[[Категория:Теоретические задачи]]

Текущая версия на 06:50, 4 мая 2023

Покажите, что задача об упаковке (в заданном семействе подмножеств найти максимальное число попарно непересекающихся подмножеств) полиномиально эквивалентна задаче о нахождении максимальной клики в графе.

Источник — «https://discopal.ispras.ru/index.php?title=Полиномиальные_сводимости_и_NP-полные_задачи._Классы_NP,_coNP,_NPC/Задачи/Packing=MaxClique&oldid=25812»