graph-theory - 一个无向图可以有多个欧拉环吗？

Question

我知道我的问题更多是关于图表而不是编程，但是，我喜欢这里非常活跃的社区，你们可能会使用图表。

所以在这里我想知道一个无向图的欧拉循环的集合是否可以包含多个。

谢谢

Answer 1

该循环称为欧拉循环，当且仅当它包含所有边时，每条边恰好一次。这意味着欧拉循环只能因边缘的顺序而有所不同（我建议将边缘的循环排列排除在琐碎的选项之外）。

使用 Fleury 的算法可以找到欧拉循环：简而言之，随心所欲地移动（扔掉你继续前进的边缘），但在整个组件完成之前不要过桥。“桥”是边缘，它是不同图形组件之间唯一剩余的方式。

所提出的算法非常古老且众所周知，所以我不会证明它的正确性。

现在，很明显存在包含许多不同欧拉循环的图。

Answer 2

是的，他们经常这样做。看看这个例子，它包含多个分离的边缘圆 - 你可以从它们构建许多不同的欧拉圆：

_{取自德语维基百科，由 Chin tin tin 创建}