欧拉图

• 欧拉回路：图G的一个回路，如果恰通过图G的每一条边，则该回路称为欧拉回路，具有欧拉回路的图称为欧拉图。欧拉图就是从图上的一点出发，经过所有边且只能经过一次，最终回到起点的路径。
• 欧拉通路：即可以不回到起点，但是必须经过每一条边，且只能一次。也叫”一笔画”问题。
• 基图：基图是针对有向图的说法，是忽略有向图的方向得到的无向图。
• 欧拉图:存在欧拉回路的图。

性质与定理：

定理1:无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。
定理2:有向图G为欧拉图，当且仅当G的基图连通，且所有顶点的入度等于出度。

欧拉回路

判断是否存在欧拉回路

• 1.是否连通
  并查集
• 2.连通度
  奇度的点称为奇点，反之偶点
  有向图 入度和出度
  无向图 入出度

查找欧拉回路路径

• 1.查找结点路径
• 2.查找边路径

欧拉通路

判断是否存在欧拉通路

• 1.是否连通
  并查集
• 2.连通度
  奇度的点称为奇点，反之偶点
  有向图 入度和出度
  无向图 入出度

查找欧拉通路路径

• 1.查找结点路径
• 2.查找边路径