13.1 欧拉图与中国邮递员问题
1.设G是一个无向图，包含G的每条边的简单道路称为欧拉道路，包含G的每条边的简单回路称为欧拉回路，具有欧拉回路的图称为欧拉图。
2.连通图G是欧拉图，当且仅当G不含奇数度结点。
3.非平凡连通图G含有欧拉道路，当且仅当G最多有两个奇数度结点。
4.连通有向图G含有有向欧拉回路，当且仅当G中每个结点的入度等于出度。连通图G含有有向欧拉道路，当且仅当除最多两个结点外，其余每个结点的入度等于其出度，而这两个结点中的一个结点的入度比其出度多1，另一个结点的入度比其出度少1.
5.构造欧拉回路算法（Fleury算法）：
1).从G中任选一点和与
关联的边
，置
,
.
2).记录s和e，并在G中标记e。设与e关联的另一结点,置
.
3).设从G中删去已标记过的全部k条边后得到的子图为,则
1.当为零图时，算法结束。
2.若在中与s关联的边都不是割边，则任选其中一边e',置e=e',转2).
3.若在中与s关联的边有割边e'且s是
中的一度点，则令e'=e,转2);否则在
中任选一条与s关联的非割边e''，令e=e''，转2).
6.求解无向图的中国邮递员问题算法：
1).若G不含奇度结点，则5介绍的方法构造欧拉回路，就是问题的解。
2).若G含有2k个奇度结点，则先求出其中任何两个结点之间的最短道路，然后再在这些道路之中找到k条道路，使得
①任何和
（i≠j）没有相同的起点和终点。
②在所有满足1)的k条道路的集合中，的长度总和最短。
3).在所有满足1)的k条道路集合中，在原图G中复制的所有出现在这k条道路上的边，设所得的图为G'.
4).造G‘的欧拉回路，即得到中国邮递员问题的解。
