как найти Эйлерову цепь в графе

[tremor]

Дан граф:



Судя по теории данный граф имеет в себе Эйлерову цепь, так как вершины 4 и 6 имеют нечетную степень, так вот вопрос как найти эту цепь? Какой алгоритм применять?

как я понимаю:

нам надо пройти от 4х до 6ти охватив все ребра

- выбираем любую вершину с нечетной степенью (скажем 4)
- из этой вершины выходим в направлении вершины с наименьшим номером (2)
- выбранное ребро не является перешейком так что ведущая вершина теперь 2
- из 2 идем в 1, выбранное ребро не перешеек, значит ведущая вершина 1

и тд, но что-то я не уверен что это верные рассуждения

[DeBill]

Форда? Флойда? Уоршелла?

[tremor]

DeBill в сообщении #1304804 писал(а):

Форда? Флойда? Уоршелла?

оно же вроде необходимо для отыскания кратчайшего пути от вершины к вершине?

-- 16.04.2018, 17:53 --

Вот выдержка из метод.указания по графам, описывающая поиск Эйлеровой цепи, опираюсь на нее, не могу понять пункт 4



свои соображения описал в первом посте идя именно по этому алгоритму

[DeBill]

Это я прикалываюсь. Неудачно..
А чем Вам не нравится "тупой алгоритм": Гуляем по графу пока есть куда гулять. Полученный цикл выбрасываем. С оставшимся делаем то же самое - пока не кончатся ребра.
Теперь - синтез цикла: повторяем первый маршрут, пока не встретится какой-нить побочный цикл: тогда его сразу и обойдем. И т.д...
Для Пути: надо добавить искусственное ребро 6-4, и проделать то же. Ну. а на этапе синтеза, первым назовем цикл, содержащий добавленное ребро, и будем его обходить стартуя из 4.
Для Вашего примера, напр, это дает: циклы 4216 - 4, 043520, 31563. (6-4 - искусственное)
Синтез: 42 - 043502 -1 -5631 -6

[tremor]

DeBill в сообщении #1304813 писал(а):

Это я прикалываюсь. Неудачно..

это я понял ;)

DeBill в сообщении #1304813 писал(а):

А чем Вам не нравится "тупой алгоритм"

А я выше привел выдержку из методички, которую писал наш дискретчик, он что-то не упомянает про добавление ребер ни тут ни далее (этим алгоритмом он описывает поиск именно цепи)

[DeBill]

Ну, он сразу берет быка за рога, и старткет с вершины нечетной степени.
А алгоритм хорош, лучше моего "тупого" - по "памяти".

[tremor]

DeBill в сообщении #1304820 писал(а):

Ну, он сразу берет быка за рога, и старткет с вершины нечетной степени.
А алгоритм хорош, лучше моего "тупого" - по "памяти".

Я просто не совсем понимаю где-то видимо, я думал, мы идем каждый раз из текущей вершины в следующую вершину с минимальным номером, и если из вершины (или в вершину) в которую пришли входит или исходит еще какое-то непройденное ребро. то мы эту вершину делаем ведущей и идем в следующую вершину с минимальным номером, но я так в тупик зашел, а весь граф не обошел :(

[arseniiv]

Просто поищите другое описание того же алгоритма, если это непонятно. Вообще же есть более эффективный алгоритм, линейный по числу рёбер.