欧拉回路及欧拉图

定义：

欧拉回路：图G的一个回路，如果恰通过图G的每一条边，则该回路称为欧拉回路，具有欧拉回路的图称为欧拉图。欧拉图就是从图上的一点出发，经过所有边且只能经过一次，最终回到起点的路径。

欧拉通路：即可以不回到起点，但是必须经过每一条边，且只能一次。也叫"一笔画"问题。

性质：

一个欧拉回路，删掉一个点，仍然是一个欧拉回路。从一个欧拉回路拖走一个小欧拉回路，结果也是一个欧拉回路。

判定：

欧拉回路：

1、 图G是连通的，不能有孤立点存在。

2、 对于无向图来说度数为奇数的点个数为0，因为必须有一点进有一点出，才能保证每条边恰好经过一次；对于有向图来说每个点的入度必须等于出度。

欧拉通路：

1、 图G是连通的，无孤立点存在。

2、 对于无向图来说，度数为奇数的的点可以有2个或者0个，并且这两个奇点其中一个为起点另外一个为终点。对于有向图来说，可以存在两个点，其入度不等于出度，其中一个入度比出度大1，为路径的起点；另外一个出度比入度大1，为路径的终点。