- •Оглавление
- •Предисловие
- •1. Теоретико‑множественные основания дисциплины
- •1.1. Понятия и аксиомы теории множеств
- •1.2. Декартовы произведения, отношения и отношение эквивалентности
- •1.3. Понятия образа, прообраза, функции и отображения на конечном множестве. Аксиома выделения.
- •1.4. Аксиомы степени и бесконечности. Мощности и кардинальные числа множеств
- •1.5. Счетные и континуальные множества
- •1.6. Ординалы и трансфиниты. Аксиома выбора и континуум‑гипотеза
- •2. Основы математической логики
- •2.1. Высказывания и функции на высказываниях
- •2.2. Операции математической логики
- •2.3. Понятие формулы и свойства операций
- •2.4. Разложения булевых функций. Принцип двойственности. Совершенные нормальные формы.
- •2.5. Понятие полноты системы булевых функций
- •2.5. Исчисление предикатов
- •2.6. Введение в методы теории доказательств
- •1 Если X a,
- •0 Если X a.
- •1 Если X a,
- •0 Если X a.
- •3. Комбинаторика
- •3.1. Размещения
- •3.2. Размещения без повторений
- •3.3. Перестановки, подстановки и их свойства
- •3.4. Сочетания, структура соединений
- •3.5. Свойства биномиальных коэффициентов
- •Структура соединений
- •3.6. Понятие производящей функции
- •3.7. Соединения с повторениями
- •3.8. Разбиения множеств
- •3.9. Разбиения чисел
- •3.10. Композиции чисел
- •4. Основы теории графов
- •4.1. Основные понятия и определения
- •4.2. Графы и бинарные отношения
- •4.3. Понятие изоморфизма и изоморфизм плоских графов
- •4.4. Степени вершин графа
- •4.5. Представление графов матрицами
- •4.6. Представление графов списками инцидентности. Оценка пространственной сложности алгоритмов.
- •4.7. Маршруты, цепи, циклы и связность
- •4.7. Эйлеровы циклы и цепи
- •4.9. Гамильтоновы циклы. Оценка временной сложности алгоритмов
- •4.10. Деревья
- •4.11. Раскраска вершин и теорема Шеннона об информационной емкости графа
- •4.12. Раскраска ребер графа и теоремы о хроматическом классе
- •Ответы и решения
- •Список литературы
4.9. Гамильтоновы циклы. Оценка временной сложности алгоритмов
Цикл на графе G называется гамильтоновым, если соответствующая ему последовательность ребер содержит каждую вершину графа G в точности один раз.
Аналогично вводится понятие гамильтонова контура на ориентированном графе.
Примеры гамильтонового цикла и графа, для которого такого цикла не существует представлены на рисунке 4.12.
а) v1 б) v1
v2 v4 v5 v2 v4 v5
v3
v3
Рисунок 4.12
На рисунке 4.12 а) направление одного из гамильтоновых циклов отмечено стрелками. Соответствующий гамильтонов цикл представлен последовательностью ребер {(v1, v4), ( v4, v5), (v5, v3), (v3, v2), (v2, v1)}. Можно заметить, что ребро (v4, v3) в этом цикле не используется. Этот факт указывает на то, что в гамильтоновом цикле могут участвовать не все ребра графа. Существенным в цикле данного типа является наличие всех вершин графа. В связи с этим, в случаях, когда нет кратных ребер, гамильтонов цикл записывают последовательностью вершин. Так в рассмотренном примере гамильтонов цикл можно представить следующей последовательностью вершин: [v1, v4, v5, v3, v2]. Нетрудно заметить, что при такой записи каждый гамильтонов цикл должен соответствовать некоторой допустимой перестановке всех вершин графа. Ясно, что одному и тому же графу можно поставить в соответствие некоторое множество гамильтоновых циклов. Пример на рисунке 4.12 б) иллюстрирует случай, когда это множество пусто, поскольку вершина v4 необходимо должна быть повторена дважды.
Укажем некоторые задачи, интерпретация которых состоит в необходимости построения гамильтоновых циклов.
Задача о шахматном коне. Можно ли начиная с произвольного поля на шахматной доске ходить конем в такой последовательности, чтобы пройти через все поля и вернуться в исходное?
Задача о званом обеде. Обед накрыт на круглом столе. Среди приглашенных некоторые являются друзьями. При каких условиях можно рассадить всех так, чтобы по обе стороны от каждого из присутствующих сидели его друзья?
Задача о коммивояжере. Коммивояжер должен объездить все n городов. Для того, чтобы сократить свои расходы он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат.
В настоящее время не получено необходимых и достаточных условий существования для гамильтоновых циклов.
С другой стороны, существует очевидный алгоритм, который казалось бы можно применить к решению любой задачи о гамильтоновом цикле: генерируем все перестановки вершин и проверяем, какая из них является гамильтоновым циклом. Всех перестановок, очевидно, будет n!
Оценим временную сложность этого алгоритма. Она вводится аналогично рассмотренной в 4.6. Под временной характеристикой сложности алгоритма понимают асимптотическую оценку О(f(n1, n2, …nk)) требуемого времени работы компьютера в зависимости от мощностей n1, n2, …, nk множеств исходных данных при неограниченном увеличении этих мощностей. Поскольку компьютеры могут обладать различной производительностью, то оценка временных затрат может быть выражена в количестве элементарных операций: сложений, умножений или других операций, выполняемых компьютером и принятых за основу.
Легко видеть, что ограничением применения предложенного выше метода является то, что для его реализации потребуется О(nn!) вычислительных операций (n операций на каждую из n! перестановок). Так, если n = 20 и каждый элементарный шаг компьютера выполняется за 10-7 с, то решение задачи о построении гамильтонова цикла займет порядка 20*20!48*1018 операций или 45*1011 с, что составляет порядка 1500 веков.
Проблема существования гамильтонового цикла принадлежит к классу так называемых NP‑полных задач. Это широкий класс задач, для которых не известен алгоритм полиномиальной сложности их решения, то есть алгоритм с числом шагов, ограниченных полиномом от размерности задачи. Задача же построения гамильтонового цикла, как указано выше, в максимальном случае решается алгоритмом факториальной сложности.
Для того, чтобы убедиться в том, что значения nn! растут быстрее, чем значения произвольного многочлена, покажем, что они растут быстрее, чем значения показательной функции, начиная с некоторого достаточно большого значения n.
Для этого рассмотрим варианту
xn = cn / nn!, с > 1.
Нетрудно заметить, что
xn+1 = xnc / (n + 1).
Поэтому, как только n + 1 > c эта варианта становится убывающей, а поскольку она ограничена нулем, то предел ее также есть нуль.
Для решения NP‑полных задач известен метод, позволяющий сократить число шагов, сводя задачу от факториальной к экспоненциальной сложности. Этот метод известен под названием «backtracing» или «алгоритм с возвратами». Его суть в применении к задаче построения гамильтоновых циклов состоит в следующем.
Будем искать решение в виде последовательности вершин v1, v2, …, vn, начиная от корневой вершины v1. Имея частичное решение v1, v2,…, vi, i < n, пытаемся найти такое допустимое значение vi + 1, относительно которого можно предположить, что оно может расширить частичное решение до v1, v2,…, vi + 1. Если такое предположение возможно, то vi + 1 включается в частичное решение и процесс продолжается. Если никакая вершина не может претендовать на vi + 1, то следует возврат на шаг к vi - 1, а vi из данного частичного решения исключается. Процесс поиска нового допустимого значения продолжается, начиная с vi - 1. Когда vn найдено, отмечают v1, v2, …, vn как решение.
Если поставлена задача отыскания всех решений, то попытка получения каждого нового решения осуществляется возвратом на шаг от vn в предположении, что решение как бы получено не было. Таким образом, отыскивается множество всех решений, которое, в частности, оказывается пустым, если гамильтонова цикла на графе не существует.
Из описания алгоритма с возвратами видно, что задача построения всех гамильтоновых циклов на графе G может быть решена путем сопоставления исходному графу некоторого другого графа G, построенного из частично пересекающихся цепей v1, v2, …, vi, (i n). Подмножество G, состоящее из цепей v1, v2, …, vn, таких что vn смежна с v1 на G представляет множество решений задачи. Граф G называется соотнесенным графом.
Рассмотрим решение задачи о коммивояжере на примере графа G, представленного на рисунке 4.13. Имеем пять пунктов V = {1, 2, 3, 4, 5}. Стоимость доставки информации из пункта i в пункт j представлена числами над ребрами графа. Требуется, используя компьютерную сеть, моделируемую данным графом, обеспечить перекличку пунктов (например, фирм, принадлежащих одной корпорации и т.д.), начиная из пункта 1. Для решения поставленной задачи построим гамильтонов цикл минимальной стоимости передачи информации, либо несколько таких циклов в случае их одинаковой стоимости.
Задачу будем решать в два этапа. Вначале построим все гамильтоновы циклы из пункта 1. Для этого применим алгоритм с возвратами. Затем на множестве полученных циклов выберем циклы минимальной длины.
Построение цепей графа G применением алгоритма с возвратами поясняется рисунком 4.13 справа. На этом рисунке цепи, соответствующие гамильтоновым циклам, выделены жирными линиями.
Всего имеем четыре гамильтоновых цикла:
{1, 2, 3, 5, 4, 1}
{1, 2, 5, 3, 4, 1},
{1, 4, 3, 5, 2, 1},
{1, 4, 5, 3, 2, 1}.
Стоимости передачи информации каждым из этих циклов вычисляются ниже:
9+10+2+2+6 = 29,
9+8+2+5+6 = 30,
6+5+2+8+9 = 30,
6+2+2+10+9 = 29.
Решению поставленной задачи отвечают гамильтоновы циклы a) и d).
Можно показать, что алгоритмы с возвратами имеют вычислительную сложность О(сn), где c > 1 — константа, определяемая свойствами присоединенного графа. Такое быстродействие при больших n значительно выше, чем в случае применения алгоритмов факториальной сложности. Например, возвращаясь к рассмотренному выше примеру оценки быстродействия алгоритма с возвратами при n = 20 видим, что в случае, когда с = 2 (граф G двоичное дерево)
G G
2 1
(9) (10) 2 4
3 5 3 5
(8)
4 5 3 4 2 5 2 3
1 5 (2 ) 3
(2) 1 5 4 4 1 3 1 5 2 1 3 2
(6) (5)
4 1 1 1 1
Рисунок 4.13
имеем всего 220 или порядка 106 вычислительных операций. На любом современном компьютере это практически не займет времени. Однако, при увеличении размерности задачи всего лишь в несколько раз снова возникают проблемы реального времени. Это способствует развитию новых идей построения гамильтоновых циклов.