Xreferat.com » Рефераты по информатике и программированию » Эйлеровы и гамильтоновы графы

Эйлеровы и гамильтоновы графы

Министерство народного образования Республики Дагестан
Дагестанский Государственный Университет

Курсовая работа


Программирование задач на графах

Гамильтоновы и эйлеровы циклы


Выполнил:

Студент 4 курса 4 гр. МФ

Цургулов Алил Гасанович

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

Якубов А. 3.


Махачкала, 2003 год

Содержание

Содержание 2

Введение 4

Глава 1. Эйлеровы циклы 4

§1. Основные понятия и определения 5

§2. Критерий существования эйлерова цикла 5

§3. Алгоритмы построения эйлерова цикла 6

§4. Некоторые родственные задачи 8

§5. Задача китайского почтальона 9

Глава 2. Гамильтоновы циклы 11

§1. Основные понятия и определения 11

§2. Условия существования гамильтонова цикла 11

§3. Задачи связанные с поиском гамильтоновых циклов 13

§4. Методы построения гамильтоновых циклов в графе. 15

§5. Алгебраический метод построения гамильтоновых циклов 15

§6. Метод перебора Робертса и Флореса 16

§8. Улучшение метода Робертса и Флореса 18

§9. Мультицепной метод 19

§10. Сравнение методов поиска гамильтоновых циклов 21

Глава 3. Задача коммивояжера 23

§1. Общее описание 24

§2. “Жадный” алгоритм решения ЗК 26

§3. “Деревянный” алгоритм решения ЗК 27

§4. Метод лексикографического перебора 29

§5. Метод ветвей и границ решения ЗК 30

§6. Применение алгоритма Дейкстры к решению ЗК 35

§7. Метод выпуклого многоугольника для решения ЗК 35

§8. Генетические алгоритмы 37

§9. Применение генетических алгоритмов 39

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

Введение


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

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

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

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

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

Глава 1. Эйлеровы циклы


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

Задача возникла из предложенной Эйлеру головоломки, получившей название "проблема кенигсбергских мостов". Река Прегель, протекающая через Калининград (прежде город назывался Кенигсбергом), омывает два острова. Берега реки связаны с островами так,



как это показано на рисунке.

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

§1. Основные понятия и определения


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

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

Выберем в качестве вершин графа берега реки, а в качестве ребер - мосты, их соединяющие. После этого задача становится оче­видной: требование неосуществимо - чтобы его выполнить, число дуг, приходящих к каждой вершине, должно быть четным. В самом деле, по­скольку по одному мосту нельзя проходить дважды, каждому входу на берег должен соответствовать выход.

§2. Критерий существования эйлерова цикла


Что необходимо, чтобы в графе существовал эйлеров цикл? Во-первых, граф должен быть связанным: для любых двух вершин должен существовать путь, их соединяющий. Во-вторых, для неориентирован­ных графов число ребер в каждой вершине должно быть четным. На са­мом деле этого оказывается достаточно.

Теорема 1. Чтобы в связанном неориентированном графе G существовал эйлеров цикл, необходимо и достаточно, чтобы число вершин нечетной степени было четным.

Доказательство.

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

Достаточность. Пусть G — связный неориентированный граф, все вершины которого имеют четную степень. Начнем путь из некоторой произвольной вершины x0 и пойдем по некоторому ранее не использованному ребру к следующей вершине, и так до тех пор, пока не вернемся в вершину x0 и не замкнем цикл. Если все ребра окажутся использованными, то нужный эйлеров цикл построен. Если же некоторые ребра не использованы, то пусть Ф — только что построенный цикл. Так как граф G связен, то цикл Ф должен проходить через некоторую вершину, скажем xi, являющуюся конечной вершиной какого-либо до сих пор не использованного ребра. Если удалить все ребра, принадлежащие Ф, то в оставшемся графе все вершины по-прежнему будут иметь четную степень, так как в цикле Ф должно быть четное число ребер (0 является четным числом), инцидентных каждой вершине.

