Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное <m>k</m>. Существует ли подсемейство, состоящее из <m>k</m> попарно непересекающихся множеств?
Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное <m>k</m>. Существует ли подсемейство, состоящее из <m>k</m> попарно непересекающихся множеств?
−
[[Category:На проверку]]
+
[[Category:Решенные задачи]]
−
+
−
<latex>
+
−
Решение (Целых Влады, 974 группа):
+
−
\begin{enumerate}
+
−
\item Сначала покажем, что задача принадлежит классу NP.
+
−
Действительно, если искомые множества существуют, то подсказка $y$---это $k$ попарно непересекающихся множеств,
+
−
причем проверку можно осуществить за полиномиальное время, используя память не больше полиномиального объема.
+
−
\item Покажем, что NP-полная задача существования независимого множества из $k$ вершин в графе (IS, Independent Set) полиномиально
+
−
сводится к рассматриваемой задаче.
+
−
Рассмотрим неориентированный связный граф $G=(V,E)$. Спрашивается, существует ли независимое множество из $k$ вершин
+
−
(таких, что никакие две
+
−
вершины множества не соединены ребром). Каждой вершине $v_i$ сопоставим множество инцидентных ей ребер
+
−
$S_{i} = \{(v_i, v_j)\in E\}$. Таким образом, рассматривается семейство из $|V|$ множеств. Если в полученной системе множеств существует $k$ попарно непересекающихся множеств,
+
−
то в графе существует независимое множество мощности $k$ (для этого достаточно взять из каждого из $k$ множеств
+
−
по соответствующей вершине). Наоборот, если в графе существует независимое множество вершин, то $k$ образованных ими множеств $S_i$
+
−
будут попарно непересекающимися.
+
−
\item Осталось пояснить, почему IS - задача о существовании независимого множества из $k$ вершин в графе
+
−
является NP-полной. Принадлежность к классу $NP$ следует из того, что в качестве подсказки в случае
+
−
ответа "да" можно взять
+
−
$k$ вершин, образующих независимое множество (проверка занимает полиномиальное время).
+
−
Покажем, что задача 3-SAT полиномиально сводится к задаче IS.
+
−
+
−
Пусть дана конъюнкция из $m$ 3-элементных дизъюнкций $C_1,\dots C_m$, образованных переменными $x_1,\dots x_n$ и
+
−
их отрицаниями $\bar x_1,\dots \bar x_n$. Построим граф $G$ следующим образом. Каждой из $m$ дизъюнкций
+
−
поставим в соответствие ``треугольник'' ---3 вершины, соединенные ребрами (например, если $C_1=x_1 \vee \bar x_2 \vee x_3$, то в графе $G$
+
−
существуют вершины $x_1,\bar x_2,x_3$, между которыми проведены 3 ребра). Таким образом, всего в графе $G$
+
−
$3\cdot m$ вершин. Проведем также ребра между всеми вершинами вида $x_i$ и $\bar x_i$.
+
−
Если конъюнкция выполнима, то в графе существует $m$-элементное независимое множество
+
−
(в каждом ``треугольнике'' выбирается вершина, соответствующая переменной, принимающей значение $1$ в данной конъюнкции). И наоборот, если
+
−
в графе существует $m$-элементное независимое множество $S$, то в него входит по одной вершине из каждого ``треугольника''.
+
−
Кроме того, вершины вида $x_i$ и $\bar x_i$ не могут входить в него одновременно (т.к. тогда множество не будет независимым).
+
−
Набор переменных $x_i = 1$, если $x_i\in S$ и $x_j = 0$, если $x_j \not \in S$ будет выполняющим ДНФ.
+
−
Таким образом, задача IS является NP-полной.
+
−
\end{enumerate}
+
−
+
−
+
−
</latex>
+
Версия 02:16, 26 декабря 2014
Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное . Существует ли подсемейство, состоящее из попарно непересекающихся множеств?