欧拉图

1. 定义

1.1 欧拉通路 & 欧拉回路

• 通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的通路称作欧拉通路。
• 通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的回路称作欧拉回路。

【注】规定平凡图是欧拉图。

1.2 欧拉图 & 半欧拉图

• 具有欧拉回路的图称为欧拉图。
• 具有欧拉通路而无欧拉回路的图称作半欧拉图。

2. 性质

• 无向图 G 是欧拉图当且仅当 G 是连通图且没有奇度顶点。
• 无向图 G 是半欧拉图当且仅当 G 是连通的且恰有两个奇度顶点。
• 有向图 D 是欧拉图当且仅当 D是强连通的且每个顶点的入度等于出度。
• 有向图 D 是半欧拉图当且仅当 D是单连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大 1 ，另一个顶点的出度比入度大 1 ，而其余顶点的入度等于出度。
• 无向图 G 是非平凡的欧拉图当且仅当 G是连通的且是若干个边不重的圈的并。