Лекции Просолупов

Доказательство. Для любого графа мы можем построить дополнение и для него

решить задачу о вершинном покрытии.

Задача о вершинном покрытии принадлежит классу , так как, если ответ на задачу "да" и нам дано множество из вершин, мы можем перебрав все ребра убедиться, что хотя бы один конец каждого из них лежит в данном множестве.

Следствие 84.6 . Задача о вершинном покрытии является -полной задачей.

§85. -полнота задачи о гамильтоновом цикле

Как мы помним, гамильтонов цикл — это цикл проходящий через каждую вершину графа ровно один раз.

Задача 85.1 (ГАМИЛЬТОНОВ ЦИКЛ). Дан граф = ( , ). Существует ли в графе гамильтонов цикл?

Теорема 85.2 . ВЕРШИННОЕ ПОКРЫТИЕ ГАМИЛЬТОНОВ ЦИКЛ.

Доказательство этой теоремы приводить не будем из-за его излишней громоздкости. Задача о гамильтоновом цикле лежит в классе , поскольку, если ответ на

задачу "да" и нам дана последовательность прохождения ребер графа , мы можем

за полиномиальное время убедиться, что вершины могут быть пройдены в этой последовательности по ребрам .

Следствие 85.3 . Задача о гамильтоновом цикле является -полной задачей.

§86. -полнота задачи коммивояжера

Итак, задачу коммивояжера строго можно сформулировать следующим образом:

Задача 86.1 . Дан полный граф = и весовая функция :

: ( ) → R+.

Требуется найти гамильтонов цикл минимального веса.

Существует также общий (несимметричный) случай задачи.

Задача 86.2 . Пусть = ( , ) — полный ориентированный граф (то

есть, ориентированный граф в которым любые две вершины связаны двумя противоположно направленными дугами). Весовая функция сопоставляет каждой дуге положительное число. Противоположные ребра могут иметь различный вес.

Требуется найти гамильтонов контур минимального веса.

Переформулируем симметричную задачу в форме распознавания:

211

Задача 86.3 (ЗАДАЧА КОММИВОЯЖЕРА). Дан полный граф = , весовая функция и целое число > 0. Существует ли в гамильтонов цикл веса не превосходящего .

Задача коммивояжера принадлежит к классу . Действительно, если нам

известен ответ на задачу "да" и в качестве доказательства перечислены ребра, составляющие гамильтонов цикл, мы можем за полиномиальное время проверить, правда ли его вес не превосходит .

Теорема 86.4 . ГАМИЛЬТОНОВ ЦИКЛ ЗАДАЧА КОММИВОЯЖЕРА.

Доказательство. Пусть 1 = ( , 1) граф, в котором необходимо проверить наличие гамильтонова цикла. Построим полный граф 2 = ( , 2) на том же множестве вершин и определим весовую функцию : 2 → R следующим образом:

Нетрудно видеть, что в 1 есть гамильтонов цикл задача коммивояжера с графом 2 и границей = | | имеет ответ "да".

Следствие 86.5 . Задача коммивояжера является -полной задачей.

Следствие 86.6 . Несимметричная задача коммивояжера является -полной

задачей, так как симметричная задача коммивояжера является ее частным случаем.

§87. Алгоритм дерева для решения задачи коммивояжера

Как мы помним, для -полных задач не известно полиномиальных алгоритмов

решения и поиск их представляется крайне сложной задачей.

Алгоритм дерева — это приближенный алгоритм решения, который применим к особому случаю симметричной задачи коммивояжера с неравенством треугольника:

Пусть = ( , ) — полный неориентированный граф с вершинами, : →

R+ — функция весов ребер:

При изложении алгоритма дерева нам понадобится два вспомогательных алгоритмов: построение минимального остовного дерева (алгоритм 79.3) и алгоритм построения эйлерова цикла.

Алгоритм построения эйлерова цикла напоминает структуру доказательства теоремы 78.4 (рис. 69).

Пусть дан эйлеров граф = ( , ) — связный и все вершины имеют четные степени.

212

Рисунок 69: Поиск эйлерова цикла

Алгоритм 87.1 (Эйлеров цикл). function ЭЙЛЕР ( , 1) {

if (deg ( 1) = 0) {

ЭЙЛЕР=( 1) } else {

1.Построить любой цикл ( 1, 2, ..., , 1), который ни по одному ребру не проходит дважды: ( , +1) ̸= ( , +1), 1 ≤ , ≤

2.= − ( 1, 2) − ( 2, 3) − · · · − ( , 1)

3. ЭЙЛЕР = (ЭЙЛЕР( , 1), ЭЙЛЕР( , 2), ..., ЭЙЛЕР( , ), 1)

}

}

main() {

= любая вершина из

= ЭЙЛЕР( , )

}

Замечание 87.2 . Заметим, что параметр в функции ЭЙЛЕР передается по ссылке. То есть все преобразования, которые производятся с графом в функции, (удаление ребер) оказывают воздействие на исходный объект . Таким образом,

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

213

На вход алгоритма дерева подается граф = ( , ) и функция весов : → R+, удовлетворяющая неравенству треугольника.

