(не показано 15 промежуточных версий 2 участников)
Строка 1:
Строка 1:
−
−
−
Условие.
−
Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное <m>k</m>. Существует ли подсемейство, состоящее из <m>k</m> попарно непересекающихся множеств?
Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное <m>k</m>. Существует ли подсемейство, состоящее из <m>k</m> попарно непересекающихся множеств?
−
Решение.
+
[[Категория:Решенные задачи]]
−
+
−
Сведем задачу о клике к данной задаче.
+
−
+
−
Пусть дан граф <m>\tilde{G} = \{\tilde{V},\tilde{E}\}</m>, требуется найти в нем клику размера <m>k</m>. Как известно, это NP-полная задача. Рассмотрим теперь граф <m>G = \{V,E\}</m> --- дополнение графа <m>\tilde{G}</m>, т.е. граф с тем же множеством вершин, и <m>2</m> вершины в нем смежны тогда и только тогда, когда они не смежны в <m>\tilde{G}</m>. Пронумеруем ребра графа <m>G</m> числами от <m>1</m> до <m>|E|</m>, а вершины --- числами от <m>|E|+1</m> до <m>|V|+|E|</m>. Теперь каждой вершине <m>v</m> графа <m>G</m> поставим в соответствие множество натуральных чисел <m>A_v</m>, в котором хранится, во-первых, номер вершины <m>v</m>, а во вторых, номера всех ребер, которые инцидентны вершине <m>v</m>.
+
−
+
−
По построению множества <m>A_{v_1}</m> и <m>A_{v_2}</m> имеют непустое пересечение тогда и только тогда, когда вершины <m>v_1</m> и <m>v_2</m> смежны в графе <m>G</m>. Пусть в семействе множеств <m>A_{|E|+1},\dots,A_{|E|+|V|}</m> существует подсемейство из <m>k</m> попарно непересекающихся подмножеств <m>A_{v_1},\dots,A_{v_k}</m>. Тогда в графе <m>G</m> вершины <m>v_1,\dots,v_k</m> попарно несмежны. Тогда в графе <m>\tilde{G}</m>вершины <m>v_1,\dots,v_k</m> попарно смежны, т.е. в графе <m>\tilde{G}</m> найдена клика размера <m>k</m>.
+
−
+
−
Таким образом, мы полиномиально (система множеств <m>A_{|E|+1},\dots,A_{|E|+|V|}</m> строится за время <m>O(|E| + |V|)</m>) свели NP-полную задачу о клике к данной задаче. Значит, данная задача NP-полна.
+
−
+
−
[[Category:Решенные задачи]]
+
Версия 15:49, 20 мая 2020
Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное . Существует ли подсемейство, состоящее из попарно непересекающихся множеств?