Начиная теперь с xi, получаем цикл Ф’, начинающийся и оканчивающийся в xi. Если все оставшиеся ранее ребра использованы для цикла Ф’, то процесс окончен. Нужный эйлеров цикл будет образован частью цикла Ф от вершины x0 до xi, затем циклом Ф’ и, наконец, частью цикла Ф от вершины xi до x0. Если же все еще остались неиспользованные ребра, то объединение построенных выше циклов Ф и Ф’ дает новый цикл Ф. Мы снова можем найти вершину xj, принадлежащую циклу и являющуюся концевой вершиной некоторого неиспользованного ребра. Затем мы можем приступить к построению нового цикла Ф’, начинавшегося в xj, и так до тех пор, пока не будут использованы все ребра и не будет получен таким образом эйлеров цикл Ф. Это доказывает теорему.

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

Следствие #1.

Для связного эйлерова графа G множество ребер можно разбить на простые циклы.

Следствие #2.

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


§3. Алгоритмы построения эйлерова цикла


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

Алгоритм построения эйлерова цикла в эйлеровом графе.

Вход: эйлеров граф G(V,E), заданный матрицей смежности. Для простоты укажем, что Г[v]— множество вершин, смежных с вершиной v.

Выход: последовательность вершин эйлерова цикла.


S:=Ш {стек для хранения вершин}

select vV {произвольная вершина}

v→S {положить v в стек S}

while S≠Ш do

v←S; v→S {v — верхний элемент стека}

if Г[v]=Ш then

v←S;

yield v

else

select uГ[v] {взять первую вершину из списка смежности}

u→S {положить u в стек}

Г[v]:=Г[v]{u}; Г[u]:=Г[u]{v} {удалить ребро (v,u)}

end if

end while


Обоснование алгоритма.

Принцип действия этого алгоритма заключается в следующем. Начиная с произвольной вершины, строим путь, удаляя ребра и запоминая вершины в стеке, до тех пор пока множество смежности очередной вершины не окажется пустым, что означает, что путь удлинить нельзя. Заметим, что при этом мы с необходимостью придем в ту вершину, с которой начали. В противном случае это означало бы, что вершина v имеет нечетную степень, что невозможно по условию. Таким образом, из графа были удалены ребра цикла, а вершины цикла были сохранены в стеке S. Заметим, что при этом степени всех вершин остались четными. Далее вершина v выводится в качестве первой вершины эйлерова цикла, а процесс продолжается, начиная с вершины, стоящей на вершине стека.

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

Алгоритм Флёри:

1. Начиная с любой вершины v присваиваем ребру vu номер 1. Вычеркиваем это ребро из списка ребер и переходим к вершине u.

2. Пусть w - вершина, в которую мы пришли в результате выполнения 1 шага алгоритма и k - номер, присвоенный очередному ребру на этом шаге. Выбираем произвольное ребро инцидентное вершине w, причем мост выбираем только в крайнем случае, если других возможностей выбора ребра не существует. Присваиваем ребру номер k+1 и вычеркиваем его. Процесс длится до тех пор, пока все ребра не вычеркнут.

Примечание: Мостом называется ребро, удаление которого лишает данный граф связности, т.е. увеличивает число компонент связности.

Пример:

П
риведем теперь строгое обоснование корректности алгоритма Флёри построения эйлерового цикла в данном эйлеровом графе.

Теорема 2. Пусть G(V,E) — эйлеров граф. Тогда следующая процедура всегда возможна и приводит к построению эйлерова цикла графа G(V,E).

Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая при этом следующие правила:

  1. Стираем ребра по мере их прохождения (вместе с изолированными вершинами, которые при этом образуются);

  2. На каждом шаге идем по мосту только в том случае, когда нет других возможностей.

Доказательство.

Убедимся сначала, что указанная процедура может быть выполнена на каждом этапе. Пусть мы достигли некоторой вершины v, начав с вершины u, v ≠ u. Удалив ребра пути из v в u, видим, что оставшийся граф G1 связен и содержит ровно две нечетных вершины v и u. Согласно следствию #2 из теоремы 1 граф G1 имеет эйлеров путь P из v в u. Поскольку удаление первого ребра инцидентного u пути P либо не нарушает связности G1, либо происходит удаление вершины u и оставшийся граф G2 связен с двумя нечетными вершинами, то отсюда получаем, что описанное выше построение всегда возможно на каждом шаге. (Если v = u, то доказательство не меняется, если имеются ребра, инцидентные u). Покажем, что данная процедура приводит к эйлерову пути. Действительно, в G не может быть ребер, оставшихся не пройденными после использования последнего ребра, инцидентного u, поскольку в противном случае удаление ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию 2).

§4. Некоторые родственные задачи


