若迹Wi =v0 e1 v1 ...ei v i已取定，选 ei+1 ? E\\{e1 ,..., ei}使 (i) ei+1 与 v i相关联；
(ii) 除非无奈，选ei+1 使它不是 Gi = G-{e1 ,..., ei} 的割边。
3. 若 2. 不能再进行下去，停止。
定理4.7 若G为Euler图 ，则由Fleury算法求得的G中的迹，是G的一Euler环游 。 证明：令 Wn =v0 e1 v1 ...en vn Fleury算法求得的G中的迹， 显然 dGn (vn ) = 0 , ? vn = v0 。
假设Wn 不是Euler环游 ，令
S = { v ? dGn (v ) > 0 } ， ?S = V\\S 。 易见，
S ? ? ； vn ??S 。
令 vm 为Wn 在S中的最后一个顶点，则，显然，
?S,S?Gm??em?1? 。
dGn(v) = 偶数， ? v ? V 。
因此Gn 中无割边，特别地，Gn中与vm相关联的任一边e是Gn中的非割边，因而也是Gm中的非割边。但 em?1 ? e (∵em?1 ?Gn )，于是在Gm 中，割边em?1 与非割边e都和vm 相关联，而迹Wn却取的是割边em?1，这与算法之 2.(ii) 相矛盾。 ?
定理之另证： 其实只要再证以下断言即可：
断言 在算法进行过程中，每个Gi 都是G的生成子图，其中只有一个分支是非空的（即其余分支每个都是孤立顶点），且v i与v0 同在该非空分支中。
证明：对i进行归纳。当i=1时，G1 = G- e1 ，由于G中无割边，G1 连通，从而结论成立。假设当i≤n-1时都成立，来证当i = n （＜ε）时也成立：
由归纳假设，Gn-1 = G - {e1 ,......,en-1 }中，vn-1 和v0 在其唯一的非空分支中。于是，算法2.(i) 所选 vn-1
的关联边en 必在该分支中。 当en不是Gn-1的割边时，（对Gn ）结论成立。 当en是Gn-1的割边时，由算法知，Gn-1中与vn-1相关联的边必都是Gn-1的割边。 由习题（见下）知，与vn-1相关联的边中至多有一条割边，从而Gn-1中与vn-1相关联的边恰只有en这条边。因此，Gn中原Gn-1的非空分支变成一个孤立顶点vn-1及一个含vn与v0 的非空分支 。结论仍成立。 ?
习题 若连通图G中只有二奇点，则与任一奇点相关联的边中至多有一 条是G的割边。
中国邮递员问题 ? 在一赋权图G中，求一最小权环游 （即最优环游） ? (i) 找赋权连通图G的一个Euler母图G*，它是由重复 （duplicated）G的一些边而得，且使 w( E(G*) \\ E(G) ) = min ；
(ii) 在G*中找出其Euler环游 。
[ 附录（关梅谷，1960）(书： “Selected Topics in Graph Theorey 2 ” , p.35) 连通图G（每边权? 1）中的“邮路”（最优环游）为C ? 在C中G的每边至多出现两次，且G的任一闭迹中至多有半数的边重复 出现于C。]
当赋权图G中恰只有二度为奇数顶点u, v时,G*可由G加上(重复)G中的最短(u, v)-路P而得。 证明：易见，G1* = G*[E* \\ E ] 中只有u， v 为奇点，它们一定在G*的同一分支中。令P*为其中的（u，v）-路，则有
w( E* \\ E ) ? w(P*) ? w(P) 。
但 G+P 也是G的一Euler母图，故 G* = G + P 。 ? 当G中有 ? 4 个奇点时，已由J.Edmonds and E.L.Johnson 解决（1972）。
21
又，
Hamilton 圈
Hamilton路 ? 生成路（spanning path ） Hamilton 圈 ? 生成圈
Hamilton 图 ? 包含Hamilton 圈的图
定理4.2 G为Hamilton 图
? ?(G-S) ? ? S ? ? S ? V
证明：令C为G的一个Hamilton 圈 ,则对任一 S ? V 必有
非Hamilton 图 ?(C-S) ? ? S ? ，
但 ?(G-S) ? ?(C-S) 。 ?
注意，定理4.2之逆不成立。 例如，Pertersen图 满足定理条件，但它是非Hamilton 图 。
约定 本节只讨论简单图。
定理4.3 （Dirac，1952）? ? 3的简单图G中，若? ? ?/2，
Petersen图则G为Hamilton 图 。
证明：反证，设G为? ? 3满足? ? ?/2的极大非Hamilton 简单图。（即任取一反例，在保持其为非Hamilton、 简单图的前提下，尽量加边，直到不能再加为止。取之为G。）因? ? 3，G不能是完全图。任取G中二不相邻接顶点u及v，则
G+uv
为Hamilton 图，且其中的每个Hamilton 圈均含边uv。从而G中有Hamilton 路 v1 v2............v? 其中v1 = u, v? = v 。 令 S = { vi ? u vi+1 ? E } T = { v j ? v jv ? E }
易见， v? ? S?T ， ??S?T ? < ? 。 又， S?T = ? 。
(不然，假设存在vk ? S?T ，则G中有Hamilton 圈 v1 v2 。。。vk v? v???。。。vk+1 v1 ， 矛盾） ∴ d(u) + d(v) = ? S ? +? T ? =? S?T ? < ? 这与? ? ?/2 相矛盾。 ?
推论4.4.1 ( Bondy & Chvatal , 1974) 设u, v 为简单图G中二不相邻顶点，且 d(u) + d(v) ? ? ，则
G为Hamilton 图 ? G+uv 为Hamilton 图 。 证明：? ：显然 。 ? ： 反证，假设G为非Hamilton 图 ，则由定理4..4之证明知, d(u) + d(v) < ? 矛盾 。 ? 闭包（closure）c(G) ? G的生成母图。 它是由G开始，通过反复将其中不相邻接而度之和 ? ? 的 顶点对 用新边连起来，直到不能再进行为止所得的图。
引理4.4.2 c(G)是唯一确定的（well define）。 证明：假设G?及G??为G的二闭包 ，而 e1 ,.........,em 及 f1 ,...........,fn 为构成它们时加上去的新边（按先后顺序）序列。先证 ：先证每个ei ? E(G?)。假设不然,令ek+1 =uv为e1 ,.........,em 中第一个? E(G??)的新边。记
H = G+{e1 ,.........,eK } 。 由G?之定义知 dH(u) + dH(v) ? ? 。
22
但H ? G?? ， ∴ dG??(u) + dG??(v) ? dH(u) + dH(v) ? ? 。 而 uv ? E(G??), 这与G??之定义矛盾。
同理，每个fj ? E(G?) 。故 G? = G?? 。 ? 定理4.4 简单图G为Hamilton 图 ? c(G)为Hamilton 图 。 推论4.4 设G为 ? ? 3的简单图，则 c(G)为完全图 ? G为Hamilton 图 。 例* 设简单连通图G中 ? ? 2? ，则G含一长 ? 2? 的路。 例 将二部图G = (X,Y,E) ， ? X ? = ? Y ? ，中X的每对顶点都连起来得图H。 则
H有Hamilton 圈 ? G有Hamilton 圈 。 例 若简单2-连通二部图G = (X, Y, E)中, ? X ? = ? Y ? - 1 = n ,且 d(x) ? n , ? x ? X , 则Y的任二顶点间都有Hamilton 路相连。
Hamilton 图 习题
4.3.1. 证明：若 (a) G不是2连通图；或者 (b) G是二划分为（X，Y）的二部图 ，且 ? X ? ≠ ? Y ? ； 则G为非Hamilton 图 。
4.3.2. 一只老鼠边吃边走通过一块3????立方体的奶酪，想走遍每个?????子立方体（共27个）。若从某个角落开始，它能否最后到达立方体的中心？
4.3.3. 证明：若G有Hamilton 路，则对于V的每个真子集S，有?(G-S) ? ?S? + 1。
??14.3.4. 若? ? 3的简单图G中，??C2?1 ，则G为Hamilton 图 。
4.3.5. ???座位的教室中，不可能让每个学生都作一上下左右移动，使每个人都换了座位。 4.3.6. 若二部图G=（X，Y；E）中，|X| = |Y| = n，且? >n/2 ，则G为Hamilton 图 。 4.3.7. ? ? 5个人围桌而坐，总有一 新就座法，使每人的邻座都不相同。 4.3.8. 对下列问题给出一好算法： (a) 构造一个图的闭包。
(b) 若某图的闭包为完全图，求该图的Hamilton 圈 。
4.3.9. 对任正整数n，完全3-部Kn,2n,3n为Hamilton 图 ；而完全3-部Kn,2n,3n+1为非Hamilton 图
旅行售货员问题(travelling salesman prob.)
问题 在赋权完全图中找最小权Hamilton 圈（最优圈） 。 （NP-hard prob。） （问题 任给一图G， G是否为Hamilton 图 ？ （NP-complete prob。）） 代替办法 找一reasonably good solution。例如，先找一Hamilton 圈 C=v1v2 ...v? v1 ，再加以改进： 对任i与j, 1 Cij＝ v1v2 ...vivJ vj-!...vi+1vj+1vj+2 ...v? v1 。 若对某i与j有 w(vi vj ) + w(vi+1vj+1) < w(vivi+1) + w(vjvj+1) 则 Cij是C的一个改进。 反复进行上述步骤，直到不能再改进为止。所得Hamilton 圈 一般不会是最优圈，但可能是比较好的。上述步骤也可从不同的Hamilton 圈作为开始，反复进行之。令W?为所 * 求得最小权，它可作为最优圈C的权的上界。 * w(C)? W? * 下界的估计式 设v为最优圈C上任取的一个顶点，则 * C - v 为G - v中的一生成树。令T为G - v 中的最优树，则 * w(T)+w(e)+w(f) ? w(C) ， 其中e，f为G 中与v相关联的边中权之和为最小的二边。 23 习题 * 4.4.1 设赋权完全图G的权满足三角不等式，即对任x,y,z ? V 都有 w(xy) + w(yz) ? w(xz) 。 证明：G中最优圈的权最多是2w(T), 其中T是G中的一最优树。 匹配 匹配 匹配（matching） M ? E ? M中的边都是link，且互不相邻接。 当uv ? M时，称u与v在M下相匹配；称M饱和（saturated) u与v。称u与v为M-饱和的。类似地，可给出一顶点x为M-不饱和的的定义。 M为图G的完美匹配 ? G中每个顶点都是M-饱和的。 M为图G的最大匹配（maximum matching ） ? 。。。 P为G中的M-交错路(M-alternating path) ? P的边交替地属于M及E\\M。 P为G中的M-可扩路（M-augmenting path ) ? P为M-交错路，且起点与终点都是M-不饱和的。 定理5.1 (Berge,1957) M为G中的最大匹配 ? G中不存在M-可扩路。 证明： ? ：假设G中有M-可扩路P，则 M? = M?E(P) 也是G的匹配， 且? M?? = ? M? +1，这与M 为最大匹配相矛盾。 ? ：反证，假设M不是最大匹配，取G中任一最大匹配M*。。令 H = G[ M?M*] 。 显然， dH(v) = 1 or 2 ? v ? V(H) 。 因此，H的每个分支都是一圈或路，由M及M*的边交错组成。但? M*? > ? M ? ，H中一定有一分 支是一条路P，且其起点与终点都是M*饱和的。从而P是G中的M-可扩路， 矛盾。 ? 习题 5.1.1 (a) 证明：每个k-方体都有完美匹配(k ? 3)。 (b) 求K2n与Kn,n中不同的完美匹配的个数。 5.1.2 证明：一树中最多只有一个完美匹配。 5.1.3 对每个k>1，找出一个无完美匹配的k-正则简单图的例子。 5.1.4 两人在图G上做游戏，交替地选取不同的顶点 v0 ,v1 ,v2 ,.........，使对每个i > 0 ，都有vi 与 vi-1 相邻。最后一个顶点的选择者胜。证明：第一个选点人有一得胜策略当且仅当G没有完美匹配。 5.1.5 G的k-正则生成子图称为G的k-因子。若G存在边不重的k-因子H1，H2， ??，Hn，使得 G = H1?H2???? Hn ，则称G为k-可因子分解的 。 (a) 证明：① Kn,n与 K2n是1-可因子分解的； ② Peterson图不是1-可因子分解的。 (b) 下面的图中哪些有2-因子： 24 (c) 用Dirac定理若G是简单图，? 是偶数，且? ? 1+?/2 ，则G有3-因子。 5.1.6* 证明：K2n+1可表为n个连通的2-因子的并。 5.1.7 证明：任连通偶图G = （X,Y, E）的2-划分（X，Y）是唯一的。 偶图的匹配和覆盖 邻集（neighbour set） N(S) （S ? V）：G中所有与S中顶点相邻接的顶点集合。 定理5.2 （Hall?s theorem,1935) 在偶图G=(X,Y,E)中 G包含使X中每个顶点都饱和的匹配 ? ? N（S）? ? ? S ? ? S ? X （*） 证明：? ：显然。 ? ： 反证，假设存在偶图G，它满足条件（*）但不包含使X中每个顶点都饱和的匹配。* * 令M为G的最大匹配，u为X中M不饱和的顶点。记 * Z = { v ? ? M-交错（u，v）-路 } ** 由于M 为最大匹配，由定理5.1 ，u为Z中唯一M-不饱和顶点。令 S = Z?X ， T = Z?Y 。 ** 显然， S\\U 与T 的顶点在M 下相匹配（注意到：任一M-边若有一端点在Z中，则其另一端一定也在Z中）。因此， ?T? = ?S? - 1 ； N(S)? T 。 但 N(S)? T ， 故 N(S) = T ，从而 ?N(S)? = ?T? =?S?- 1 推论 5.2 (marriage theorem) 若G 为 k-正则偶图（k>0 )，则G有完美匹配。 证明：设G的2-划分为(X, Y)，则 k?X?=?E?=k?Y? ， ? ?X? = ?Y? 。 又，对任S ? X，令E1和E2 分别为与S和N(S)相关联的边集。易见， E1 ? E2 。 ∴ k?S? = ?E1? ? ?E2? = k?N(S)? ∴ ?S? ? ?N(S)? ? S ? X 。 故G中有使X中每个顶点都饱和的匹配M，它也是完美匹配。 ? 称 K（? V）为G的一个覆盖（covering） ? G中每边至少有一端在K中。 最小覆盖（minimum covering）K 。 对G中任一覆盖K及任一匹配M ，显然，恒有 ?M? ? ?K?。 特别地，有 25 ~