24.Другие np-полные задачи. Примеры сводимости в классе np.
Задача является NP-полной, если к ней можно эффективно свести задачу ВЫПОЛНИМОСТЬ, NP-полноту которой доказал С.Кук.
Имеет место ряд важных практических задач, для которых установлена их NP-полнота.
ЗАДАЧА ВЕРШИННОЕ ПОКРЫТИЕ.
Графом называется множество вершин и связывающих их ребер. Пример графа дает рис.1.
Вершины представлены с помощью кружков. Номера вершин указаны числами внутри кружков. Ребра – отрезки прямых линий, соединяющие вершины. Будем говорить, что вершина i покрывает некоторое ребро, если данная вершина i является концевой вершиной рассматриваемого ребра.Множество вершин называется вершинным покрытием, если для каждого ребра графа найдется хотя бы одна вершина из , которая ее покрывает. Так, одним из возможных вершинных покрытий представленного выше графа, является ={2,4,5}. Задача ВЕРШИННОЕ ПОКРЫТИЕ требует найти покрытие с заданным числом вершин.
Задание 1. Показать, что задача – найти вершинное покрытие минимального размера также NP-полна.
Закодируем граф с помощью матрицы смежности M вершин
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
1 |
3 |
0 |
1 |
0 |
0 |
1 |
0 |
4 |
1 |
0 |
0 |
0 |
1 |
0 |
5 |
0 |
0 |
1 |
1 |
0 |
0 |
6 |
0 |
1 |
0 |
0 |
0 |
0 |
Для экономии, часто в матрице смежности указывают только 1, а 0 – нет. Как видим, матрица смежности квадратная и симметричная.
Вопрос. Чему же соответствует вершинное покрытие размером, скажем, 3 на этой матрице?
Ответ: оно соответствует нулевой квадратной подматрице с одноименными строками и столбцами, размером 3*3.
ЗАДАЧА о КЛИКЕ размером n.
Эта задача состоит в том, чтобы для произвольного графа определить n вершин, никакие две из которых не соединены ребром. Так, примером клики размером 3 для изображенного выше графа является следующий: {1,5,6}.
Задание. Доказать, что если - минимальное вершинное покрытие данного графа, то все вершины, не вошедшие в , образуют максимальную клику этого графа.
Так, клика {1,5,6} максимальная. Следовательно, множество {2,3,4} – есть минимальное вершинное покрытие.
Доказательство. Пусть В – множество вершин и Е – множество ребер графа и К –максимальная клика. Нужно показать, что разность В\К есть минимальное покрытие. Допустим, что это не так. Скажем, вершина х принадлежит действительно минимальному покрытию и не попала в В\К. Включим ее в В\К . Тогда она “выбьет” из В\К скажем вершины z,w как лишние (избыточные). Эти вершины z,w покрывают какие-то ребра. Но тогда и вершина х должна покрывать эти же ребра. Кроме того, ясно, что нет ребра (z,w). (Почему ?). Приходим к простому выводу, что вершина х должна быть концевой для всех таких ребер, другими концами которых являются z,w . Следовательно, вершины z,w могут быть включены в максимальную клику.
ЗАДАЧА о Гамильтоновом цикле.
Спрашивается, имеется ли в графе путь, проходящий через каждую вершину ровно один раз, который бы завершался в той же вершине, из которой он стартует.
ЗАДАЧА 3-ВЫПОЛНИМОСТЬ NP-полна.
Задача 3-ВЫПОЛНИМОСТЬ – это задача ВЫПОЛНИМОСТЬ, которая использует 3 литеры в записи каждого дизъюнкта. Покажем, как свести обычную задачу ВЫПОЛНИМОСТЬ к задаче 3-ВЫПОЛНИМОСТЬ.
Возьмем например дизъюнкт:
Этот дизъюнкт (как и любой подобный ему) можно заменить трехлитерными дизъюнктами, введя новые булевские переменные:
Легко доказать, что представленные два трехлитерных дизъюнкта эквивалентны исходному четырехлитерному.