работа по Теория информационных процессов и систем на тему Алгоритм Фаулкса и его приложения

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

по Теория информационных процессов и систем

на тему Алгоритм Фаулкса и его приложения

Ватиант № 15

Семестр № 7

Преподаватель Александров О. Е.

Студент гр. ИТ-44018д Рагозин В. П.

Номер зачётной книжки: 17421412

Екатеринбург

2008

Домашнее задание по Теория информационных процессов и систем

№ записи в книге регистрации 17421412

Преподаватель Александров О. Е.

Студент Рагозин В. П. группа № ИТ-44018д

Деканат ФДО____________

Содержание:

Номер зачётной книжки: 17421412 1

Введение. 3

Эйлеровы циклы 4

Основные понятия и определения 4

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

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

Алгоритм Фаулкса 9

Вводное описание Гамильтоновых циклов 13

Основные понятия и определения 13

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

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

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

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

Введение.

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

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

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

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

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

Эйлеровы циклы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вход: эйлеров граф 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).

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

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

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

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

Убедимся сначала, что указанная процедура может быть выполнена на каждом этапе. Пусть мы достигли некоторой вершины 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, поскольку в противном случае удаление ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию

Алгоритм Фаулкса

Рассмотрим шесть операций: A, B, C, D, E, F, между которыми существуют следующие соотношения:

А<B B/<C C<D E<D F<D

A<D B<D F<E

A><F B><E

B><F

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

	A	B	C	D	E	F
A	1	1	0	1	0	1
B	0	1	1	1	1	1
C	0	0	1	1	0	0
D	0	0	0	1	0	0
E	0	1	0	1	1	0
F	1	1	0	1	1	1

B

A C

F D

E

Рис. 16.4

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

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

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

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

Так, в настоящем случае строка и столбец D могут быть заранее опущены; мы получаем матрицу М 1 . образуем элементарные произведения элементов какой-нибудь строки (например, строки А) на элементы какого-нибудь столбца (скажем С), как если бы мы хотели вычислить М 1[2].

	A	B	C	D	E	F
A	1	1	0	1	0	1
B	0	1	1	1	1	1
C	0	0	1	1	0	0
D	0	0	0	1	0	0
E	0	1	0	1	1	0
F	1	1	0	1	1	1

Элементарные произведения в порядке их следования таковы:

а) 1*0=0; б) 1*1=1; в) 0*1-0; г) 0*0=0; д) 1*0=0. проследим, что они означают. Пусть мы хотим отправиться из А в С.

Тогда:

а) не существует прямого пути из А в С;

б) существует прямой путь, идущий из А в B и путь из B в C; следовательно имеется путь длины 2 из А в С;

в) не существует прямого пути из А в С;

г) нет прямого пути из А в Е и так же нет пути из Е в С;

д) есть прямой путь из А в F, но нет ни какого пути из F в С.

Таким образом, мы получили все пути из А в С длины меньшей или равной 2.

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

Таким образом, мы приходим к матрице М 1[2] , все единицы которой обозначают существование путей единицы меньшей или равной 2, а нули - их отсутствие.

		A	B	C	E	F
	A	1	1	1	1	1
	B	1	1	1	1	1
M^1[2]=	C	0	0	1	0	0
	E	0	1	1	1	1
	F	e; padding-top: 0in; padding-bottom: 0in; padding-left: 0.08in; padding-right: 0in;">1	1	1	1	1

Из матрицы М 1[2] мы заключаем, что точка С необходимо является крайней точкой гамильтонова пути, если таковой существует. Опять отбрасываем строку и столбец С, откуда получаем.

		A	B	E	F
	A	1	1	1	1
M^1[2]=	B	1	1	1	1
	E	0	1	1	1
	F	1	1	1	1

		A	B	E	F
	A	1	1	1	1
M^1[3]=	B	1	1	1	1
	E	1	1	1	1
	F	1	1	1	1

Точно так же, как мы, вычислив М 11[2] , нашли пути длины меньшей или равной 2, найдем пути длины меньшей или равной 3, вычисляя М 11[3] . Матрица М 1[8] М 11[3] содержит только единицы; это доказывает существование путей длины меньшей или равной 3 между всеми точками ABEF, взятыми по две.

В частности, можно идти из Е в А через B и F. Вычислять М 11[4] которая, очевидно, содержит только единицы, уже нет смысла.

Вообще, когда вычисляют последовательные символические степени М, можно остановиться на том n для которого

М(n+1) = М (n)

ибо это означает, что в М не существует пути, длина которого превышает n. Матрица М [3] , полученная возвращением на место строк и столбцов C и D, может быть перегруппирована таким образом, чтобы все нули были расположены под главной диагональю, а единицы – над ней.

Квадратные матрицы, состоящие из единиц опирающихся на главную диагональ, образуют классы эквивалентности относительно закона: точка Х связана с точкой Y и обратно.

	A	B	C	D	E	F
A	1	1	1	1	1	1
B	1	1	1	1	1	1
C	1	1	1	1	1	1
D	1	1	1	1	1	1
E	0	0	0	0	1	1
F	0	0	0	0	0	1