Сразу же укажем ряд вопросов, связанных с тем, имеется ли в неориентированном графе эйлеров цикл. Например,

  1. Каково наименьшее число цепей или циклов необходимое для того, чтобы каждое ребро графа G содержалось точно в одной цепи или в одном цикле? Очевидно, что если G имеет эйлеров цикл или эйлерову цепь, то ответом будет число один.

  2. Р
    ебрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин njc(aj), где число nj показывает, сколько раз проходилось ребро aj, а c(aj) — вес ребра) минимален. Очевидно, что если G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится по один раз и вес этого цикла равен тогда

Сформулированная выше задача 2) называется задачей китайского почтальона, и ее решение имеет много потенциальных приложений, как например:

    1. Сбор мусора. Рассмотрим проблему сбора домашнего мусора. Допустим, что определенный район города обслуживается единственной машиной. Ребра графа G представляют дороги, а вершины — пересечения дорог. Величина c(aj) — вес ребра — будет соответствовать длине дороги. Тогда проблема сбора мусора в данном районе сводится к нахождению цикла в графе G, проходящего по каждому ребру G по крайней мере один раз. Требуется найти цикл с наименьшим километражем.

    2. Доставка молока или почты. Еще две задачи, когда требуется определить маршрут, проходящий хотя бы один раз по каждой из улиц, возникают при доставке молока или почты. Здесь задача состоит в нахождении маршрута, минимизирующего общий километраж (или время, стоимость и т.д.).

    3. Проверка электрических, телефонных или железнодорожных линий. Проблема инспектирования распределенных систем (лишь некоторые из которых названы выше) связана с непременным требованием проверки всех «компонент». Поэтому она также является проблемой типа 2) или близка к ней.


§5. Задача китайского почтальона


Р
ассмотрим неориентированный граф G(X,A). Среди вершин из X некоторые вершины (скажем из множества X+) будут иметь четные степени, а остальные (из множества X-=XX+) — нечетные степени. Сумма степеней di всех вершин xiX равна удвоенному числу ребер в A (т.к. каждое ребро добавляет по единице к степеням двух его концевых вершин) и поэтому равна четному числу 2m. Следовательно, и так как первая сумма четна, то вторая сумма также четна. Но все di в последней сумме нечетны, значит число |X-| вершин нечетной степени четно.

Пусть M — множество таких цепей (скажем μij) в G между концевыми вершинами xi и xj X-, что никакие две цепи не имеют одинаковых конечных вершин, т.е. цепи соединяют различные пары вершин из X- и покрывают все вершины множества X-. Число цепей μij в M равно 1/2|X-| и всегда цело, если конечно оно определено. Предположим теперь, что все ребра, образующие цепь μij, теперь удвоены (добавлены искусственные ребра). Так поступаем с каждой цепью μijM и полученный граф обозначим через G-(M). Так как некоторые ребра из G могут входить более чем в одну цепь μij, то некоторые ребра из G-(M) могут быть (после того как добавлены все «новые» цепи μij) утроены, учетверены и т.д.

Теорема 3. Для любого цикла, проходящего по G, можно выбрать множество M, для которого граф G-(M) имеет эйлеров цикл, соответствующий первоначально взятому циклу в графе G. Это соответствие таково, что если цикл проходит по ребру (xi, xj) из G l раз, то в G-(M) существует l ребер (одно реальное и l-1 искусственных) между xi и xj, каждое из которых проходится ровно один раз эйлеровым циклом из G-(M). Справедливо и обратное утверждение.

Доказательство.

Если цикл проходит по графу G, то по крайней мере одно ребро, инцидентное каждой вершине xi нечетной степени, должно проходиться дважды. (Ребро, проходимое дважды, можно рассматривать как два параллельных ребра — одно реальное и одно искусственное — и каждое из них проходится один раз). Пусть это ребро (xi, xk). В случае нечетности степени dk вершины xk графа G добавление искусственного ребра прежде всего сделает dk четным, и значит только ребро (xi,xk) нужно будет проходить дважды, если ограничиться рассмотрением лишь вершин xi и xk. В случае когда dk четно, добавление искусственного ребра сделает dk нечетным, а второе ребро выходящее из xk должно быть пройдено дважды (т.е. добавляется еще одно искусственное ребро). Такая ситуация сохраняется до тех пор, пока не встретится вершина нечетной степени, о чем говорилось выше. Следовательно, чтобы удовлетворить условию возвращения в вершину xi, нужно дважды пройти всю цепь из xi в некоторую другую вершину нечетной степени xr X-. Это автоматически приводит к выполнению условия прохождения вершины xr. Аналогично обстоит дело для всех других вершин xi X-. Это значит что все множество M цепей из G, определенное выше, должно проходится дважды, и так как отсюда вытекает, что каждое ребро из G-(M) должно проходиться один раз, то теорема доказана.

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