Алгоритм 87.3 (Алгоритм дерева).

1)= ( , 1) = минимальное остовное дерево ( )

2)= мультиграф, полученный удвоением ребер из дерева

3)= ЭЙЛЕР( , ), где — любая из вершин

4)= (Удалить повторение вершин ( ), )

Пример 87.4 . Предположим, что мы уже нашли минимальное остовное дерево и удвоили его ребра. Результат изображен на рисунке 70. В ходе выполнения

Рисунок 70: Построение гамильтонова цикла с помощью алгоритма дерева

алгоритма поиска эйлерова цикла мы могли обойти сначала, скажем, цикл (1,8,1). Тогда искомый цикл должен получиться в результате вызова функций в выражении

= (ЭЙЛЕР(H,1), ЭЙЛЕР(H,8), 1).

Вершина 1 к этому моменту уже имеет степень 0, так что ЭЙЛЕР(H,1) =

(1).

ЭЙЛЕР(H,8) может найти, например, цикл (8, 2, 3, 2, 8). В этом случае мы выполним вызов (ЭЙЛЕР(H,8),ЭЙЛЕР(H,2),ЭЙЛЕР(H,3),ЭЙЛЕР(H,2),8). Здесь ЭЙЛЕР(H,2) = (2) в обоих случаях. ЭЙЛЕР(H,8) мог бы оказаться (8,7,8), а ЭЙЛЕР(H,3) — (3,6,5,4,5,6,3).

Подставим эти циклы в (ЭЙЛЕР(H,8),ЭЙЛЕР(H,2),ЭЙЛЕР(H,3),ЭЙЛЕР(H,2),8)

214

и получим (8,7,8,2,3,6,5,4,5,6,3,2,8). Теперь подставим это вместо ЭЙЛЕР(H,8) в выражение для и получим эйлеров цикл

= (1, 8, 7, 8, 2, 3, 6, 5, 4, 5, 6, 3, 2, 8, 1).

После удаления повторений в этой последовательности получим цикл =

(1, 8, 7, 2, 3, 6, 5, 4, 1) (на рисунке 70 изображен пунктирной линией). Это и есть результат работы алгоритма — гамильтонов цикл.

Степень близости веса полученного в алгоритме дерева гамильтонова цикла к оптимальному описывает следующая теорема.

Определение 87.5 . Пусть ( , ) — оптимальный цикл в задаче коммивояжера для графа и функции весов , а ( , ) — маршрут полученный с помощью некоторого алгоритма .

Тогда алгоритм называют -приближенным, если

( ( , )) − ( ( , )) ≤ .

( ( , ))

Утверждение 87.6 . Алгоритм дерева — 1-приближенный алгоритм.

Доказательство. Пусть ( , ) — оптимальный цикл в задаче коммивояжера для графа и функции весов , а ( , ) — маршрут полученный с помощью алгоритма дерева. Так же предполагаем, что функция удовлетворяет

неравенству треугольника (39), поскольку в прочих случаях алгоритм дерева мы не рассматриваем.

При удалении любого ребра из ( , ) мы получим некоторое остовное дерево графа . Вес этого дерева не может быть меньше веса минимального остовного дерева графа . Следовательно,

( ( , )) > ( ( , ) − ) ≥ ( ).

Сдругой стороны ( , ) построен из с удвоенными ребрами (и весом 2 ( )) заменой последовательностей ребер ( 1 , 2 ), ( 2 , 3 ), ..., ( −1 , ) на одиночные ребра ( 1 , ). Из неравенства треугольника следует, что

(( 1 , 2 )) + (( 2 , 3 )) + · · · + (( −1 , )) ≥ (( 1 , )).

Таким образом, ( ( , )) ≤ 2 · ( ) и следовательно ( ( , )) ≤ 2 ·

( ( , )).

Осталось записать формулу для -приближенности.

215

Хотя мы и не можем пока ответить на вопрос о существовании полиномиального алгоритма для -трудной задачи коммивояжера, в некоторых случаях (при

выполнении дополнительных условий) мы можем находить приближенное решение этой задачи.

216

Литература

[1]Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы.: Учеб. пособие. — М.: Издательский дом “Вильямс”, 2000.

[2]Вирт Н. Алгоритмы и структуры данных. — СПб.: Невский Диалект, 2001.

[3]Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике: Учеб. пособие. — 3-е изд., перераб. — М.: Физматлит, 2005.

[4]Грэхэм Р., Кнут Д., Паташник О. Конкретная математика. — М.: Мир, 1998.

[5]Ерусалимский Я.М. Дискретная математика: Теория, задачи, приложения — 8-е изд., — М.: Вузовская книга, 2006.

[6]Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. — 5-е изд., исправл. — М.: Физматлит, 2004.

[7]Нефедов В.Н., Осипова В.А. Курс дискретной математики. — М.: Изд-во МАИ, 1992.

[8]Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: теория и практика — М.: Мир, 1980.

[9]Хаггарти Р. Дискретная математика для программистов — М.: Техносфера, 2005.

[10]Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов /Под ред. В.А. Садовничего. — 4-е изд., стер. — М.: Высш. шк.; 2003.

217