Реферат: Построение эйлерова цикла. Алгоритм Форда и Уоршелла

Транзитивным называется отношение, удовлетворяющее следующему условию: если (x, y) Î E и (y, z) Î E, то (x, z) Î E для всех  x, y, z Î X. Отметим, что бинарное отношение можно однозначно представить орграфом G(X, E). Теперь для произвольного отношения Е определим новое отношение Е* следующим образом

E* = (x, y).

Легко проверить, что Е* - транзитивное отношение. Кроме того, Е* является наименьшим транзитивным отношением на Х в том смысле, что для произвольного транзитивного отношения F É E выполняется E* É F. Отно­ше­ние Е* называется транзитивным замыканием отношения Е.

Если отношение Е представить в виде графа G(X, E) в котором каждая дуга имеет вес 1, то транзитивное замыкание Е* можно вычислить с помощью алгоритма Флойда. При этом надо учесть, что

                                  (xi, xj) Î E* если .

Для большего удобства алгоритм Флойда в этом случае можно моди­фи­ци­ровать следующим образом.

Положим

                                    .

Вместо (3) запишем

                                 ,

где    Ú – дизъюнкция (логическое сложение),

Ù – конъюнкция (логическое умножение).

После завершения работы алгоритма будем иметь

Модифицированный таким образом алгоритм называется алгоритмом Уоршелла.

ЛИТЕРАТУРА

1.  Баканович Э.А., Волорова Н.А., Епихин А.В. Дискретная математика:. В 2-х ч..– Мн.: БГУИР, 2000.– 52 с., ил. 14 ISBN 985-444-057-5 (ч. 2).

2.  Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации. М. Иза-во МГТУ им. Н.Э.Баумана, 2003.

3.  Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).