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

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

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

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

(xi, xj) О E* если Построение эйлерова цикла. Алгоритм Форда и Уоршелла.

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

Положим

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

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

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

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

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

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

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

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

ЛИТЕРАТУРА


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

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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: