Каталог Рефератов - Эйлеровы циклы. Задача "Китайского почтальона"

	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

Эйлеровы циклы. Задача "Китайского почтальона"

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

Рисунок 3а

Рисунок 3б

1.3 Разрезы

Понятие разреза очень тесно связано с понятием цикла и определяется так.

Определение. Если вершины неориентированного графа разбиты на два множества и (где , и является дополнением Хо относительно X), то множество ребер графа одни концевые вершины которых лежат в а другие в называется разрезом графа G.Множество ребер разрева может быть представлено множеством вершин пары . Таким образом, остовный подграф ,полученный ив удалением ребер, принадлежащих разрезу, является несвязным графом, состоящим но крайней мере из двух компонент.

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

Теорема Если -- остов неориентированного врафа , то фундаментальный разрез, определяемый ребром из Т, образован и теми ребрами из не принадлежащими которые после добавления к дают фундаментальные циклы, содержащие

1.4 Матрицы циклов и разрезов
Пусть -- остов неориентированного графа. Матрицей фундаментальных циклов графа называется матрица состоящая из строк и столбцов, в которой равно 1, если ребро принадлежит циклу и равно 0 в противном случае. Если ребра, не принадлежащие дереву Т, пронумеровать последовательно от 1 до а ребра дерева T пронумеровать от до , то матрица циклов будет иметь вид ,где - единичная матрица. Это объясняется тем, что каждый цикл содержит одно, и только одно ребро, не принадлежащее остову Т, и циклы всегда можно пронумеровать по числу принадлежащих им внеостовных ребер, вследствие чего все единицы в первой подматрице матрицы лежат на диагонали.

Матрица фундаментальных разрезов определяется аналогично -- как матрица строками и столбцами, где есть 1, если ребро - принадлежит разрезу и 0 в противном случае. При той же самой нумерации ребер, что и выше, матрица К имеет вид так как теперь каждый фундаментальный разрез содержит одно, и только одно ребро из ребер дерева Т.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

whileS?Ш do

v<S; v>S {v -- верхний элемент стека}

ifГ[v]=Ш then

v<S;

yieldv

else

selectuГ[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).

1.6 Алгоритм для задачи китайского почтальона
В случае, когда веса всех ребер равны единице, задачу китайского почтальона рассмотрели Беллман и Кук с использованием динамического программирования. Более общую задачу. когда веса ребер произвольны, сформулировали и решили как задачу о паросочетании (с частной задачей о кратчайшей цепи) Эдмондс, Эдмондс и Джонсон , Басакер и Саати и Кристофидес.

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

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

Пусть -- множество таких цепей (скажем ) в между концевыми вершинами и ) что никакие две цепи не имеют одинаковых конечных вершин, т. е. цепи соединяют различные пары вершин из и покрывают все вершины множества .Число цепей в в равно , а как было показано выше, ,всегда четно, следовательно, это число всегда целое, если, конечно, оно определено. Предположим теперь, что все ребра, образующие цепь , добавлены к в качестве искусственной параллельной цепи, причем эти ребра остаются в графе . Это означает, прежде всего, что все ребра из , образующие цепь ,теперь удвоены. Так поступаем с каждой цепью и полученный -граф обозначим через Так как некоторые ребра из могут входить более чем в одну цепь ·, то некоторые ребра из могут быть (после того как добавлены все «новые» цепи) утроены, учетверены и т. д. Теперь мы можем рассмотреть следующую теорему.

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

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

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

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

Шаг 2. Найдем то цепное паросочетание для множества которое дает наименьший вес (в соответствии с матрицей весов ).

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

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.