Может ли неориентированный граф иметь более одного цикла Эйлера?

Question

Я знаю, что мой вопрос скорее о графиках, чем о программировании, но мне нравится сообщество, которое очень активно, и вы, ребята, можете работать с графиками.

Итак, мне интересно, может ли множество циклов эйлеров неориентированного графа содержать более одного.

Thanks

Answer 1

Цикл называется эйлеровым, если он содержит все ребра, ровно один раз каждый. Это означает, что эйлеровы циклы могут отличаться только по порядку края (я предлагаю исключить циклические перестановки края как тривиальный вариант).

Можно найти цикл Эйлера, используя алгоритм Флери: короче, двигайтесь как хотите (выбрасывая края, которые вы продолжали), но не пересекайте мост, пока весь компонент не будет выполнен. «Мост» - это край, который является единственным оставшимся способом между различными компонентами графа.

Предлагаемый алгоритм довольно старый и хорошо известный, поэтому я не буду доказывать его правильность.

Теперь должно быть совершенно очевидно, что существуют графики, содержащие много различных циклов Эйлера.

Answer 2

Да, они часто это делают. Посмотрите на этот пример, который содержит несколько разобщенный край кругов - вы можете построить много различных эйлерова кругов из них:

_{Взятые из German Wikipedia, созданный Chin олова олова}