1. 定义

1.1 欧拉通路 & 欧拉回路

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

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

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

1.2 欧拉图 & 半欧拉图

  • 具有欧拉回路的图称为欧拉图

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

2. 性质

  • 无向图 GG 是欧拉图当且仅当 GG 是连通图且没有奇度顶点。

  • 无向图 GG 是半欧拉图当且仅当 GG 是连通的且恰有两个奇度顶点。

  • 有向图 DD 是欧拉图当且仅当 DD 是强连通的且每个顶点的入度等于出度。

  • 有向图 DD 是半欧拉图当且仅当 DD 是单连通的且恰有两个奇度顶点,其中一个顶点的入度比出度大 1 ,另一个顶点的出度比入度大 1 ,而其余顶点的入度等于出度。

  • 无向图 GG 是非平凡的欧拉图当且仅当 GG 是连通的且是若干个边不重的圈的并。