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
1578
Форда? Флойда? Уоршелла?

 Профиль  
                  
 
 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
1578
Это я прикалываюсь. Неудачно..
А чем Вам не нравится "тупой алгоритм": Гуляем по графу пока есть куда гулять. Полученный цикл выбрасываем. С оставшимся делаем то же самое - пока не кончатся ребра.
Теперь - синтез цикла: повторяем первый маршрут, пока не встретится какой-нить побочный цикл: тогда его сразу и обойдем. И т.д...
Для Пути: надо добавить искусственное ребро 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
1578
Ну, он сразу берет быка за рога, и старткет с вершины нечетной степени.
А алгоритм хорош, лучше моего "тупого" - по "памяти".

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


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


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

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


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

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

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



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

Сейчас этот форум просматривают: bayak


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

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