Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Эйлеров путь

Автор: zim22 19.9.2009, 10:47

Читаю книгу по алгоритмам (Роберт Седжвик. Фундаментальные алгоритмы на С++. Часть 5. Алгоритмы на графах. стр. 74)
В примечании к (Рис. 17.20. Примеры эйлеровых циклов и цепей)
написано, что

Цитата

Граф, изображенный на рисунке, не содержит эйлерова цикла, однако содержит эйлеров путь 0-2-0-1-3-4-2-3-5-4-6-0-5

http://xmages.net/show.php/492456_Untitled.gif.html
Я же думаю, что этот граф не содержит эйлеров путь, т.к. он не проходит через ребро 1-2. Я прав?
Т.к. согласно http://ru.wikipedia.org/wiki/Эйлеров_цикл

Цитата

Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

Автор: Olympian 19.9.2009, 12:41

Тот путь что указан - врятли является просто путем - "0-2-0-1" а то, как мы вернулись из 2 в 0 не сказано.

Но тут есть эйлеров путь - к примеру : 5-0-1-2-0-6-4-5-3-4-2-3-1