algorithm - 寻找对偶欧拉

Question

需要一些关于如何定义图形是否为对偶欧拉的指导？这意味着有 2 个电路，如果组合起来收集我们访问图中的所有边。我可以假设该图包含欧拉回路。

编辑

@Evgeny Kluev 的回答

如果该图包含至少一个具有 4 条或更多条边的顶点，则该图具有 2 个欧拉循环。

Answer 1

这是关于 DUAL EULERIAN GRAPHS WITH APPLICATIONS TO VLSI DESIGN 的论文作者:安德烈·弗里曼。

欧拉电路\路径:

• 一个无向图有一个欧拉环当且仅当每个顶点的度数都是偶数，并且所有非零度数的顶点都属于一个连通分量。

• 当且仅当无向图的所有顶点都具有偶数度时，它才能分解为边不相交的循环。因此，当且仅当图可以分解为边不相交的环并且其非零度顶点属于单个连通分量时，图才具有欧拉环。

• 一个无向图有欧拉轨迹当且仅当至多两个顶点的度数为奇数，并且所有非零度数的顶点都属于一个连通分量。

• 有向图具有欧拉环当且仅当每个顶点的入度和出度都相等，并且所有非零度的顶点都属于一个强连通分量。等价地，有向图具有欧拉环当且仅当它可以分解为边不相交的有向环并且其所有非零度的顶点都属于单个强连通分量。

• 有向图有欧拉轨迹当且仅当至多一个顶点有 (out-degree) − (in-degree) = 1，至多一个顶点有 (in-degree) − (out- degree) = 1，所有其他顶点的入度和出度都相等，并且其所有非零度的顶点都属于底层无向图的单个连通分量。

来源:Wikipedia:Eulerian Path