Гамильтоновы графы и сложность отыскания гамильтоновых циклов

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Гамильтоновы графы и сложность отыскания гамильтоновых циклов

Гамильтоновы графы и сложность отыскания гамильтоновых циклов

Федеральное агентство по образованию РФ

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н.Г. ЧЕРНЫШЕВСКОГО

Кафедра геометрии

Гамильтоновы графы и сложность отыскания гамильтоновых циклов

КУРСОВАЯ РАБОТА

Научный руководитель

Старший преподаватель ______________

должн., уч. степень, уч. зван. подпись, дата инициалы, фамилия

Саратов 2010

Содержание

Введение

1. Гамильтоновы графы

1.1 Основные определения и результаты

1.2 Теоремы достаточности гамильтонова графа

2. Методы отыскания гамильтоновых циклов

2.1 Алгебраические методы

2.2 Метод перебора Робертса и Флореса

2.2.1 Улучшение метода Робертса и Флореса

Приложение

Заключение

Список литературы

Введение

Целью моей курсовой работы является:

1. Ознакомление с основными понятиями, связанными с гамильтоновыми графами и циклами.

2. Рассмотреть задачи и методы отыскания гамильтоновых циклов в графах

3. Создание программы для нахождения гамильтоновых циклов.

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

Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер: ,, … , , в которой любые два соседних элемента инцидентны. Если = , то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, ребра) различны, то маршрут называется простой цепью.

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл -- контуром.

1. Гамильтоновы графы

1.1 Основные определения и результаты

Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира.

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

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

Замечание.

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1,…, vp графа G добавить вершины u1, …, up и множество ребер {(vi, ui)} {(ui, vi+1)}.

Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень do(v) по выходящим дугам и di(v) -- по входящим.

В отличии от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки существования гамильтонова цикла оказывается NP-полной. Большинство известных теорем имеет вид: «если граф G имеет достаточное количество ребер, то граф является гамильтоновым». Приведем несколько таких теорем.

1.2 Теоремы достаточности гамильтонова графа

Теорема (Дирак, 1952) 1. Если в простом графе с n ? 3 вершинами p(v) ? n/2 для любой вершины v, то граф G является гамильтоновым.

Замечание Существует несколько доказательств этой широко известной теоремы, здесь мы приводим доказательство Д. Дж. Ньюмана.

Доказательство. Добавим к нашему графу k новых вершин, соединяя каждую из них с каждой вершиной из G. Будем предполагать, что k -- наименьшее число вершин, необходимых для того, чтобы полученный граф Gстал гамильтоновым. Затем, считая, что k > 0, придем к противоречию.

Пусть v>p>w>…>v гамильтонов цикл в графе G, где v, w-- вершины из G, а p-- одна из новых вершин. Тогда w не является смежной с v, так как в противном случае мы могли бы не использовать вершину p, что противоречит минимальности k. Более того, вершина, скажем, w, смежная вершине w, не может непосредственно следовать за вершиной v, смежной вершине v, потому что тогда мы могли бы заменить v>p>w>…>v> w>v на v>v>…>w>w>…>v, перевернув часть цикла, заключенную между w и v. Отсюда следует, что число вершин графа G, не являющихся смежными с w, не меньше числа вершин, смежных с v (то есть равно, по меньшей мере, n/2 + k); с другой стороны, очевидно, что число вершин графа G, смежных с w, тоже равно, по меньшей мере, n/2 + k. А так как ни одна вершина графа Gне может быть одновременно смежной и не смежной вершине w, то общее число вершин графа G, равное n + k, не меньше, чем n + 2k. Это и есть искомое противоречие.

Теорема (Оре) 2. Если число вершин графа G(V, E) n ? 3 и для любых двух несмежных вершин u и v выполняется неравенство:

d(u) + d(v) ? n и (u, v)E, то граф G -- гамильтонов.

Граф G имеет гамильтонов цикл если выполняется одно из следующих условий:

Условие Бонди: из d(vi) ? i и d(vk) ? k => d(vi) + d(vk) ? n (k ? i)

Условие Хватала: из d(vk) ? k ? n/2 => d(vn-k) ? n k.

Далее, известно, что почти все графы гамильтоновы, то есть

где H(p) -- множество гамильтоновых графов с p вершинами, а G(p) -- множество всех графов с p вершинами. Задача отыскания гамильтонова цикла или эквивалентная задача коммивояжера являются практически востребованными, но для нее неизвестен (и, скорее всего не существует) эффективный алгоритм решения.

Пример графа, когда не выполняется условие теоремы Дирака, но граф является гамильтоновым.

N = 8; d(vi) = 3; 3 ? 8/2 = 4 не гамильтонов граф, но существует гамильтонов цикл: M = (1, 2, 3, 4, 5, 6, 7, 8, 1)