第四章第四章 遍历问题遍历问题v4.1 Euler 环游v4.2 中国邮递员问题v4.3 Hamilton 圈v4.4 旅行售货员问题(travelling salesman prob.)4.1 Euler 环游v环游（环游（tour） 通过图中每边至少一次的闭闭途径。vEuler环游环游 通过图中每边恰一次的闭闭途径。vEuler迹迹 通过图中每边的迹 。 通过图中每边恰一次的途径。（可 “一笔画成”。）vEuler图图 包含Euler环游的图 包含Euler闭迹的图。 本身为闭迹的图。 定理定理4.1 设设G为非空连通图，则为非空连通图，则G为为 Euler图图 G中无度为奇数的顶点。中无度为奇数的顶点。 证明： ：令C = u0 e1 u1 e2 u2 .e u (u = u0 )为G的一Euler环游 ，起点为u0 。则对任一顶点v u0 ，当v每次作为内部顶点出现于C时，C上有二边与v相关联。由于C上包含了G的所有边且不重复，因此d(v)=偶数。类似地，d(u0)=偶数。 ：反证，假设存在非空连通图，它的每个顶点的度都是偶数，但却不是Euler图 。在这种图中选取G使其边数最少边数最少。由于 (G) 2，G包含圈。令C为G中的最长闭迹。由假设，C不会是 Euler环游。因此G - E(C)中一定有一分支G 使(G)0。由于C本身为 Euler图，（由定理的必要条件知）C中每个顶点的度都是偶数，因此G中无度为奇数的顶点。但(G) (G)由G的选择知，G中含一 Euler环游 C。 又，由于G连通，C与C至少有一公共顶点，设为v，不妨设它同时为它们的起点。于是，CC是G的一闭迹，其长大于C的长，矛盾。 附附v定理4.1 :之新证法（J.G.T.Fall 1986)： 对 进行归纳。当 =2时，显然成立。只要再考虑 3情形。 假设对 0 个奇点，则G中存在k条边不重的迹 Q1 ,Q2 ,.,Qk 使得 E(G) = E(Q1) E(Q2) . E(Qk) v 设G为非平凡Euler图 ，且v V。证明：G中任一条 以v为起点的迹 都能延伸成一Euler环游 当且仅当 G-v为林。 （O.Ore）v 若连通图G的任一 边割边数都是偶数，则G 是一Euler图。v4.1.7 左图中能否引一连续曲线（如图中虚线所示），穿过每一线段恰好一次？若能，画出之；不然，证明之。 4.2 中国邮递员问题 v问题问题 在一赋权图G中，求一最小权环游 （即最优最优环游环游）。 当G 为Euler图时，其任一Euler环游都是最优环游，此时有求最优环游的好算法如：vFleury算法算法 （“过河拆桥，尽量不走独木桥”） 1.任取一顶点v0 ，令w0 = v0 。 2.若迹Wi=v0e1v1.eivi已取定，选ei+1Ee1 ,., 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 = VS 。易见， S ； vn S 。令 vm 为Wn 在S中的最后一个顶点，则，显然， ，即 是 的割边。又， = 偶数， v V 。 因此Gn 中无割边，特别地，Gn中与相关联的任一边e是Gn中的非割边，因而也是 中的非割边（？）。但 e ( Gn )，于是在 中，割边 与非割边e都和 相关联，而迹Wn却取的是割边 ，这与算法之 2.(ii) 相矛盾。 v定理之另证： 其实只要再证以下断言断言即可：v断言断言 在算法进行过程中，每个每个Gi 都是G的生成子图，其中只有一个分支是非空的其中只有一个分支是非空的（即其余分支每个都是孤立顶点），且v i与v0 同在该非空分支中。v证明：对i进行归纳。当i=1时，G1 = G - e1，由于G中无割边，G1连通，从而结论成立。假设当in-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的割边。 由习题4.2.1知，与vn-1相关联的边中至多有一条割边，从而Gn-1中与vn-1相关联的边恰只有en这条边。因此，Gn中原Gn-1的非空分支变成一个孤立顶点vn-1及一个含vn与v0 的非空分支 。结论仍成立。 中国邮递员问题中国邮递员问题 在一赋权图G中，求一最小权环游 （即 最优环游最优环游） (i) 找赋权连通图G的一个Euler生成母图 G*，它是由重复（duplicated）G的 一些边而得，且使 w( E(G*) E(G) ) = min ； (ii) 在G*中找出其Euler环游 。 v 附录附录（管梅谷，1960）(书： “Selected Topics in Graph Theorey 2 ” , p.35) 连通图G（每边权 1）中的“邮路”（最优环游）为C 在C中G的每边至多出现两次，且G的任一闭迹中至多有半数的边重复出现于C。 v上述(ii)可用Fluery（好）算法来解决；而(i)已由Edmonds及Johnson(1973)找到好算法。下面仅就最简单的情形，即赋权图G中恰只有两个度为奇数顶点u, v时,讨论求该G*问题：来证，G*可由可由G加上加上(重复重复)G中的最短中的最短 (u, v)-路路P而得而得。v证明：易见，G1* = G*E* E 为一简单图；且其中只有u, v 为奇点，它们一定在G1*的同一分支中（习题1.6.10）。令P*为其中的（u，v）-路，则有w( E* E ) w(P*) w(P) 。 但G+P 也是G的一Euler生成母图，故 G*= G+P 。 习题习题v4.2.1 若连通图G中只有二奇点，则与任一奇点相关联的边中至多有一条是G的割边。4.3 Hamilton 圈vHamilton路路 生成路（生成路（spanning path ）vHamilton 圈圈 生成圈生成圈vHamilton 图图 包含包含Hamilton 圈的图圈的图 v判定任意给定的图是不是判定任意给定的图是不是Hamilton 图，是个图，是个NP-Hard问题。问题。v一个图为Hamilton 图的充要条件是其基础简单图为Hamilton 图，故关于Hamilton 图的讨论只需对简单图即可。v完全图是Hamilton 图非Hamilton图定理定理4.3.1（必要条件）（必要条件） G为为Hamilton图图 (G-S) S , S V证明：令C为G的一个Hamilton 圈 ,则对任一 S V 必有(C-S) S ， 但显然 (G-S) (C-S) ，得证。非Hamilton图定理定理4.3.1 G为为Hamilton图图 (G-S) S , S V注意注意1: 定理4.3.1之逆不成立。 例如，Pertersen图满足定理条件，但它是非 Hamilton 图 。Petersen图定理定理4.3.1 G为为Hamilton图图 (G-S) S , S V注意注意2: 寻找定理中的顶点集S一般来说不容易。比如用穷举法找()的真子集，计算量为Petersen图定理定理4.3.2 (充分条件充分条件) （Ore,1960） 3的简单图的简单图G中，若对任二不相邻顶点中，若对任二不相邻顶点u,v都都有有 (*) d(u)+d(v) ，则则G为为Hamilton 图。图。证明证明：反证，假设存在 3、满足条件(*)的非Hamilton 简单图，在保持其为非非Hamilton 简单简单图的前提下，尽量加边，直到不能再加为止，记所得图为G 。 因 3，G不能是完全图（?）。 任取G中二不相邻接顶点u及v，则G + uv为Hamilton 图，且其中的每个Hamilton 圈均含边uv 。从而G中有Hamilton 路v1 v2.v 其中v1 = u, v = v 。定理定理4.3.2 (充分条件充分条件) （Ore,1960） 3的简单图的简单图G中，若对任二不相邻顶点中，若对任二不相邻顶点u,v都有都有 (*) d(u)+d(v) ，则则G为为Hamilton 图图 。证明证明(续续)：令 S = vi u vi+1 E ，T = v j v jv E 易见：v ST ， S T 。又， ST = 。(否则，存在vk S T ，则G中有Hamilton 圈 v1 v2 vk v vvk+1 v1 ，矛盾。） d(u) + d(v) = S + T = S T 。 这与条件(*) 相矛盾。 证毕。证毕。 u=v1 v2 vk vk+1 v-1 v 推论推论4.3.3 (Dirac,1952) 3的简单图的简单图G中，若中，若 /2，则，则G为哈密尔顿图。为哈密尔顿图。 vKn,n是Hamilton图；vKn, n，n 是Hamilton图vKn,2n，3n 是Hamilton图推论推论4.3.4 ( Bondy & Chvatal , 1974) 设设u, v为简为简单图单图G中二不相邻顶点，且中二不相邻顶点，且d(u) +d(v) ，则，则: G为为Hamilton 图图 G+uv 为为Hamilton 图。图。证明： ：显然 。 ：反证，假设G为非Hamilton 图 ，则由定理4.3.2之证明知, d(u) + d(v) n/2 ，则G为Hamilton 图 。 v. 5个人围桌而坐，总有一 新就座法，使每人的邻座都不相同。v4.3.7. 对下列问题给出一好算法： (a) 构造一个图的闭包。 (b) 若某图的闭包为完全图，求该图的Hamilton 圈 。v4.3.8 对任正整数n，完全3-部Kn,2n,3n为Hamilton 图 ；而完全3-部Kn,2n,3n+1为非Hamilton 图。v4.3.9 称图G为H-连通的连通的G中任二不同顶点u与v间 都有一(u,v)-路。 证明：若的简单图G中每对不相邻顶点u与v 都有d(u) + d(v) +1 ， 则G 为H-连通的。 4.4 旅行售货员问题旅行售货员问题(travelling salesman problem) TSP问题问题: v有一个售货员，从他所在的城市出发去访问其他n-1个城市，要求经过每个城市恰好一次，然后返回原地，问他的旅行路线怎样安排才最经济（即线路最短或旅费最省）？v任给一图G，G是否为Hamilton图？(NP-hard) v如果是，怎样安排旅行路线才最经济？(NP-hard) v图论问题：图论问题：在任给一赋权完全图G中，求最小（最大）权Hamilton圈（最优圈最优圈（optimal cycle）。v对于权重全为1或无穷大的“简单情况”仍是NP-hard Problemv理论上已经证明：除非PNP，不存在多项式时间近似算法，使相对误差小于或等于v为了比较权的大小，对每条Hamilton圈要做 n 次加法，故加法的总数为：v一般的TSP是NP-hard Problem.v当城市数为n时，可能的路线数为：(n-1)! ，或简单情况为： (n-1)! /2n! /2 应用应用v如一工厂需要经过如一工厂需要经过n道工序道工序j1,j2,.,jn周而复始周而复始地生产某种产品，而从工序地生产某种产品，而从工序 ji 到到 jk 的调整时的调整时间为间为ti,k(设设ti,k tk,i)，如何安排加工顺序，使，如何安排加工顺序，使总调整时间为最短？总调整时间为最短？v近似近似 先找一Hamilton 圈C=v1v2 .v v1，再加以改进： 对任i与j, 1i+1j ,若有 w(vivj ) + w(vi+1vj+1) w(vivi+1) + w(vjvj+1)， 则Hamilton 圈 Cij v1v2 .vivj vj-1.vi+1vj+1vj+2 .vv1 是C的一个改进。 v1vivjvi+1vj+1v1vivjvi+1vj+1v反复进行上述步骤，直到不能再改进为止。v所得Hamilton 圈一般不会是最优圈，但可能是“比较好的”。上述步骤也可从不同的Hamilton 圈作为开始，反复进行之。v令W为所求得最小权，它可作为最优圈C*的权的上界上界，即w(C*) W。 v下界下界的估计式的估计式 设v为最优圈C*上任取的一个顶点，则C* - v为G - v中的一个生成树。令T为G - v 中的最优树，则有 w(T)+w(e)+w(f) w(C*) ， 其中e，f为G 中与v相关联的边中权之和最小的两边。 v所以所以 w(T)+w(e)+w(f) 可作为最优圈C*的下界。v设赋权完全图设赋权完全图G的权满足的权满足三角不等式三角不等式，即对，即对 任任x,y,z V，都有，都有 w(xy) + w(yz) w(xz) 。我们介绍一种用最小生成树求最优圈的近似算法。我们介绍一种用最小生成树求最优圈的近似算法。 （1）求）求G中的一棵最小生成树中的一棵最小生成树T。 （2）将）将T中各边均加一条与原边权值相同的平行中各边均加一条与原边权值相同的平行边，设所得图为边，设所得图为G，显然，显然G是欧拉图。是欧拉图。 （3）求）求G中的一条欧拉回路中的一条欧拉回路E。 （4）在）在E中按如下方法求从顶点中按如下方法求从顶点v出发的一个出发的一个Hamilton 圈 H：从：从v出发，沿出发，沿E访问访问G中各个结点，中各个结点，在没有访问完所有结点之前，一旦出现重复出现的在没有访问完所有结点之前，一旦出现重复出现的结点，就跳过它走到下一个结点。（称这种走法为结点，就跳过它走到下一个结点。（称这种走法为抄近路走法。抄近路走法。)abecdfabecdfabcdcecbfbaabecdfabcdecbfbaabecdfabcdebfbaabecdfabcdefbaabecdfabcdefavw(H)作为最优圈的长度( w(C*) )的近似值近似值，则： w(T) w(C*) w(H) 2 w(T), 其中T 是G中的一最优树。vTSP是算法与复杂性领域著名的测试问题。小结小结