2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 как найти Эйлерову цепь в графе
Сообщение16.04.2018, 16:06 


14/09/16
57
Дан граф:

Изображение

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

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

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

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

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

 Профиль  
                  
 
 Re: как найти Эйлерову цепь в графе
Сообщение16.04.2018, 16:30 
Заслуженный участник


10/01/16
1689
Форда? Флойда? Уоршелла?

 Профиль  
                  
 
 Re: как найти Эйлерову цепь в графе
Сообщение16.04.2018, 16:34 


14/09/16
57
DeBill в сообщении #1304804 писал(а):
Форда? Флойда? Уоршелла?


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

-- 16.04.2018, 17:53 --

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

Изображение

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

 Профиль  
                  
 
 Re: как найти Эйлерову цепь в графе
Сообщение16.04.2018, 16:54 
Заслуженный участник


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

 Профиль  
                  
 
 Re: как найти Эйлерову цепь в графе
Сообщение16.04.2018, 17:00 


14/09/16
57
DeBill в сообщении #1304813 писал(а):
Это я прикалываюсь. Неудачно..


это я понял ;)

DeBill в сообщении #1304813 писал(а):
А чем Вам не нравится "тупой алгоритм"


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

 Профиль  
                  
 
 Re: как найти Эйлерову цепь в графе
Сообщение16.04.2018, 17:03 
Заслуженный участник


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

 Профиль  
                  
 
 Re: как найти Эйлерову цепь в графе
Сообщение16.04.2018, 17:14 


14/09/16
57
DeBill в сообщении #1304820 писал(а):
Ну, он сразу берет быка за рога, и старткет с вершины нечетной степени.
А алгоритм хорош, лучше моего "тупого" - по "памяти".


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

 Профиль  
                  
 
 Re: как найти Эйлерову цепь в графе
Сообщение16.04.2018, 18:59 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group