欧拉图

定义

通过图（无向图或有向图）中所有边且每边仅通过一次通路称为欧拉通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。

定理

欧拉道路

• 无向图：当且仅当该图为连通图且所有顶点的度数为偶数，或者除了两个度数为奇数外其余的全是偶
  数。
• 有向图：当且仅当该图为连通图（忽略边的方向）且所有顶点 出度等于入度 或者一个顶点 入度比出度小1（把它当作起点） ，另一个顶点 入度比出度大1（把它当作终点），其他顶点 出度等于入度。

欧拉回路

• 无向图：当且仅当该图为连通图且每个顶点的度数都是偶数。
• 有向图：当且仅当该图为连通图且每个顶点的入度等于出度。