Описание алгоритма решения задачи китайского почтальона:
  1. Пусть [cij] — матрица весов ребер G. Используя алгоритм нахождения кратчайшей цепи, образуем |X-|*|X-| — матрицу D=[dij], где dij — вес цепи наименьшего веса, идущей из некоторой вершины xiX- в другую вершину xjX-.

  2. Найдем то цепное паросочетание M* для множества X-, которое дает наименьший вес (в соответствии с матрицей весов D). Это можно сделать эффективно с помощью алгоритма минимального паросочетания.

  3. Если вершина xα сочетается с другой вершиной xβ, то определим цепь μαβ наименьшего веса (из xα в xβ), соответствующую весу dαβ, делая шаг 1. Добавим искусственные ребра в G, соответствующие ребрам из μαβ, и проделаем это для всех других цепей из множества M*, в результате чего получится граф G-(M*).

  4. Сумма весов всех ребер графа G-(M*), найденная с использованием матрицы [cij] (вес искусственного ребра берется равным весу параллельного ему реального ребра), равна минимальному весу цикла, проходящего по G. При этом число прохождений цикла по ребру (xi,xj) равно общему числу параллельных ребер между xi и xj в G-(M*).

Покажем, что указанный выше алгоритм строит минимальный цикл. Для этого следует заметить, что поскольку на шаге 2 мы используем минимальное паросочетание, никакие две кратчайшие цепи μij и μpq при таком паросочетании (скажем, идущие из xi в xj и из xp в xq) не могут иметь общего ребра. Если бы они имели общее ребро (xa, xb), то сочетание вершин xi и xq (использующее подцепи от xi к xb и от xb к xq) и сочетание пары вершин xp и xj (использующее подцепи от xp к xa и от xa к xj) давало бы общее паросочетание веса 2cab, меньшего чем вес первоначального паросочетания, что противоречит предположению о минимальности исходного паросочетания. Следовательно, граф G-(M*)не должен содержать более двух параллельных ребер между любыми двумя вершинами, т.е. оптимальный цикл не проходит ни по какому ребру графа G более чем два раза.


Глава 2. Гамильтоновы циклы


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


§1. Основные понятия и определения


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

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

Замечание.

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

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


§2. Условия существования гамильтонова цикла


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

Теорема Дирака. Если в графе G(V,E) c n вершинами (n ≥ 3) выполняется условие d(v) ≥ n/2 для любого vV, то граф G является гамильтоновым.

Доказательство.

От противного. Пусть G — не гамильтонов. Добавим к G минимальное количество новых вершин u1, … ,un, соединяя их со всеми вершинами G так, чтобы G’:= G + u1 + … + un был гамильтоновым.

Пусть v, u1, w, … ,v — гамильтонов цикл в графе G’, причем vG, u1G’, u1G. Такая пара вершин v и u1 в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда wG, w {u1,…,un}, иначе вершина u1 была бы не нужна. Более того, вершина v несмежна с вершиной w, иначе вершина u1 была бы не нужна.

Далее, если в цикле v,u1,w, … ,u’,w’, … ,v есть вершина w’, смежная с вершиной w, то вершина v’ несмежна с вершиной v, так как иначе можно было бы построить гамильтонов цикл v,v’, … ,w,w’, … ,v без вершины u1, взяв последовательность вершин w, … ,v’ в обратном порядке. Отсюда следует, что число вершин графа G’, не смежных с v, не менее числа вершин, смежных с w. Но для любой вершины w графа G d(w) ≥ p/2+n по построению, в том числе d(v) ≥ p/2+n. Общее число вершин (смежных и не смежных с v) составляет n+p-1. Таким образом, имеем:

n+p-1 = d(v)+d(V) ≥ d(w)+d(v) ≥ p/2+n+p/2+n = 2n+p.

Следовательно, 0 ≥ n+1, что противоречит тому, что n > 0.

Теорема Оре. Если число вершин графа G(V,E) n ≥ 3 и

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: