МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Эйлеровы и гамильтоновы графы

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

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

    Дагестанский Государственный Университет

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

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

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

    Выполнил:

    Студент 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. Задачи связанные с поиском гамильтоновых циклов 12

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    §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 v[pic]V {произвольная вершина}

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

    while S?Ш do

    vS {v — верхний элемент стека}

    if Г[v]=Ш then

    vS {положить 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. Некоторые родственные задачи

    Сразу же укажем ряд вопросов, связанных с тем, имеется ли в

    неориентированном графе эйлеров цикл. Например,

    Каково наименьшее число цепей или циклов необходимое для того, чтобы каждое

    ребро графа G содержалось точно в одной цепи или в одном цикле? Очевидно,

    что если G имеет эйлеров цикл или эйлерову цепь, то ответом будет число

    один.

    Ребрам графа G приписаны положительные веса. Требуется найти цикл,

    проходящий через каждое ребро графа G по крайней мере один раз и такой, что

    для него общий вес (а именно сумма величин njc(aj), где число nj

    показывает, сколько раз проходилось ребро aj, а c(aj) — вес ребра)

    минимален. Очевидно, что если G содержит эйлеров цикл, то любой такой цикл

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

    цикла равен тогда

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

    ее решение имеет много потенциальных приложений, как например:

    Сбор мусора. Рассмотрим проблему сбора домашнего мусора. Допустим, что

    определенный район города обслуживается единственной машиной. Ребра графа G

    представляют дороги, а вершины — пересечения дорог. Величина c(aj) — вес

    ребра — будет соответствовать длине дороги. Тогда проблема сбора мусора в

    данном районе сводится к нахождению цикла в графе G, проходящего по каждому

    ребру G по крайней мере один раз. Требуется найти цикл с наименьшим

    километражем.

    Доставка молока или почты. Еще две задачи, когда требуется определить

    маршрут, проходящий хотя бы один раз по каждой из улиц, возникают при

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

    минимизирующего общий километраж (или время, стоимость и т.д.).

    Проверка электрических, телефонных или железнодорожных линий. Проблема

    инспектирования распределенных систем (лишь некоторые из которых названы

    выше) связана с непременным требованием проверки всех «компонент». Поэтому

    она также является проблемой типа 2) или близка к ней.

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

    Рассмотрим неориентированный граф G(X,A). Среди вершин из X некоторые

    вершины (скажем из множества X+) будут иметь четные степени, а остальные

    (из множества X-=X\X+) — нечетные степени. Сумма степеней di всех вершин

    xi[pic]X равна удвоенному числу ребер в A (т.к. каждое ребро добавляет по

    единице к степеням двух его концевых вершин) и поэтому равна четному числу

    2m. Следовательно, и так как первая сумма четна, то вторая сумма

    также четна. Но все di в последней сумме нечетны, значит число |X-| вершин

    нечетной степени четно.

    Пусть M — множество таких цепей (скажем ?ij) в G между концевыми

    вершинами xi и xj [pic] X-, что никакие две цепи не имеют одинаковых

    конечных вершин, т.е. цепи соединяют различные пары вершин из X- и

    покрывают все вершины множества X-. Число цепей ?ij в M равно 1/2|X-| и

    всегда цело, если конечно оно определено. Предположим теперь, что все

    ребра, образующие цепь ?ij, теперь удвоены (добавлены искусственные ребра).

    Так поступаем с каждой цепью ?ij[pic]M и полученный граф обозначим через 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 [pic] X-. Это автоматически

    приводит к выполнению условия прохождения вершины xr. Аналогично обстоит

    дело для всех других вершин xi [pic] X-. Это значит что все множество M

    цепей из G, определенное выше, должно проходится дважды, и так как отсюда

    вытекает, что каждое ребро из G-(M) должно проходиться один раз, то теорема

    доказана.

    Алгоритм решения задачи китайского почтальона немедленно следует из

    доказанной теоремы, так как все, что для этого необходимо, состоит в

    нахождении множества цепей M* (цепного паросочетания для множества вершин

    нечетной степени), дающего наименьший дополнительный вес. Цикл наименьшего

    Страницы: 1, 2, 3, 4


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.