欧拉图

概念

• 通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。
• 通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。
• 具有欧拉回路的无向图称为欧拉图。
• 具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图

定理和推论

无向图 G 存在欧拉通路的充要条件是：

G 为连通图，并且 G 仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。

推论 1：

1. 当 G 是仅有两个奇度结点的连通图时，G 的欧拉通路必以此两个结点为端点。
2. 当 G 是无奇度结点的连通图时，G 必有欧拉回路。
3. G 为欧拉图（存在欧拉回路）的充分必要条件是 G 为无奇度结点的连通图。

有向图 D 存在欧拉通路的充要条件是：

D 为有向图，D 的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为 1，另一个顶点的出度与入度之差为-1。

推论 2：

1. 当 D除出、入度之差为 1，-1 的两个顶点之外，其余顶点的出度与入度都相等时，D的有向欧拉通路必以出、入度之差为 1 的顶点作为始点，以出、入度之差为-1 的顶点作为终点。
2. 当 D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。
3. 有向图 D为有向欧拉图的充分必要条件是 D的基图为连通图，并且所有顶点的出、入度都相等。

存在判断

A.判断欧拉通路是否存在的方法

有向图：图连通，有一个顶点出度大入度 1，有一个顶点入度大出度 1，其余都是出度=入度。 无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

B.判断欧拉回路是否存在的方法

有向图：图连通，所有的顶点出度 = 入度。 无向图：图连通，所有顶点都是偶数度。

应用

• 哥尼斯堡七桥问题
• 旋转鼓轮的设计
• 一笔画问题
  • leetcode 332