欧拉图(Eulerian Graph)

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

非形式化地讲，欧拉图就是从任意一个点开始都可以一笔画完整个图，半欧拉图必须从某个点开始才能一笔画完整个图。

要判断一个无向图是否为欧拉图或半欧拉图，有以下两个必要条件：

1. 欧拉图：图中所有顶点的度数均为偶数。
2. 半欧拉图：图中恰有两个顶点的度数为奇数。

如果一个无向图满足上述第一个条件，则它是欧拉图。如果满足第二个条件，则它是半欧拉图。

对于有向图（有向欧拉图）：

1. 有向欧拉图：每个顶点的入度等于出度，并且整个图必须是强连通图。这意味着，从图的任意一个顶点，可以沿着有向边到达任何其他顶点。。
2. 有向半欧拉图：图中只有两个顶点的入度与出度不相等，其中一个顶点的出度比入度大1，另一个顶点的入度比出度大1。其余所有顶点的入度必须等于出度。图必须是弱连通的，即在将所有边看作无向边后，图必须连通。