Например, А связанная с Е через B или же через F и B; Е связанная с А через В и F. Мы упростим исходный граф, разбив его на классы. Определение единственного гамельтонова пути AFEBCD становится совсем простым (рис 16.5).

Рис. 16.5

Возвращаясь к задаче Фреголи, которую мы решили выше, мы устанавливаем, что вычисление М [2] дало нам пути длины <= 2, вычисление М [4] - пути длины <= 4. Если бы мы вычислили М [7] , мы имели бы пути длины <= 7; в действительности мы вычислили М [8] , которая дает все пути, ибо каждый путь длины больше 7 проходит два раза через одну точку. Мы констатировали совпадении М [8] и М [4] .

Затем мы нашли классы эквивалентности, представляя М [4] в форме ABDFGCEH; в частности, BDF и EH образуют классы эквивалентности.

Замечание: Очевидно, что когда записывают отношения порядка (как, например, отношения предшествования) в некотором множестве, алгоритм Фаулкса представляет собой один из методов выяснения их совместимости (поскольку не должно существовать цикла). Он позволяет, кроме того, найти все отношения порядка между двумя, которые выводятся из предположений в силу транзитивности отношения порядка (из А<B и В<С следует, что А<С, хотя это отношение не было явно выражено ранее).

Только тогда, когда между точками нет связи виде отношения, можно вводить законно отношение индифферентности ><.

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

Вводное описание Гамильтоновых циклов

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

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

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

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

Следующая схема перебора, использующая обычную технику возвращения, была первоначально предложена Робертсом и Флоресом [2, 3]. Начинают с построения (kЧn) матрицы M = ||m[i][j]||, где элемент m[i][j] есть i-ая вершина (скажем xq), для которой в графе G = (X, Г) существует дуга (xj, xq). Вершины xq в множестве Г(xj) можно упорядочить произвольно, образовав элементы j-ого столбца матрицы M. Число строк k матрицы M будет равно наибольшей полу-степени исхода вершины.

Метод состоит в следующем. Некоторая начальная вершина (скажем xj) выбирается в качестве отправной и образует первый элемент множества S, которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S добавляется первая вершина (например a) в столбце x1. Затем к множеству S добавляется первая возможная вершина (например, вершина b) в столбце a, потом добавляется к S первая возможная вершина (например, вершина c) в столбце b и т. д. Под "возможной" вершиной мы понимаем вершину, ещё ен принадлежащую S. Существую две причины, препятствующие включению некоторой вершины на шаге r в множество S = {x1, a, b, c, …, xr-1, xr}. Или (1) в столбце xr нет возможной вершины, или (2) цепь, определяемая последовательностью вершин в S, имеет длину n-1, т. е. является гамильтоновой цепью. В случае (2) (а) в графе G существует дуга (xr, x1) и поэтому найден гамильтонов цикл, или (б) дуга (xr, x1) не существует и не может быть получен никакой гамильтонов цикл. В случаях (1) и (2б) следует прибегнуть к возвращению, в то время как в случае (2а) можно прекратить поиск и напечатать результат. Возвращение состоит в удалении последней включенной вершины xr из S, после чего остается множество S = {x1, a, b, c, …, xr-1}, и добавлении к S первой возможной вершины, следующей за xr, в столбце xr-1 матрицы M. Если не существует никакой возможной вершины, делается следующий шаг возвращения, и т. д.

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

В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат должен быть перенастроен после того как был произведен продукт pi (но до того как начато производство продукта pj), в зависимости от комбинации (pi,pj). Стоимость перенастройки аппаратуры постоянна и не зависит от производимых продуктов. Предположим, что эти продукты производятся в непрерывном цикле, так что после производства последнего из n продуктов снова возобновляется в том же фиксированном цикле производство первого продукта.

Возникает вопрос о том, может ли быть найдена циклическая последовательность производства продуктов pi (i=1,2,…,n), не требующая перенастройки аппаратуры. Если представить эту задачу в виде ориентированного графа, то ответ на поставленный вопрос зависит от того, имеет ли этот ориентированный граф гамильтонов цикл или нет.

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

Таким образом мы рассмотрим следующие две задачи.

Задача 1. Дан ориентированный граф G, требуется найти в G гамильтонов цикл (или все циклы), если существует хотя бы один такой цикл.

Задача 2. Дан полный ориентированный цикл G, дугам которого приписаны произвольные веса C=[cij], найти такой гамильтонов цикл, который имеет наименьший общий вес. Следует отметить, что если ориентированный граф G неполный, то его можно рассматривать как полный ориентированный граф, приписывая отсутствующим дугам бесконечный вес.

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

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

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

