VPF::Эйлеров путь - Форум программистов

zim22

Дата 19.9.2009, 10:47 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: нет
Всего: 69

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

Цитата

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

Я же думаю, что этот граф не содержит эйлеров путь, т.к. он не проходит через ребро 1-2. Я прав?
Т.к. согласно википедии

Цитата

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

Это сообщение отредактировал(а) zim22 - 19.9.2009, 11:25

--------------------

C++ FAQ Lite

Olympian

Дата 19.9.2009, 12:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 7.11.2006

Репутация: 1
Всего: 1

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

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

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »