一.引入
哥尼斯堡七桥问题。
河中有两座小岛，7座桥，问：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。
答案是怎么走都不能满足。
二.定义：
1.欧拉回路：经过每条边一次且仅一次的回路。
2.欧拉路径：经过每条边一次且仅一次的路径。
3.欧拉图：存在欧拉回路的图。
4.半欧拉图：存在欧拉路径但不存在欧拉回路的图。
三.定理
假设图 \(G\) 不存在孤立点。
无向图
定理1：无向图 \(G\) 为欧拉图，当且仅当 \(G\) 为连通图切所有顶点的度为偶数。
推论1：无向图 \(G\) 为半欧拉图，当且仅当 \(G\) 为连通图且除了两个顶点的度为奇数之外，其他所有顶点的度为偶数。
存在欧拉路径的充分必要条件：度数为奇数的点只能有0或2个。
有向图
定理2：有向图 \(G\) 为欧拉图，当且仅当 \(G\) 的基图（忽略边的方向得到的无向图）连通，且所有顶点的入度等于出度。
推论2：有向图 \(G\) 为半欧拉图，当且仅当 \(G\) 的基图连通，且存在顶点 \(u\) 的入度比出度大1，\(v\) 的入度比出度小1，其他所有顶点的入度等于出度。
存在欧拉路径的充分必要条件：要么所有点的出度均等于入度；要么除了两个点之外，其余所有点的出度等于入度，剩余两个点：一个满足出度比入度多1（起点），另一个满足入度比出度多1（终点）。