3C12?C1?C2，有C3与C12至少有一个公共顶点，于是C123??Ci也是闭道路，如此
i?1d下去，得证G??Ci?1i是闭道路，故G是欧拉图。证毕。
推论 6·1 设G是非平凡连通图，G有欧拉道路的充要条件是G最多只有两个奇次顶点。
证 必要性 设G有欧拉道路P??0e1?1e2?2?ex?x则此道路中，除起点与终点外，都是偶次顶点，故奇次顶点最多只有两个。
充分性 若G中无奇次顶点，由定理6·1，G有一条闭欧拉道路，若G有奇次顶点，则正好两个奇次顶点u和?，则G?e(e?u?)无奇次顶点，G?e有一条欧拉巡回：
C?ue?e1?1?egu 于是
C?e??e1?1?egu 是G中的一条欧拉道路。证毕。
中国邮递员问题 一、G是欧拉图
此时G的欧拉巡回便是最佳巡回。下面介绍欧拉图中欧拉巡回的两种方法：Fleury算法和Hierholzer算法。
先看Fleury算法，其基本思想是：从任一点出发，每当访问一条边时，先要进行检查，如果可供访问的边不止一条，则应选一条不是未访问边的导出子图的割边作为访问边，直到没有边可选择为止。
定理6·2 若G是欧拉图，则由Flueury算法得出的每一条道路都是欧拉巡回。 证 设G是欧拉图 ?n??0e1?1e2?en?n
是Fleury算法终止时得到的道路，则dG(?n)?0,因此d?(?n)?偶数，从而?n??0,
nn故?n是闭道路。
下面?n包含G的全部边，否则，令S是Gn中非零次顶点的集合，则S??。但?n?S?V?S,令m是使?m?S,?m?1?S的最大整数，因?n终止于S，所以em?1是Gm的
割边（图6—6)，令e是Gm中于?m关联的一边，由算法第二步，e必定为Gm的割边，因此
也是Gm?S?的割边矛盾。证毕。
二、G不是欧拉图
定理 6·3 设G正好有两个奇次顶点u,?,则沿u到?的一条最短路径P*?(u,?)，加重复边得到G*，G*的一条欧拉巡回便是G的最佳巡回。
证 设G?是由G添加重复边而得到的欧拉图，则G??E(G)也只有u,?两个奇次顶点，它们必在G??E(G)的同一分支中，故G??E(G)中存在一条路径P?(u,?)，因此
从而
??(e)?W(P)?W(Pe?G\\E(G)*)
??(e)???(e)
e?G*e?G故G*得一条欧拉巡回是G的最佳巡回。
例6·4 求图（6—9）所示的加权图G的最佳巡回。
图（6—9）所示的图中恰有两个奇次顶点a和c，先求a到c的最短路径P： P=adebc
P的长度为1+2+1+2=6。
例6·6 用最小权对集法求图（6—14）所示的加权图的最佳巡回。
图中有4个奇次顶点：v1,v2,v4,v5,用Floyd算法求出它们之间的距离和最短路径如下： 以v1,v2,v4,v5为顶点，它们之间的距离作为边的权构造完备图G1，如图（6—15）（a)所示。
用一个很大的数比如10减去各边权得修改了边权的图G?1，如图（6—15）（b)所示。 求出G?的最大权匹配： M=｛v1vs,v2v4｝ M也是G1的最小权理想匹配。
沿v1到v5的最短路径：v1v6v5添加重复边于G上，沿v2到v4的最短路径：v2v3v4添加重复边于G上，得到欧拉图G*，见图（6—16）所示。
求出G*的欧拉巡回：
C=v1v2v3v4v9v10v5v6v10v7v8v9v7v1v6v5v4v3v2v8v3v6v1
它即是原图的最佳巡回，其权为W(C)=37+5=42 3 有向欧拉图
定义6·2 设G?(V,E)是弱连通有向图
（1）有向巡回：经过G的每条弧至少一次的有向闭通路称为有向巡回； （2）有向欧拉巡回：经过G的每条弧正好一次的有向巡回称为有向欧拉巡回； （3）有向欧拉图：存在有向欧拉巡回的有向图称为有向欧拉图；
（4）有向欧拉道路：经过G的每条弧正好一次的有向道路称为有向欧拉道路。 定理6·5 G是弱连通有向图，则下述命题等价： （1）G是有向欧拉图。
（2）?v?V(G),d?(?)?d?(?)
n（3）G?然数。
?Ci,其中Ci?1i是有向圈，且E（Ci)?E（Cj)??,1?i?j?n,n为某个自
此定理的证明与第1节中定理6·1证明相似。当证明（2）?（3）时，首先证明G中有有向圈C1，为此，考虑G中的最长有向路径P(u,?)，因d?(?)?d?(?)，所以有一边e， e的尾是?,e的头必在P(u,?)上，于是产生了有向圈。其他推导与定理6·1雷同。证毕。
推论6·5 有向图G有以u1为起点，以u2为终点的有向欧拉道路的充要条件是；G是弱连通有向图，且满足：
?d?(?)?1,??u1??? d(?)??d(?)?1,??u2
???d(?),??u1,u2,??V(G)其证明与推论6·1完全类似。
5 哈米尔顿图
定义6·3 经过图G每个顶点正好一次的路径，称为G的一条哈米尔顿路径，简称H路径。进过G的每个顶点正好一次的圈，称为G的哈米尔顿圈或H圈。含H圈的图称为哈米尔顿图或H图。
例6·9 Kn（n≥3）是哈米尔顿图。但奇数个顶点的二部图不是哈米尔顿图，因为二部图中没有奇圈。埃斯欠尔(Herschel)图（如图（6—24））是11个顶点的二部图，因此它不是H图。
表面看来，哈米尔顿圈与欧拉巡回很相似，但判断一个图是否是H图，要比判断一个图是否E图困难得多。对于E图，已有非常有效且简捷的充分必要的判别定理。但对H图，至今尚未建立起较像样的充要条件，这方面的探索一直在继续。
定理6·7 若G是H图，则?S?V,S??有： 证：设C施G的H圈，则?S?V,S??有 w(C?S)?S
又C?S是G?S的生成子图，所以 w(G?S)?w(C?S)?S 证毕。
引理 6·8 设G是??3的简单，非H图，x,y在G中不相邻，若G?xy是H图，则
dG(x)?dG(y)?v
证 设G不是H图，G?xy是H图，则G?xy的每个H圈都含边xy，于是G中有条H路径P(x,y)??1?2??v(?1?x,?v?y) 令S???ix?i?1?E(G)?，则
S?d(x) 令T???i?iy?E(G)?，则
T?d(y) 因?v?S，且?v?T，所以
?v?S?T，从而S?T?? 下证 S?T?0
否则，存在?i?S?T，，从而x?i?1?E(G),?iy?E(G)，则G含圈?1?2??iy?i?1x，此圈是H圈（见图（6—26）），这与G不是H图矛盾。故
d(x)?d(y)?S?T?S?T??。证毕。
定理6·8 (Dirac1952)若G是??3，且??v2的简单图，则G是H图。
证 若G不是H图，在G的一些不相邻的顶点对之间加边，使G成为最大的非H图显然G不是完备图，且有G?xy是H圈，由引理6·8，G。G中存在不相邻的顶点x,y,，有
dG(x)?dG(y)??
******从而2?(G)??,与?(G*)?即可。证毕。
*?2矛盾。故G是H图。按其H图的次序对A的全部子集排序
定理6·9 x与y是G的两个不相邻的顶点，且d（x）?d(y)?u,则G为H的充要条件是G?xy是H图。
证 必要性显然，只需证充分性。若G?xy是H图，而G不是H图，由引理6·8，应有
d(x)?d(y)?? 这与假设矛盾，故G也是H图。证毕。
定义6·4 将G中次数之和至少为u的不相邻顶点之间添加一边，得到图G，再将G1中次数之和至少为u的不相邻顶点之间添加一边，得到图G2，这样的过程重复直到图Gn没有这样的顶点为止。最终得到的图Gn称为G的闭包，记为C（G）。
定理6·10 简单图G是H的充要条件是C（G）是H图。
推论 6·10 G是u?3的简单图，若C（G）完备，则G是H图。
8 流动推销员问题 定义6·6 在加权图G?(V,E)中
（1）权最小的哈米尔顿圈称为最佳H圈。
（2）经过每个顶点至少一次的权最小闭通路称为最佳推销员回路。
定义6·7 在加权完备图G?(V,E)中，若对任意x,y,z?V,z?x,z?y,都有 ?(x,y)??(x,z)??(z,y) 则称G满足三角不等式。
定理 6·14 若加权图G满足三角不等式，则最佳H圈也是最佳推销员回路。 证 设C是一个最佳推销员回路，若C不是H图，则存在某顶点z在C上出现至少两次。z在C上第一次出现的前一个顶点是x，后一顶点是y，则去掉第一个z及边(x,z)和
(z,y)，增加边(x,y)，得到C?，由于G满足三角不等式，则?(C?)??(C)，因此C?也
是最佳推销员回路，重复上诉过程，直到没有重复顶点为止，便得到一个H图，其权不超过C的权，当然是最佳推销员回路。证毕。
定理 6·15 加权图G的最佳推销员回路的权和G?的最佳H圈的权相同。
证 设C是G的一条最佳推销员回路其权为?(C)，C?是G?的最佳H图，其权为?(C?)。
设G?中与C在G中行走路线相同的闭通路为C?。由G?的构造有?(C1?)??(C)，若C1?在G?中经过有些顶点多于一次，比如z，设x是第一个z的前一顶点，y是第一个z的
后一顶点，由于G?满足三角不等式，因此用边xy取代边xz和zy所得的闭通路仍是G?的推销员回路，且其权小于等于?(C1?)，对C1?的所有重复顶点重复以上做法直到C1?不再有重
?。 复顶点为止。最后得到的是G?的H圈G0?)??(C1?)??(C) ?(C0