В вышеупомянутом полном ориентированном графе G1 мы можем наверняка найти гамильтонов цикл. Пусть это будет цикл Ф1, и пусть вес самой длинной его дуги равен ?1. Удалив из G1 любую дугу, вес которой не меньше ?1,получим ориентированный граф G2. Найдем в ориентированном графе G2гамильтонов цикл Ф2, и пусть вес его самой длинной дуги равен ?2. Удалим из G2 любую дугу, вес которой не меньше ?2, и так будем продолжать до тех пор, пока не получим ориентированный граф Gm+1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Фm в Gm (с весом ?m) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в Gm+1 следует, что в G1 не существует никакого гамильтонова цикла, не использующего по крайней мере одну дугу с весом, большим или равным ?m.

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

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

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

Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G гамильтонов цикл. Критерии существования, данные выше, представляют теоретический интерес, но являются слишком общими и не пригодны для произвольных графов, встречающихся на практике. Алгебраические методы определения гамильтоновых циклов не могут быть применены с более чем несколькими десятками вершин, так как они требуют слишком большого времени работы и большой памяти компьютера. Более приемлемым является способ Робертса и Флореса, который не предъявляет чрезмерных требований к памяти компьютера, но время в котором зависит экспоненциально от числа вершин в графе. Однако другой неявный метод перебора имеет для большинства типов графов очень небольшой показатель роста времени вычислений в зависимости от числа вершин. Он может быть использован для нахождения гамильтоновых циклов в очень больших графах. Ниже будут описаны алгебраический метод, перебор с возвратами, его улучшение, мультицепной метод.

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

Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин»цепи x1, x2, … ,xk-1, xk определяется как выражение вида x2*x3* … xk-1, не содержащее две концевые вершины x1 и xk. «Модифицированная матрица смежности» B=[?(i,j)] — это (nЧn)- матрица, в которой ?(i,j) — xj, если существует дуга из xi в xj и нуль в противном случае. Предположим теперь, что у нас есть матрица PL = [pL(i ,j)], где pL(i,j) — сумма внутренних произведений всех простых цепей длины L (L?1) между вершинами xi и xj дляxi?xj. Положим pL(i,i)=0 для всех i. Обычное алгебраическое произведение матриц B*PL = P’L+1 = [p’L+1(s,t)] определяется как

т.е. p’L+1(s,t) является суммой внутренних произведений всех цепей из xs вxt длины l+1. Так как все цепи из xk в xt, представленные внутренними произведениями из pL(k,t), являются простыми, то среди цепей, получающихся из указанного выражения, не являются простыми лишь те, внутренние произведения которых в pL(k,t) содержат вершину xs. Таким образом, если изp’L+1(s,t) исключить все слагаемые, содержащие xs (а это можно сделать простой проверкой), то получим pL+1(s,t). Матрица PL+1=[pL+1(s,t)], все диагональные элементы которой равны 0, является тогда матрицей всех простых цепей длины L+1.

Вычисляя затем B*PL+1, находим PL+2 и т.д., пока не будет построена матрица Pn-1, дающая все гамильтоновы цепи (имеющие длину n-1) между всеми парами вершин. Гамильтоновы циклы получаются тогда сразу из цепей в Pn-1 и тех дуг из G, которые соединяют начальную и конечную вершины каждой цепи. С другой стороны, гамильтоновы циклы даются членами внутреннего произведения вершин, стоящими в любой диагональной ячейке матрицы B*Pn-1 (все диагональные элементы этой матрицы одинаковые).

Очевидно, что в качестве начального значения матрицы P (т.е. P1)следует взять матрицу смежности A графа, положив все ее диагональные элементы равными нулю.

Недостатки этого метода совершенно очевидны. В процессе умножения матриц (т.е. когда L увеличивается) каждый элемент матрицы PL будет состоять из все большего числа членов вплоть до некоторого критического значения L, после которого число членов снова начнет уменьшаться. Это происходит вследствие того, что для малых значений L и для графов, обычно встречающихся на практике, число цепей длины L+1, как правило, больше, чем число цепей длины L, а для больших значений L имеет место обратная картина.Кроме того, так как длина каждого члена внутреннего произведения вершин увеличивается на единицу, когда L увеличивается на единицу, то объем памяти, необходимый для хранения матрицы PL, растет очень быстро вплоть до максимума при некотором критическом значении L, после которого этот объем снова начинает уменьшаться. Небольшая модификация вышеприведенного метода позволяет во много раз уменьшить необходимый объем памяти и время вычислений. Так как нас интересуют только гамильтоновы циклы и, как было отмечено выше, они могут быть получены из членов внутреннего произведения любой диагональной ячейки матрицы B*Pn-1, то необходимо знать только элемент pn-1(1,1). При этом на каждом этапе не обязательно вычислять и хранить всю матрицу PL, достаточно лишь найти первый столбец PL. Эта модификация уменьшает необходимый объем памяти и время вычислений в n раз. Однако даже при использовании этой модификации программа для ЭВМ, написанная на языке PL/1, который позволяет построчную обработку литер и переменное распределение памяти, не была способна найти все гамильтоновы циклы в неориентированных графах с более чем примерно 20 вершинами и средним значением степени вершины, большим 4.Использовался компьютер IBM 360/65 с памятью 120 000 байтов. Более того, даже для графа с вышеуказанными «размерами» данный метод использовал фактически весь объем памяти и время вычислений равнялось 1.8 минуты. Не такое уж незначительное время для столь небольшого графа.