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

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

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

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, видим, что оставшийся граф G₁ связен и содержит ровно две нечетных вершины v и u. Согласно следствию #2 из теоремы 1 граф G₁ имеет эйлеров путь P из v в u. Поскольку удаление первого ребра инцидентного u пути P либо не нарушает связности G₁, либо происходит удаление вершины u и оставшийся граф G₂ связен с двумя нечетными вершинами, то отсюда получаем, что описанное выше построение всегда возможно на каждом шаге. (Если 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[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	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. Матрица М ^[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).