寻找对偶欧拉

Question

需要一些关于如何定义图是对偶欧拉的指导吗？这意味着有两个电路，如果组合在一起，我们会访问图中的所有边。我可以假设图包含一个欧拉电路。

编辑

@ Evgeny Kluev答复

如果该图包含至少一个具有4个或多个边的顶点，则该图具有2个Euler圈。

Answer 1

这是一篇关于http://www.wpi.edu/Pubs/ETD/Available/etd-0430103-155731/unrestricted/andre.pdf的论文，作者是安德烈·弗里曼。

欧拉电路\路径：

• 一个无向图具有欧拉圈当且仅当每个顶点都有偶数度，且其所有非零度顶点都属于一个单连通分量。
• 一个无向图可以分解为边不相交圈当且仅当它的所有顶点都有偶数度。因此，图具有欧拉圈当且仅当它可以分解为边-不相交环，且它的非零度顶点属于单个连通分量。
• 无向图有欧拉迹当且仅当至多两个顶点有奇数度，且其所有非零度顶点都属于单个连通分量。
• 有向图具有欧拉圈当且仅当每个顶点的度和出度相等，且其所有非零度顶点都属于单个强连通分量。等价地，有向图具有欧拉圈当且仅当它可以分解为边-不交有向圈，且其所有非零度顶点都属于单个强连通分量。
• 一个有向图有欧拉迹当且仅当一个顶点至多有(出度)−(内度)= 1，最多一个顶点有(内度)−(出度)= 1，其他每个顶点都有度和出度相等，并且它的所有非零度顶点都属于底层无向图的单个连通分量。

来源：维基百科:欧拉之路