图和子图 图和简单图 图 G = (V, E)， 其中 V = {} V ---顶点集， ---顶点数 E = {}E ---边集， ---边数  例。 左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G的几何实现（代表）， 它们有无穷多个。真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。 称 边 ad 与顶点 a (及d) 相关联。也称 顶点 b(及 f) 与边 bf 相关联。 称顶点a与e 相邻。称有公共端点的一些边彼此相邻，例如p与af 。 环（loop，selfloop）：如边 l。 棱（link）：如边ae。 重边：如边p及边q。 简单图：（simple graph）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号：。 习题 1.1.1 若G为简单图，则  。 1.1.2 n ( ( 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。 同构 在下图中， 图G恒等于图H , 记为 G = H ( VG)=V(H), E(G)=E(H)。  图G同构于图F ( V(G)与V(F), E(G)与E(F)之间 各 存在一一对应关系，且这二对应关系保持关联关系。 记为 G F。 注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。 注 判定两个图是否同构是NP-hard问题。 完全图(complete graph) Kn 空图（empty g.） ( E = ( 。 V’ ( ( V) 为独立集 ( V’中任二顶点都互不相邻。   二部图（偶图，bipartite g.） G = (X, Y ; E) (存在 V(G) 的一个 2-划分 (X, Y), 使X与Y 都是独立集。 完全二部图 Km,n ( 二部图G = (X, Y)，其中X和Y之间的每对顶点都相邻，且 (X( = m, (Y( = n 。 类似地可定义，完全三部图（例如 Km,n,p），完全 n-部 图等。  例。用标号法判定二部图。 习题 1.2.1 G ( H ( ((G) = ((H) , ((G) = ((H) 。 并证明其逆命题不成立。 1..2.2 证明下面两个图不同构：   1.2.3 证明下面两个图是同构的： 1.2.4 证明两个简单图G 和H同构 ( 存在一一映射 f : V(G) (V(H) ，使得 uv ( E(G)当且仅当 f(u)f(v) ( E(H) 。 1.2.5 证明：(a).((Km,n ) = mn ; (b). 对简单二部图有 ( ( (2/4 . 1.2.6 记Tm,n为这样的一个完全m-部图：其顶点数为n，每个部分的顶点数为[n/m]或{n/m}个。证明： (a). ((Tm,n) =  其中 k =[n/m] . (b)*. 对任意的n顶点完全m-部图G，一定有 ((G)( ((Tm,n)，且仅当G( Tm,n时等式才成立。 1.2.7 所谓k-方体是这样的图：其顶点是由0与1组成的有序k-元组，其二顶点相邻当且仅当它们恰有一个坐标不同。证明k-方体有个顶点，k*2 k-1条边，且是一偶图。 1.2.8 简单图G的补图G c 是指和G有相同顶点集V的一个简单图，在G c中两个顶点相邻当且仅当它们在G不相邻。 (a). 画出Kcn和 Kcm,n。 (b). 如果G ( G c则称简单图G为自补的。证明：若G是自补的，则 ( ( 0, 1 (mod 4) 关联矩阵M(G)与邻接矩阵A(G) M(G)=[mi,j](((, A(G)=[ai,j]((( , 其中 mi,j = 顶点vi与边ej 的关联次数= 0, 1, 2. ai,j = 连接顶点vi 与 vj 的边数 。 例。    子图 子图(subgraph) H ( G ( V(H) ( V(G) , E(H) ( E(G) 。 真子图 H ( G。 母图（super graph）。 生成子图（spanning subg.） ( H ( G 且V(H) = V(G) 。 生成母图。 基础简单图 （underlying simple g.）。 导出子图（induced subg.）G[V’], (非空V’( V ) ( 以V’为顶点集，以G中两端都在V’上的边全体为边集构成的G的子图。 边导出子图 G[E’] 非空E’ ( E ( 以E’为边集，以E’中所有边的端点为顶点集的的子图。  例。  以上两种子图，其实，对应于取子图的两种基本运算。下面是取子图的另两种基本运算： G - V’ ( 去掉V’及与V’相关联的一切边所得的剩余子图。 ( 即 G[V \ V’] G - E’ ( 从中去掉E’ 后所得的生成子图 例。G - {b, d, g}, ( = G[E \ {b, d, g}] ) G - {b, c, d, g}, ( ( G[E \ {b, c, d, g}] ) G - {a, e, f, g}. ( ( G[E \ {a, e, f, g}] ) 注意 G[E \ E’] 与G - E’ 虽有相同的边集，但两者不一定相等 ： 后者一定是生成子图，而前者则不然。 上述四种运算是最基本取子图运算，今后老要遇到，一定要认真掌握好。关于子图的一些定义还有： G + E’ ( 往G上加新边集E’ 所得的（G的母）图。 为简单计，今后将 G ( {e} 简计为 G ( e ； G - {v} 简计为 G - v 。 设 G1, G2 ( G ，称G1与G2为 不相交的（disjiont） ( V(G1) ( V(G2) = ( ( ( E(G1) ( E(G2) = ( ) 边不相交 （edge-distjiont）( E(G1) ( E(G2 ) = ( 。 ( 但这时G1与G2仍可能为相交的）。 并图 G1(G2 , 当不相交时可简记为 G1+G2. 交图 G1(G2 . 习题 1.4.1 证明：完全图的每个导出子图是完全图；偶图的每个导出子图是偶图。 1.4.2 设G为一 完全图，1( n ( (-1。证明：若 ( ( 4，且G中每个n顶点的导出子图均有相同的边数，则 G ( K(或 Kc( 。 顶点的度 顶点 v的 度 dG(v) = G中与顶点v 相关联边数。 （每一环记为2） 最大、最小度 (，( 。 （((G) , ((G) ) 定理1.1 (hand shaking lemma) 任一图中， 　. 系1.1 任一 图中，度为奇数顶点的个数为偶数。 例。任一多面体中，边数为奇数的外表面的数目为偶数。 证明。作一图，使其顶点对应于多面体的面，并使其中二顶点相邻当且仅当对应的两个面相邻。...... (   k-正则图 （k-regular g.) ( d(v) = k, (v ( V . 习题 1.5.1 证明：( ( 2(/( ( ( 。 1.5.2 若 k-正则偶图(k > 0)的2-划分为 (X, Y),则 (X( = (Y(。 1.5.3 在人数 >1的人群中，总有二人在该人群中有相同的朋友数。 1.5.4 设V(G) = {}，则称 ( d(v1), d(v2), ...... , d(v() ) 为G的度序列。证明：非负整数序列 ( d1 ,d 2, ......, d n) 为某一图的度序列 ( 是偶数。 1.5.5 证明：任一 无环图G都包含一 偶生成子图H，使得 dH(v) ( dG(v)/2 对所有v ( V 成立。 1.5.6* 设平面上有n个点，其中任二点间的距离 ( 1，证明：最多有 3n对点的 距离 = 1 。 路和连通性 途径 （walk) 例如 （u，x）-途径 W = ueyfvgyhwbvgydxdydx (有限非空序列） = uyvywvyxyx (简写法---当不引起混淆时）  起点（origin ） u 。 终点（terminus） x。 内部顶点（internal vertex） y, v, w, x。 （注意，中间出现的x也叫内部顶点。） 长 ( 边数（重复计算）。 节（段，section）。 例如W的(y, w)-节=yvw 。 W-1 （逆途径）, WW’（两条途径W与W’相衔接）。 迹( trail) ( 边各不相同的途径。 例如，yvwyx 。 路 (path) ( 顶点各不相同的途径。（可当作一个图或子图)。例如， yvwx 。 d(u, v) = u与v之间最短路的长。 例。（命题）G中存在(u, v)-途径 ( G中存在(u, v)-路。  G中顶点u与v为连通的(connected) ( G中存在(u, v)-路 ( ( G中存在(u, v)-途径。) V上的连通性是V上的等价关系，它将V划分为（等价类）： V1,......,V( 使每个Vi中的任二顶点u及v都连通（即存在(u, v)-路）。 称每个 G[Vi] i=1,2,......( 为G的一个分支（component）; 称((G）为G的分支数。 G为连通图 ( ((G) = 1 ( G中任两点间都有一 条路相连。 G为非连通图 ( ((G) ( 1。 记号 对任一非空 S(V ，令  = V\S, 记（称为边割） [S, ] = G中 一 端在S中，另一 端在中 的一切边的集合。 例。（命题）G连通 ( 对任 S ( V 都有 [S, ] ( ( 例。（命题） 简单图G中， ( ( k ( G中有 长 ( k 的路。 习题 1.6.1 证明：G中长k为的(vi ,vj )-途径的数目, 就是A k中的(I, j)元素。 1.6.2 证明：对简单图G有，  ( G连通。 对于( > 1，试给出的不连通简单图。 1.6.3 简单图G中， ( > [(/2] - 1 ( G连通。 当(是偶数时，试给出一个不连通的([(/2]-1)正则简单图。 1.6.4 G不连通 ( Gc 连通。 1.6.5 对任意图G的任一边e，有 ((G)( ((G-e) ( ((G) +1 。 1.6.6 G连通，且 d(v)=偶数，( v( V ( ((G-v)( d(v)/2, ( v( V. 1.6.7 连通图中，任二最长路必有公共顶点。 1.6.8 对任一图的任三个顶点 u, v, w 都有 d(u, v)+d(v, w) ( d(u, w)。 1.6.9 任一简单图非完全图中，一定有三个顶点 u, v, w， 使得uv, vw( E 而 uw (E。 圈 闭途径（closed walk) ( 起点=终点且长 ( 0 的途径。 闭迹 (closed trail) (边各不相同的闭途径。 圈（cycle）( 顶点各不相同的闭迹。 （可当作一图或子图。）  例。闭途径： uyvyu ; uywxywvu ； uyuyu。 闭迹：uyxwyvu。 圈： yfvgy ; uywvu。 k-圈（k-cycle）( 长为k的圈。 例。1-圈（即一条环）， 2-圈(由重边组成），3-圈（又称三角形）。 奇圈 (odd cycle)。 偶圈 (even cycle)。 定理1.2 G 为二部图 ( G不含奇圈。 证明：(：设G的2-划分为（X, Y），由G的定义，G的任一圈中，X和Y的顶点一定交错出现，从而其长必为偶数。 (：不妨设G为 连通的。 任取一顶点u,令 X = { x(V ( d(u, x) = 偶数 }, Y = { y(V ( d(u, y) = 奇数}。  由于，易见，(X, Y)为V的2-划分，只要再证X和Y都是G的独立集（ 即X（或 Y）中任二顶点v， w都不相邻 ）即可： 令P与Q分别为最短(u, v)-路与最短(u, w)-路。设u’为P与Q的最后一个公共顶点； 而 P’与Q’分别为P的(u’, v)-节与Q的(u’, w)-节。则P’与Q’只有一公共顶点。 又，由于P与Q的(u, u’)-节的长相等， P’与Q’的长有相同的奇偶性，因此v与w不能相邻，不然， v( P’)-1 Q’wv 将是一 奇圈，矛盾。( 例。（命题） 图G中 ( ( 2 ( G中含圈。 例。（命题） 简单图G，( ( 2 ( G含长 ( ( (+1 的圈。 例。（命题） 任一图中 (a). ( ( ( ( 含圈。 (b)*. ( ( ( + 4 ( 含二条边不重的圈。 习题 1.7.1 若边e在G的一闭迹中，则e在G的一圈中。 1.7.2 证明：(a). ( ( ( ( G含圈。 (b)*. ( ( ( + 4 ( G含两个边不重的圈。 最短路问题 赋权图（weighted g.)(权 ( 1 之推广 ) 权( weight ) w(e) ( 0. w(H) = , H ( G . 路P的长 = w(P) 顶点u与v距离 d(u, v) = 最短(u, v)-路的长。 问题 求最短( u0, v0)-路。 转 求最短(u0, v)-路, ( v ( V \ {u0}. 简化 只考虑简单图，且w(e) > 0 ( e ( E. （ w(uv) = 0 时， 可合并u与v为一 顶点）。 原理 逐步求出顶点序列 u1, u2, ............ 使 d(u 0, u1) ( d(u 0, u2) ( ...... 记 S0 = { u0 }, Sk = { u 0, u1,.............,u k} ， = V \ S 。 Pi为最短( u0, ui)-路 i= 1, 2,...... (1).u1 ： u1是使 w(u 0u1) = min{ w(u 0v)( v ( u 0 } 者 . 得 S1 = S0({u1} , P1 = u 0u1 . (2). 若已求得S k-1 ; d(u 0, u1),.........d(u 0, u k-1) ; 及最短 (u 0, u i)路 Pi i=1.2,...,k-1 . u k ：显然， d(u0, u k) = min{ d( u0, v) ( v ( ((} = d(u 0, u j ) + w( u ju k ) 某 j({ 1,2,......,k-1 } = min{ d( uo, u ) + w( uu k ) ( u ( S k-1 } = min{d( u 0 , u ) + w(uv ) ( v ( ( , u ( S k-1 } = min { l( v ) ( v ( } 其中， l( v ) = min { d( u o, u ) + w( uv ) ( u ( S k-1} ( ( l( u k ) = d( u 0 , u k ) ) ( S k = S k-1 ( { u k } , P k = P j u ju k 某 j({ 1,2,......,k-1 } 。 update 进行下一 步时，只要更新 l( v ) 即可： l( v ) ( min { l( v ) , l( u k ) + w( u kv ) } ( v (  Dijkstra算法 (1).作为开始：l( u 0 ) ( 0 ; l( v ) ( ( ( v ( u 0 ; S0 ( { u 0 }; k ( 0 . (2). （这时已有Sk = { u 0, u1,.............,u k}） l( v ) ( min { l( v ) , l( u k ) + w( u kv ) } ( v (  再计算 min { l( v ) }，设其最小值点为 u k+1 ，令 S k+1 = S k ( { u k+1 }。  (3). 若 k = ( - 1 , 仃止；不然，令 k ( k+1 ,并回到 (2) 。  计算复杂性 加法： (((- 1)/2 比较： (((- 1)/2 ( 2 v (： ((-1)2 +)________________________________________________ 共 O ((2 ) 凡是复杂性为 p( (, ( ) 的算法 ( p( . , . ) 为一多项式 ) 称为“好算法”( “good algorithm”------J.Edmonds )。这是相对于指数型算法而言的：在10 - 6秒/步运算速度下： 复杂性 n= 10 20 30 40 50  n3 .001sec .008sec .027sec .064sec .125sec  n5 .1sec 3.2sec 24.3sec 1.7min 5.2min  2n .001sec 1.0sec 17.9min 12.7days 35.7years  由上表可见，两种算法有天壤之别。 注 1.若只关心求d(u 0 , v 0)则算法进行到v 0 ( S k时停止。 2.计算过程中，所得子图是一 棵树。每步都是往其上增加一条边及一个顶点，因此该过程称为 tree growing procedure 。 3.若要计录u 0到每个顶点u的最短路，只要记录下该路中u 的前一 个顶点即可。 习题 1.8.1 描述一个算法以确定 (a). 一图的各个分支； (b). 一图的围长（即最短圈的长）。 并说明你的算法好到什么程度。 树 树 无圈图（acyclic g.；林forest）。 树（tree） ( 连通无圈图。 叶 (leave) ( 树中度为1的顶点。 定理2.1 树中任二顶点间有唯一的路相连。 证明：反证，假设存在树G，其中有二顶点u与v，其间有二不同(u, v)-路P1 和P2 相连。因P1 ( P2 ，一定存在P1 的一条边e = xy ，它不是P2 的边。显然，图 P1 ( P2 - e是连通的，从而其中包含一条(x, y)-路P。于是P + e 是G中的一 圈，这与G为无圈图相矛盾。 ( 注意 (1). 当G无环时，易见， G是树 ( G中任二顶点间有唯一的路相连。 (2). 以下结论不一 定成立： ( 闭途径 ( ( 圈 。 定理2.2 G是树 ( ( = ( - 1。 证明：对 ( 进行归纳。当 ( = 1时，G = K 1 ，成立。假设定理对 小于 (个顶点的树成立，而G为 ( 个顶点的树。任取G的一边uv 。它是G中的一条路，由定理2.1知， G - uv 不连通，且 它恰有二分支（习题1.6.5），设为G 1与G 2 。它们都是连通无圈图，因此是树。又，它们的顶点数都小于 ( 。由归纳假设知 ((G I ) = ((G I )- 1 I= 1,2 . 故， ((G) = ((G 1 ) + ((G 2 ) + 1 = ((G 1 ) + ((G 2 ) - 1 = ((G) - 1 。 ( 推论2.2 每棵非平凡树至少有两个度为1的顶点。 证明：由于G为非平凡连通图， d(v) ( 1 , ( v ( V 。 再由定理1.1 及2.2知，  ， 由此知推论成立。 例。（命题）恰只包含二度为一顶点的树是路。 习题 2.1.1 证明：非平凡树中，任一最长路的起点和终点均是度为 1的顶点。再由此去证明推论2.2。 2.1.2 当 ( = ( - 1 时，证明以下三结论是等价的： (a) G 是连通图； (b) G是无圈图； (c) G是树。 2.1.3 一树中若 ( ( k，则其中至少有k个度为 1 的顶点。 2.1.4 G为 林 ( ( = ( - ( 。 2.1.5 若林G 恰有2k个奇点，则G中存在k条边不重的路P1 ,P2 ,..,Pk ,使得 E(G) = E(P1 )(E(P2 )( ... (E(Pk )。 2.1.6 正整数序列(d 1 ,d 2 ,...,d ( )是一 棵树的度序列，当且仅当。 2.1.7 饱和烃分子形如C mH n ,其中碳原子的价键为4，氢原子的价键为 1，且任何价键序列都不构成圈。证明：对每个m，仅当n = 2m + 2时C mH n方能存在。 割边和键 e为割边( cut edge) ( ((G-e) > ((G) 。 （即 ((G-e) = ((G) + 1 ） 定理2.3 e为G的割边 ( e不在G的任一圈中 。 证明：令 e = xy ，则 x 与 y在G的同一分支中。于是， e 为G的割边 ( ((G-e) = ((G) + 1 ( x与y不G-e在同一分支中 ( G-e中无(x,y)-路 ( G中无含e的圈。 ( 定理2.4 图G连通，且每边是割边 ( G为树。 证明：注意到以下事实即可， G无圈 ( G中每边不在任一圈中 ( G中每边是其割边。 ( 连通图G的生成树（spanning tree ) ( G的生成子图，且为树。 推论2.4.1 每一连通图都包含一生成树。 证明：令 T 为极小( minimal)连通生成子图 （意指 T 的任一真子图都不是连通生成子图）（由定义，T 可在保持连通性的前提下，用逐步从G中去边（ (所去的边一定在一圈中（即非割边））（每次破坏一圈）的办法求出。 由T的定义知， ((T) = 1 ， ((T - e) = 2 ( e ( E(T) 。 即 T 的每边为割边，故由定理2.4知T为树。 ( 注 也可用极大无圈（生成）子图（即其真生成母图都含圈）来求生成树 T。它可由V上的空图开始，在保持无圈的前提下，逐步由G中取边的办法求出。 （为何是生成树？） 推论2.4.2 G ( ( ( ( - 1 。 定理2.4.5 设 T 为G的一生成树，e为G中不属于T的边，则T+e 含唯一的圈。 证明： 由于T 无圈，T + e 中的每个圈都包含e 。又， C为 T + e 的一圈 ( C - e 为T 中连接e的两个端点的路。 但，由定理2.1知，T中恰只有一条这样的路，因此 T + e中包含唯一的圈。 小结 G为树 ( G中任二顶点间有唯一的路相连，且无环 ( G连通，无圈 ( G连通，且每边为割边 ( G连通，且 ( = ( - 1 ( G连通。且 ( = ( - 1 。 图G的边割（ edge cut） [S,] S ( V ( G中一端在S另一端在中的 边的子集合。 显然，在连通图G中， E’ ( 边割 ( ((G-E’) > 1 。 键（bond, 割集cut set ) ( 极小非空边割。 例。e是G的割边 ( {e} 是G的键。 例。左图G中，  {uv, zv, zy, vw, yx}, {zu, zv, zy, xy, xw}, {uv, zv, zy} {zu, zv, zy} 都是边割，其中后两个为键。而 E’ ={zu, zv, zy, uv}不是G的边割，当然更不是G的键，虽然G- E’ 变成不连通。 易见，当G连通且 S ( ( 时， 边子集B 为G的键 ( B是使G不连通的E的极小子集。 ( ((G-B)=2，且中每边的两端点分别在二分支中。 边割B = [S,]为键 ( G[S],G[]都连通。 （习题） 设H为G的子图，称子图 G - E(H) 为G中H的补图，记为：  (H(G) 。 特别地，当T为G的生成树时，称 (T 为G的余树。 定理2.6 设T为连通图G的一个生成树， e为T的一条边，则 (1).余树(T 不包含G的键； (2). (T + e中唯一包含的G的一个键。 证明：(1).因 G - E((T )= T 连通，则不包含G的边割，从而也不包含G的键。 (2).注意到e为的T割边，令S与(S 分别为 T - e的二分支的顶点集。考虑 B = [S,(S]G 由于G[S] ( 包含T-e的一个分支T[S]) 与G[(S] ( 包含T-e的一个分支T[(S]) 都连通，B必是G键，包含于((T+e中。 来证B为包含在(T+e中的唯一键,只要再证对包含在(T+e中的G的任一键B’，一定有 B = B’ 即可： 假设不然，由于键的极小性，B’不会包含B，从而一定存在B的一边b( B’ 。于是 G - B’ ( T - e +b ( 注意到 B’ ( (T+e ( G-B’ ( T-e ) 但T-e+b也是G的一生成树（因其边数=( -1，且连通），从而G - B’ 连通，这与B’ 为G的键相矛盾。 ( 附录 设G连通，T为其任一生成树。 对每一 e ( (T ，T+e 中有唯一圈C，因而可得 C1 ,C2 ,......,C(-(+1 共( -( + 1个 不同的圈 ，每个称为G的一个基本圈。 同样，对每一 e ( T ，(T+e中有唯一的键因而可得 B1 ,B2 ,......,B(-1 共( - 1个不同的键，每个称为的一个基本割集。 设S1 ,S2为二集合，记其对称差( 即（S1(S2）-（S1(S2） )为 S1 ( S2 称为它们的环和(ring sum)。 性质 图G的每一边割是G的一些割集的边不重并。 设B1 ,B2 为图的任二边割，则B1 ( B2 也是G的边割。 （对任二非空V1 ,V2 ( V， 有[V1 ,V1]([V,V] = [V2 , V2], 其中V3 =(V1 (V2)(((V1( (V2 ) ）。 设边子集E’与E”分别为G中一些圈的边不重并，则E’(E” 亦然。 G的每个圈可唯一地表为G的一些基本圈的环和。 G的每个边割可唯一地表为G的一些基本割集的环和。 边子集E’为G中一些边不重圈的并集 ( 边子集E’与G中每个边割有偶数条公共边。 边子集B为G的一个边割 ( 边子集B与G的每个圈有偶数条公共边。 G为一些圈的边不重并 ( d(v) = 偶数 ( v ( V 习题 2.2.1 设G连通且 e ( E，证明： (a) e在G的每棵生成树中当且仅当e是G的边割。 (b) e不在G的任一生成树中当且仅当e是G的环。 2.2.2 无环图G恰只有一棵生成树T，则G = T 。 2.2.3 设F是G的极大（maximal）林，证明： (a) 对G的每个分支H， F(H 是H的生成树； (b) ((F) = ((G)- ((G)。 2.2.4 证明： 任一图G至少包含 ( - ( + ( 个不同的圈。 2.2.5 (a) 若G的每个顶点均为偶点（即，度为偶数的顶点），则G没有割边； (b) 若G是k-正则偶图且 k ( 2，则没有割边。 2.2.6 当G连通且 S ( ( 时， 边割B = [S,]为键 ( G[S],G[]都连通。 2.2.7 图G的每一边割是G的一些键（即，割集）的边不重并。 2.2.8 在图G中，设B1和B2为键，C1和C2为圈（看作边子集）。证明： (a) B1(B2 是G的键的边不重并集； (b) C1(C2是G的圈的边不重并集； (c) 对G的任一边e，(B1(B2)\{e}都包含键； (d) 对G的任一边e，(C1(C2)\{e}都包含圈。 2.2.9 证明：若图G包含k棵边不重的生成树，则对于顶点集每一划分(V1 ,V2 ,...,Vn )，端点在这个划分的不同部分的边的数目至少为 k(n-1)。 割点 称顶点v为G的割点(cut vertex) ( E可划分为二非空子集E1及E2，使G[E1]与G[E2]只有一公共顶点v。 显然， 当G无环时， v为割点 ( ((G-v) > ((G) 。 ( 存在二顶点x及y ，使G中任一(x, y)-路一定包含v。  例。（边割） 为G的键 ( v不是的G的割点。 定理2.7 在树G中 v为割点 ( d(v) > 1 。 证明：(i) 若d(v) = 0，则G ( K1 ，v不是割点。 (ii) 若 d(v) = 1，则G -v 仍然是树。因此 ((G-v)= 1 = ((G)，从而 v不是割点。 (iii) 若 d(v) > 1，则G中存在与v相邻接的二不同顶点u, w 。由定理2.1知，uvw是G中的唯一(u, w)-路，因此G-v中不含(u, w)-路，（即G-v中u,w不连通） ( ((G-v) > 1 ， 即v为G的割点。 ( 推论2.7 非平凡、无环、连通图中，至少有二顶点不是割点。 证明：令T为G的一生成树，由推论2.2及定理2.7知，T中至少存在二顶点 u与v不是T的割点，则它们也不是G的割点：这是因为对于u (及v)有 1 = ((T-u) ( ((G-u) ( 1 ， ∴ ((G-u) = 1 =((G) 。 ( 习题 2.3.1 设G为 ( ( 3的连通图，证明： (a) 若G有割边，则G有顶点v使 ((G-v) > ((G)； （即，割边必有一端点为割点） (b) (a)的逆命题不成立。 2.3.2 证明：恰有二顶点为非割点的简单连通图必是一条路。 2.3.3 在简单连通图G中证明： v为G的割点 ( G的任一生成树不以v为叶。 生成树的计数及Caley公式 本节只讨论无环连通图。  将图G的关联A((( 矩阵中每列的两个1元素之一改为 -1，得一新矩阵，记为Aa（它是G的一个定向图的关联矩阵）。例如：  记A为从Aa中删去某一行所得的(( -1)(( 矩阵。 引理1 设A 1 为A的任一((-1) 阶子方阵，则 det(A1 ) = ( 1 ( A1 的列对应于G的一生成树。 证明：令划去的行对应于顶点u，记H为以全体与A1的列相对应的边构成的生成子图。由于 ((H)= (-1 ,因此有 H连通 ( H为G的生成树。 （1） 当H不是G的生成树时，由上述知，H不连通。令S为H中不含u的一个分支的顶点集。易见，A1中对应于S的全体行向量之和为一零向量。因此，det(A1 ) = 0。 （2）当H是G的生成树时，重排A1 的行、列如下： 取H的一个度为1的顶点u1 ，并使 u1 ( u 。记 u1 在H中的关联边为e1 ; 再取 H-u1 中的一个度为1的顶点u2 ，并使 u2 ( u ,记 u2 在H-u1 中的关联边为 e2 ;......。 按u1 ,u2 ,...及e1 ,e2 ,,,,,,,的顺序重排A1 的行、列，得矩阵A1’ 。易见，A’1 为下三角型。且主对角线元素全为 (1 ,因此 (detA1 ( = (detA1’( =1 。 ( Binet-Cauchy定理 设矩阵 P=[ pij ]m(n ， Q=[ qij ]n(m ，且m ( n 则  引理2 连通图的生成树数目 = det（AAT）。 证明：由Binet-Cauchy定理知， det(AAT) = ∑(detA1)2 (对A的所有 v-1阶子方阵A1求和） 但由引理1知 (detA1( =  得证。 ( 无环图G的度矩阵 K = [ kij ]( ( ( ， 其中  例如对本节开头的例子有   定理 连通图G的生成树数目 = K的任一元素的代数余子式 证明：容易验证，K=AaAaT 。 又，K的任一行（列）的元素的代数和 = 0，因此 K的所有代数余子式都相等。 再，设A k为从A a中去掉第k行所得的 ((-1)(( 矩阵，易见， A kAT k = 从K中去掉第k行第k列后所得的子方阵 故由引理2知本定理成立。 ( 例。前例的图的生成树数目 = K的(2,3)-元素的代数余子式 = = 8 。 定理（Cayley）　K n 中共有　nn-2 个不同的生成树。 证明：用上述定理可直接证出（习题）。　　　　( 习题 2.4.1 求Ｋ３，３的生成树数目。 2.4.2 若ｅ是Ｋｎ的一条边，　则　Ｋｎ－ｅ的生成树数目为　(n-2)nn-3 。 连线问题 问题 设城市vi与vj间建立直接通信线路的费用为cij（ ( 0）。 建设连接 {}的通讯网使造价最省 ( 在赋权图G中求一最小权连通生成子图； ( 在赋权图G中求一最小权生成树（最优树）。 下面的Kruskal算法是在非赋权图中求生成树的“极大无圈子图”算法的改进，它是一种贪心算法（greedy algorithm）： Kruskal’s algorithm (1) 选棱（link）e1 使w(e1)最小； (2) 若已选定 e1 ,e2 ,...,ei ，则从 E\{e1 ,e2 ,...,ei}中选取 ei+1 使 (i) G[{e1 ,e2 ,...,ei }( {ei+1 }]无圈； (ii) w(ei+1)是满足(i)之最小者。 (3) 若(2)不能再进行下去时，停止。 否则，回到?(2)。 定理2.10 Kruskal算法求出的生成树 = G[{e1 ,e2 ,...,e(-1 }] 是最优树。 证明：反证，假设T* 不是G的最优树。取G的一最优树T。令ek为{e1 ,e2 ,...,e(-1 }中（ 按顺序）第一个不属于T的边，且令T为最优树中使k为最大者。则T+ek中唯一的圈C包含ek ，且C中必含一条边e’k ( T* (不然，C ( T*，矛盾。）但 T’ = T + ek -e’k 也是G的生成树。（因e’k不是T + ek的割边（定理2。3），从而T’ 连通，且其边数=( -1。）又，由于T的子图 G[{e1 ,e2 ,...,ek-1 }( {e’k }] 也不含圈，由法算法知 w(ek )( w(e’k) ∴ w(T’) ( w(T)， 即T’也是G的最优树，且{e1 ,e2 ,...,e(-1 }中第一个不属于T’的边的下标 > k。这与k的取法相矛盾。 ( 实现 先按权的不减顺序将边集重排成 a1 ,a2 ,...,a( 。 关于算法中无圈性的判定，我们有一简单的办法： 当S={e1 ,e2 ,...,ei }已取定时，对候选边aj G[S ( {aj}] 无圈 ( aj的两端点在林G[S]（此处当作生成子图）的 不同分支中。 从而我们有求最优树的标记法： 开始：取a1为候选边； 并将vk标以k， k = 1,2,...,( 。  若S={e1 ,e2 ,...,ei }已取定，当候选边aj 的两端点有相同标号时，改取aj+1为 候选边（丢掉aj 永不再考虑）；否则选定ei+1=aj ，并将G[S]中aj两端点所在的二分支的顶点重新标号，标以两者中的最小者。 算法复杂性 边排序 O( ((log2( ) 比较边两端的标号 ( 重新标号 O(( ( -1)( ) 故为好算法（ ( O( (3) ）。 附录 （A） Prim’s algorithm （也是一种贪心算法） T ( ( , V’ ( {u} for all v((V’ do L(v) ( w(uv) //initializing L(.); (V’=V\V’ while (V’(V do begin find vertex w s.t. L(w)=min{ L(v) ( v ( (V’ } and denote the associated edge from V’ to w by e T ( T ( {e}, V’ ( V’ ( {w} for all v((V’ do //updating L(v) from new vertex w L(v) ( if w(vw) < L(v) then w(vv) end Prim算法的复杂性为 O((2) （B）Steiner tree prob.： （NP-hard prob.) 已给赋权连通图G中，任给定 V’ ( V ，求一最小权树 T 使 V(T) ( V’ 。 习题 2.5.1 用Kruskal算法解带约束的连线问题：用最小费用建立一连接若干城市的网络。但某些特定的城市对间要求有直通线路相连。 2.5.2 连通图G的树图是这样的一个图：其顶点集是G的全体生成树{T1 ,T2 ,...,T(}，且 Ti和Tj相连 ( 它们恰有 v-2条公共边。 证明：任何连通图的树图是连通的。 连通度问题 连通度 B ( E(G)为图G的k-边割 ( (B( = k 。 图G的边连通度（edge connectivity)   ( = 使G变成不连通或平凡图所需去掉的最少边数。） 易见，当G为非平凡连通图时， (( = G的最小键的边数。 例。(( = 0 ( G平凡或不连通。 (( = 1 ( G连通且含割边。 (((Kn)= n-1 ( n > 0 )。 当G为简单图时， (( = ( -1 ( G ( K( 。 称 图G为 k-边连通的（k-edge connected） ( (((G) ( k ( 至少去掉k条边才能使G变成不连通或平凡图。 例如，所有非平凡连通图都是 1-边连通的。 称 顶点子集V’为G的顶点割(vertex cut) ( G - V’ 不连通。 称 顶点子集V’为G的k-(顶)点割(vertex cut) ( V’为G的顶点割，且 ((V’(( = k 。 显然，当G为无环连通图时， v 为G的1-点割 ( v为G的 割点。 完全图无点割。 G的连通度(connectivity)  （ = 使G变成不连通或平凡图所需去掉的最少的顶点数。） 例。当 ( ( 3时， ( = 1 ( G连通且有1-点割。 ((K() = (-1 。 ((G) = ( -1 ( G的基础简单图为完全图。 称 图G为k-连通的（k-connected） ( ((G) ( k ( 至少去掉k个顶点才能使G变成不连通或平凡图。 例如，所有非平凡连通图都是 1-连通的。 定理3.1 ( ( (( ( ( 。 证明：先证(( ( ( ：当G为平凡图时，(( (0 ( ( ，结论成立；当G为非平凡图时，选取v使d(v) = ( , 则 E’ =  是G的一个边割，因此 ((((((((((((( 结论成立。 再来证 (((((( ： 不妨设G为简单、连通、非完全图，于是 (( ( ( -2。 任取一 ((-边割B，及B中任一边 e = xy 。 今，在B-e 的每边上各取一个端点使之不等于x及y 。令这些端点的集合为S。易见， ( S ( ( ((-1 。 记 H = G-S 。 (i) 若H不连通，则S为G的点割，从而 ( ( ( S ( ( ((-1 。 (ii) 若H连通，则e = xy 为H的割边。但，((H) = ((G)- ( S ( ( ( - ( ((-1)( 3 ，因此，x与y必有一个为H的割点，设为 x 。于是 S ( {x} 为G的点割，故 ( ( ( S ( + 1 ( (( 。 ( 习题 3.1.1 (a) 证明：若G是k-边连通的，且k > 0 ，又E’为G的任k条边的集合，则 (（G-E’) ( 2。 (b) 对 k >0，找出一个k-连通图G以及G的k个顶点的集合S，使((G-S)> 2 。 3.1.2 证明：若G是k-边连通的，则 ( ( k(/2 。 3.1.3 (a) 证明：若G是简单图且 ( ( ( -2，则 ( = ( 。 (b) 找出一个简单图G，使得( =(-3且 ( <( 。 3.1.4 (a) 证明：若G是简单图且 ( ( (/2，则 (( = ( 。 (b) 找出一个简单图G，使得 ( = [（(/2）-1] 且 (( < ( 。 3.1.5 证明：若G是简单图且( ( (( +k-2)/2 ( k < ( )，则G是k连通的 。 3.1.6 证明：若G是正则简单图，则 ( = (( 。 3.1.7 证明：若l，m和n是适合0<l ( m ( n的整数，则存在一个简单图G，使得 ( = l，(( =m和 ( =n。 块 块（block） ( 无割点连通图。 显然，当 v ( 3时， G为块 ( G为无环、2-连通图。 例。 v ( 3的块中无割边。 定理3.2 (Whiteney,1932) 当 v ( 3时， G为2-连通图 ( G中任二顶点间则至少被两条内部不相交（internally disjoint）的路连接。 （两条路P与Q内部不相交 ( P与Q无公共内部顶点） 证明：( ：显然，G连通，且无1-点割，因此G为2-连通。 ( ：对G中二顶点间的距离d((,()进行归纳。 当d(u,v) = 1 时（即uv为G的边)， 因G为2-连通，边uv是G的非割边( ∵ ( ( (( ( 2)。因此，由定理2.3 ，边uv在G的某一 圈内，成立。  假设定理对 d((,()<k的任二顶点成立，而 d（u，v）= k （( 2）。令w为长为k的一(u,v)-路中v的前一个顶点。显然， d(u,w)= k-1 。 因此，由归纳假设，存在二内部不相交的 （u,w)-路P及Q。 因G为2-连通，G-w 中一定存在一 (u,v)-路P’ 。令x为P’在 P ( Q 中的最后一个顶点。不失一般性。不妨设x在P上。这时G中有二内部不相交的(u,v)-路： ( P的(u,x)-节)( P’的(x,v)-节) Quv。 ( 推论3.2.1 当( ( 3时， 图G为2-连通的 ( G的任二顶点共圈。 证明：由定理3.2 ，显然。 ( 称边e被剖分 ( 用连接e的两端点的长2为的新路去替换e。 容易验证，当( ( 3时，块的一些边被剖分后仍然保持是块。 推论3.2.2 G为块 ( G的任二边共圈。 证明：( ：当( ( 2时，显然成立。当( ( 3时，将G的任二边e1 和e2 分别用新顶点v1 和v2 加以剖分，得新图G’ 。它是块，因此为2-连通的。由推论3.2.1知，v1 与v2 共圈。从而e1 与e2共圈。 ( ：由条件知，G无环。只要再证G也不会有割点即可：假设u为G的割点。由割点定义知，存在E(G)的一个2-划分（E1 ,E2 )使边导出子图G[E1]与G[E2]恰只有一公共顶点u。由边导出子图定义知，E1 和E2 各含一边 e1 和e2 ，它们有一公共端点u。从而，易见， e1 和e2不能共圈，矛盾。 ( 附录 Menger 定理 若( ( k+1，则 G为k-连通的 ( G中任二不同顶点至少被k-条内部不相交的路所连接。 G为k-边连通的 ( G中任二不同顶点至少被k-条边不重的路所连接。  当一个图G有割点时，我们可沿G的割点将G逐步划分为一些不含割点的极大连通子图，它们每个称为G的块。例如 性质 (1) G的两个块之间至多有一公共顶点，它一定是G的割点。 (2) G的任一割点至少是G的两个块的公共顶点。 (3) G是它的块的边不重并。 (4) 含割点的连通图G中，至少有两个G的块每个恰含G的一个割点。 (5)* 任一图G中，易证，两边之间的共圈关系是一等价关系。它将E(G)划分为一些等价类 (E1 ,E2 ,...,Ep )，而每个G[Ei ]就是G每个的块。 习题 3.2.1 证明：一图是边连通的当且仅当任二顶点至少被两条边不重的路所连接。 3.2.2 举例说明：若P为2-连通图G中一给定的(u,v)-路，则G不一定有一条与P内部不相交的（u,v)-路。 3.2.3 证明：若G没有偶圈及孤立点，则G的每个块为K2 或奇圈。 3.2.4 证明：不是块的连通图G中，至少有两个G的块每个恰含G的一个割点。 3.2.5 证明：G的块的数目 =  ，其中b(v)是G中含顶点v的块的个数。 3.2.6 设G为2-连通，而X和Y 是V的不相交子集，它们各至少包含二顶点。证明：G包含二不相交的路P和Q使得 (i) P和Q的起点在X中； (ii) P和Q的终点在Y中； (iii) P和Q的内部顶点都不在X ( Y中。 3.2.7 叙述求图的块的好算法。 可靠通信网的建设 ( 及((越大越可靠（造价越贵：( ( (( ( ( ） 问题 已给赋权图G及正整数k，求G的最小权k-连通（k-边连通）生成子图。 解 当 k = 1 , optimal tree (connector prob.) 当k > 1 , NP-hard prob. 当每边权( 1且G为任意图时，问题变成求边数最少的k-连通生成子图。( 仍然是 NP-hard prob.) 当G ( K( 且每边权为 1 时，Harary (1962)作出边数最少的G的k-连通（k-边连通）生成子图Hk,(（边数={k(/2}) （∴有好算法。） Hamilton 圈与Euler 环游 Euler 环游 环游（tour）( 通过图中每边至少一次的闭途径。 Euler环游 ( 通过图中每边恰一次的闭途径。 Euler迹 ( 通过图中每边的迹 。 ( 通过图中每边恰一次的途径。 （可“一笔画成”。） Euler图 ( 包含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的长，矛盾。 ( 附录 定理4.1( :之新证法（J.G.T.Fall 1986)： 对( 进行归纳。当( =2时，显然成立。只要再考虑( ( 3情形。 假设对 ( < q成立，而 ((G)=q 。 选取顶点v ，使v有二不同顶点u及w与它相邻 。考虑图  H = (G - {uv,vw})+uw （uw 为一新加边——不管G中是否有以u，w为两端点的边） 显然， ((H) ( 2 , ((H) = q-1 , dH(x) = 偶数 ( x ( V 。  (i) 当((H)=1时，由归纳假设，H中有Euler环游 C’。把C’ 中一边uw代之以路uvw，即得G的Euler环游 。 (ii) 当((H)=2时，由归纳假设，H的二分支各有其Euler环游 C1及C2 。不妨设uw在C2 中。将C2中的边uw代之以迹 uvC1vw，即得G的Euler环游 。 ( 推论4.1 若G连通，则 G有一Euler迹 ( G中至多有二度为奇数顶点。 证明：( ： 类似定理4.1中( ：的证明。 ( ： 若G中无度为奇数顶点，则由定理4.1 ，G中有Euler迹。否则，G中恰有二度为奇数顶点，设为u，v 。 考虑图 G + e ， 其中e为连接u与v的新边。显然，G+e中 无度为奇数顶点，从而包含一Euler环游 C = v0 e1 v1 e2 v2 ...e(((v((( ， 其中，v((( = v0 =u ，v1 =v 。易见 v1 e2 v2 ...e(((v((( 就是G的Euler迹。 ( 习题 4.1.1 若可能，画出一个( 为偶数，而( 为奇数的Euler图。否则说明理由。 4.1.2 证明：若G无奇点，则G的每个块也是Euler图 。 4.1.3 若G无奇点，则存在边不重的圈C1 ,C2 ,...,Cm 使得 E(G) = E(C1) ( E(C2)( ...( E(Cm)。 4.1.4 若连通图G有2k >0 个奇点，则G中存在k条边不重的迹Q1 ,Q2 ,...,Qk 使得 E(G) = E(Q1) ( E(Q2)( ...( E(Qk)。 4.1.5 设G为非平凡Euler图 ，且v ( V。证明：G中任一条 以v为起点的迹 都能延伸成一Euler环游 当且仅当 G-v为林。 （O.Ore） 中国邮递员问题 问题 在一赋权图G中，求一最小权环游 （即最优环游）。 当G 为Euler图时，其任一Euler环游 都是最优环游，此时有求最优环游的好算法，如 Fleury算法 （“过河拆桥，尽量不走独木桥“） 任取一顶点v0 ，令w0 = v0 。 若迹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中的最后一个顶点，则，显然，  。 又，  = 偶数， ( v ( V 。 因此Gn 中无割边，特别地，Gn中与相关联的任一边e是Gn中的非割边，因而也是中的非割边。但  ( e (∵ (Gn )，于是在 中，割边 与非割边e都和 相关联，而迹Wn却取的是割边，这与算法之 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）。 Hamilton 圈  Hamilton路 ( 生成路（spanning path ） Hamilton 圈 ( 生成圈 Hamilton 图 ( 包含Hamilton 圈的图 定理4.2 G为Hamilton 图 ( ((G-S) ( ( S ( ( S ( V  证明：令C为G的一个Hamilton 圈 ,则对任一 S ( V 必有 ((C-S) ( ( S ( ， 但 ((G-S) ( ((C-S) 。 ( 注意，定理4.2之逆不成立。 例如，Pertersen图 满足定理条件，但它是非Hamilton 图 。 约定 本节只讨论简单图。 定理4.3 （Dirac，1952）( ( 3的简单图G中，若( ( (/2，则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) ( ( 。 但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 路相连。 习题 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。 4.3.4. 若( ( 3的简单图G中， ，则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<i+1<j<( , 对应有一Hamilton 圈 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相关联的边中权之和为最小的二边。 习题 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-因子：  (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 <(S( 。 矛盾。 ( 推论 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） 。 对G中任一覆盖K及任一匹配M ，显然，恒有 (M( ( (K(。 特别地，有 (M*(( (( 。 引理5.3 设M与K分别为G中的匹配与覆盖，如果 (M( = (K( 则M为最大匹配，K为最小覆盖。 （证明：略） 定理5.3 (Konig’s theorem,1931) 设 M*，分别为偶图G的最大匹配和最小覆盖，则 (M*(=(( 。 证明：设G的2-划分为（X，Y）。记 U = { u ( X ( u为M*-不饱和的 } Z = { v ( V ( ( M*-交错（u，v）-路 } S = Z(X， T = Z(Y 。 与定理5.2之证明类似，我们有： T中每顶点都是M*-饱和的；T与S\U中顶点在M*下相匹配；N(S) = T。 记 = (X\S) ( T 。 易见，G中每边至少有一端在 中，即 为G 的覆盖（不然，与N(S) = T相矛盾）。又，显然， (M*(=(( 。 再由引理5.3知为最小覆盖。 ( 习题 5.2.1 证明：一个5(5方格棋盘去掉其对角上的两个1(1方格之后，不可能用1(2长方格恰好添满。 5.2.2 (a) 证明：偶图G有完美匹配当且仅当对 所有S ( V 都有 (N(S)(( (S( 。 (b) 举例说明：去掉偶图这个条件之后，上述不成立。 5.2.3 对于k > 0，证明： (a) 每个k-正则偶图都是1-可因子分解的； (b)* 每个2k-正则图都是2-可因子分解的 。 5.2.4 设A1 ，A2 ，……，An 是某集S的子集。 族（A1 ，A2 ，……，An）的一个相异代表系是指S的一个子集{ a1 ，a2 ，……，an }使 ai ( Ai （1( i ( n），且 ai ( aj （当i(j）。证明：（A1 ，A2 ，……，An）有一个相异代表系 当且仅当 ((( (J( ( J ( {1,2,...,n} 。 5.2.5 矩阵的一行或一列统称一条线。证明：一（0,1)-矩阵中 ，含所有1元素的线的最小条数 = 两两都不在相同线上的1元素的最大个数。 5.2.6 (a) 证明：Hall定理的一个推广：偶图G =（X,Y; E) 的最大匹配的边数是 (X( - { (S(-(N(S)( } 。 (b) 试证：若G 为简单偶图，且(X(=(Y(=n 及 ( > (k-1)n ，则G有边数为k的匹配。 5.2.7* 由Konig定理推导Hall定理。 5.2.8* 若非负实数矩阵Q的每行元素之和均为1，每列元素之和也均为1，则称Q为双随机矩阵。称一矩阵为置换矩阵如果它是每行和每列均恰只有一个1元素的 （0，1）矩阵（∴是双随机的）。证明： (a) 每个双随机矩阵一定是个方阵； (b) 每个双随机矩阵Q都可表为置换矩阵的凸线性组合，即 Q = c1 P1 +c2 P2 +……+ck Pk 。 其中每个Pi都是置换矩阵，每个ci都是非负实数，且 。 5.2.9 若偶图G=(X,Y,E)中，X中每顶点的度(Y中每顶点的度，则G有使X每顶点都饱和的匹配。 5.2.10 设偶图G=(X,Y,E)中，Y’为匹配M在Y中的端点集，则存在G的最大匹配M*，其端点集包含Y’。 完美匹配 称H为G的奇分支（odd component） ( H为G的分支，且其顶点数为奇数。 称H为G的偶分支（even component） ( ……。 记 o(G) = G中奇分支数。 定理5.4 ( Tutte,1947) G有完美匹配 ( o(G-S) ( (S( ( S ( V (*) 证明：（Lavasz证法）只要对简单图情形加以证明即可。 ( ： 设G有完美匹配M。对任S ( V，令 G1 ，……，Gn 为G-S中的奇分支。因每个Gi的顶点数都是奇数，每个Gi中至少 有一顶点u i 与S中一顶点vi 在M 下相匹配。从而 o(G-S) = n = ({v1 ，……，vn}( ( (S( 。 ( ： 反证。假设存在图G 满足条件（*），但不含完美匹配。令G* 为G的不含完美匹配的极大生成母图。由于G-S是G*-S的生成子图， o(G*-S) ( o(G-S) ( (S( ( S ( V 。 即G*满足条件（*），又，上式中令S=(得o(G*)=0，因此 ((G*)=偶数。 令 。 因G不含完美匹配，U ( V。 断言 G*-S是一些完全图的不相交并。 从而，由于 o(G*-U) ( (U( ， G*-U中至多有(U(个奇分支。于是，由断言易见， G* 中有完美匹配，这与G* 之假设矛盾。 来证断言 反证。假设G*-U有一分支不是完全图，则其中一定存在3个顶点x，y，z使 xy, yz ( E(G*) ， 而 xz(E(G*) 又，因 y ( U，一定存在 w (V(G*-U) 使 yw ( E(G*)。 令 M1 与 M2 分别为 G*+xz 与 G*+yw中的完美匹配。 考虑 G*+{xz，yw} 中 M1(M2 的边导出子图 H 。显然，H中顶点的度都是2，因而H是一些圈的不相交并。且每圈都是偶圈，由M1 与M2 的边交错组成。 情况1 xz与yw不在H的同一圈中： 设yw在圈C上，则C中所有M1 边及C外所有M2 边一起构成G* 的一个完美匹配，矛盾。 情况2 xz与yw同在H的某一圈C上： 不妨设x，y，w，z以这顺序出现于C上。这时，C的yw……z节中的所有M1 边，及不在该节中的所有M2 边，以及边yz ，一起构成G* 的一个完美匹配，矛盾。( 推论5.4 (Peterson,1891) 每一不含割边的3-正则图都有一完美匹配。 证明：对任S ( V，令 G1 ，……，Gn 为G-S中的所有奇分支。记mi 为一端在Gi中而另一端在S中的边数。则 。 但G中无割边，因此mi ( 3。从而 3(S(=  。 ∴ (S( ( n = o(G-S) ( S ( V。 故由定理5.4，G有完美匹配。 ( 习题 5.3.1* 用Tutte定理推导Hall定理。 5.3.2 推广推论5.4：若G是（k-1）边连通的k-正则图，且( 是偶数，则G有完美匹配。 5.3.3 设G为一树，证明： G有完美匹配 ( o(G-v) = 1 ( v ( V 。 5.3.4* 证明Tutte定理的推广： G的最大匹配的边数 = (( -d)/2 ，其中  （C.Berge) 人员分派问题 问题 n个工人x1 ，……，xn 及n个工作y1 ，……，yn ，已知每个工人都胜任一些工作。能否使每个工人都分派到一件他所胜任的工作？（ （the personnel）assignment prob.) 解 在偶图G=(X,Y,E),(X(=(Y(, 中求出其完美匹配（若存在的话）。 Hungarian method (Edmonds,1965) 以任一匹配M作为开始。（可取M=(） ① 若M饱和X的每个顶点，停止（M为完美匹配）。否则，取X中M-不饱和顶点u， S({u}，T(( 。 ② 若N(S)(T,转到③；否则，N(S)=T,停止（无完美匹配）。 ③ 取 y ( N(S)\T 。若y为M-饱和的，设 yz ( M ，则 S(S({z} ， T(T({y} ， 回到②；否则，存在M-可扩路P。 M(M(E(P) ， 并回到① 。 注1 算法用生长“以u为根的M-交错树”的方法 ，来系统地搜索M-可扩路。树中除u外都是M-饱和的，直到碰到第一个 M-不饱和的顶点时，即得一M-可扩路。当树不能再生长下去时，即为N(S)=T之时。 注2 本算法是个‘好’算法： 从一个M到下一个，至多进行(X(次搜索运算；M至多扩大(X(次 。 习题 5.4.1 试述如何利用Hungarian算法求偶图的最大匹配。 Optimal assignment problem 问题 求赋权图G = Kn，n 的最大权匹配。 称l为（feasible vertex labelling)（f.v.l.) ( l为V上的实函数，且满足： l(x)+l(y) ( w(xy) ( x ( X， y ( Y 。 例。 下面是一可行顶点标号：  记   (相等子图，equality subgraph） ( 以为边集的G的生成子图。 定理5.5 设偶图G的可行顶点标号l使 包含一完美匹配，则是G的最优匹配。 证明：显然，也是G的完美匹配，且  。 但对G的任一完美匹配M有  。 因此w(M)( w()，即是G的最优匹配。 ( 下面是求最优匹配算法的基本思想 ： 任取一f.v.l. l作为开始。定 ，并在 上任取一匹配M作为开始的匹配。用Hungarian算法在 上找完美匹配。若找到，它就是G的最优匹配；否则Hungarian算法停止于某匹配M’（不是完美匹配）及一M’交错树H，它不能再“生长”。将l适当修改成新的f.v.l. ：使仍包含M’及H，且H在中又可继续“生长”。重复上述过程。 Kuhn-Munker algorithm （1955，1957；Edmonds改写（1967）） 以任f.v.l. l作为开始。定 ，并在 上任取一匹配M作为开始的匹配。 ① 若M饱和X的每个顶点，则M为最优匹配，停止；否则，任取一M-不饱和顶点u， S({u}， T(( 。 ② 若( T，转到③；否则，=T。计算  =  及f.v.l.  ：  l(  ，  (  。 ③ 选取 y(\T，若y为M-饱和的，则存在 yx(M ， 作 S((S({x}， T(T({y}， 并转到② ；否则，令P为中的M-可扩-(u,y)路， M(M(E(P) ， 并转到① 。 注1 算法中每计算一次新的的计算量为O((2)；在找到M-可扩路之前，至多进行 (X(次 搜索（每次可能作一次新的的计算）；而初始匹配M至多扩大(X(次。因此是个‘好’算法（计算复杂性为O((4) ) 注2 本算法也可用于解人员分派问题。 习题 5.5.1 所谓n×n矩阵的一条对角线是指它的任n个两两不同行、不同列元素的集合。对角线的权是指它的n个元素的和。试找出下列矩阵的最小权对角线：  （答：权=30） 边着色 边色数 前提 本章只讨论无环图。 k-边着色（k-edge colouring）C ( k种色在图G的边集上的一种分配。 ( C是E(G)的一个k-划分，即 C =（E1 ，。。。，Ek） （注：允许Ei=( ） 边着色C是正常的 ( 每个Ei都是G的一个匹配。 G为k-边可着色的（k-edge colurable） ( G有一正常k-边着色。 ( 存在E(G)的一个k-划分 C =（E1 ，。。。，Ek），使每个Ei 都 是G的一个匹配。 （注：允许Ei=( ） （显然，G为k-边可着色的 ( G为l-边可着色的 （l ( k） ） G的边色数（edge chromatic number） (((G) = min{ k ( G为k-边可着色的} G为k-边色的（k-edge chromatic） ( (((G) = k。 例。 n个人举行一些两两会谈，每次会谈用一个单元时间。问最少要多少单元时间，才能安排完所有会谈？ 例。Peterson图有 (( = 4。 显然， (( ( ( 。 称色i表现（rrepresented）于顶点v ( 与v相关联的某一边有色i。 引理6.1.1 设连通图G不是奇圈，则G有一2-边着色，使该二色表现于G的每个 度( 2的顶点。 证明：不妨设G为非平凡的。 (A) 若G为Euler图： ① 若G 为一圈： 则G为偶圈，从而G的一个正常2-边着色满足要求。 ② 若G不是个圈：则一定存在顶点v0 ，使d(v0)( 4 (∵Euler图每个顶点的度均为偶数）。 令 v0 e1 v1 e2 。。。e( v( 为G一的Euler环游 （ v( = v0 ）。令 E1 与 E2 分别为Euler环游中下标为奇数与偶数的边子集。则G 的2-边着色 C=（E1，E2）满足要求。 (B) 若G为非Euler环游 ：往G中加一新顶点v0 ，并将v0 与G中每个度为奇数顶点都用一新边连起来，得图G’ 。显然，G’为一Euler图 。令v0 e1 v1 e2 。。。e( v( （ v( = v0 ）为G的一Euler环游 。与(A)②一样定义 C =（E1，E2），易见 C’ = ( E1 ( E，E2 ( E） 满足要求。 ( 记号 c(v) = 边着色C表现于v的不同颜色数。 显然， c(v) ( d(v) ( v ( V 。 C为正常边着色 ( c(v) = d(v) ( v ( V 。 称G的k-边着色C’ 为其k-边着色C的一个改进 (  。 C为最优k-边着色（optimal k-edge colouring） ( C不能再改进 。 引理6.1.2 设 C =（E1 ，。。。，Ek）为G的一个最优k-边着色。若G中有一顶点u及色i与j，使i不表现于u，而j在u上至少表现2次。则G[Ei ( Ej ]中含u的分支是一奇圈。 证明：令H为G[Ei ( Ej ]中含u的分支。假设H不是奇圈，由引理6.1.1.，H有一2-边着色，使该二色表现于H的每个度(2顶点上。以这方式，用色i与j对H重新边着色，得G的一个新的k-边着色C’。显然， c’(u) = c(u) + 1 c(v) ( c(v) ( v(u (  这与C为最优矛盾。 ( 定理6.1 设G为偶图，则(( = ( 。 证明：反证，假设(( > ( 。令C为G的一个最优(-边着色，而u ( V为使 c(u) < d(u) 的顶点。于是u满足引理6.1.2.条件，从而G包含奇圈。这与定理1.2 相矛盾。 ( 另一证法（Wilson）对( 进行归纳。当 ( = 1 时显然成立。假设对 ( < 1 都成立，而 ((G)= k 。任取G的一边 e = uv ，考虑 G’ = G - e 。 由归纳假设，G’ 有一 ((G’)-正常边着色 C’={E1’,...,E((G’)}。 若 ((G’) < ((G)，则G显然有((G)-正常边着色，证完； 否则，((G’) = ((G)。令Au与Av各表示C’中不表现于u与v的色集。由于在G’中u与v都不是其最大度顶点，从而有 Au ，Av ( ( 。 ① 当 Au ( Av ( ( 时：将Au ( Av 之一色着在边e上，即得G的((G)-正常边着色。 ② Au ( Av = ( 时：任取色i ( Au 及色j ( Av 。令H为G[Ei’ ( Ej’] 中含u的分 支。易见，H是一条路，由色i与色j边交替组成。因此，v一定不在H上（不然，H的第一条边有色j，最后一边有i ，从而其长为偶数。这导致G中含一奇圈H + e，矛盾。）对换H上的色i与j，得G’的另一正常 ((G’)-边着色，其中在u与v上色j都不表现。 再将色j着在e上，即得G的正常 ((G)-边着色 。 ( 习题 6.1.1 找出一适当的边着色以证明(((Km,n) = ((Km,n)。 6.1.2 (a) 证明：任一偶图G都有一(-正则偶母图。 （不一定为生成母图！） (b) 利用(a)给出定理6.1 的另一证明。 6.1.3 叙述求偶图G的正常(-边着色的好算法。 6.1.4* 证明：若偶图G有 ( > 0 ，则G有一(-边着色，使所有( 种色在每一顶点上都表现。 Vizing定理 定理6.2 (Vizing,1964) 对简单图G有 (( = ( 或 ( + 1 。 证明：（Bollobas）不妨设G中 除uv1外 都已用色 1,2,……,( +1 进行了正常边着色。注意到，G的每个顶点上都至少有一色未表现。令u，v1 各有色i0，i1 未表现。我们可逐步找到不同的色、边序列： i0 ， i1 ， i2 ，……，ij ，…… ； uv1 ，uv2 ，……，uvj ，…… 。 其中， 色ij 是顶点 vj 上未表现的（任意取定的）一色；  边uvj 有色ij-1 。 j=2，3，…… 。 显然，上述过程至多进行到某l（ ( (）次而停止（无法继续满足上述条件）。 这时只有两种可能： (A) 色il 未表现于顶点u上（即没有一条u的关联边uvk有色il ）：重新进行边着色如下 uvj 改着色ij 1 ( j ( l-1 并抹去边uvl 上的色 il-1 。 得G中除uvl 外的正常（( +1）边着色。其中u与vl　上色il 同时不表现。将uvl 改着色il 即得G的正常（( +1）边着色。 (B) il = ik 某 1 ( k ( l-1 ： 重新进行边着色如下 将uvj 改着色ij 1 ( j ( k 并抹去边uvk+1 上的色 ik 。 易见， H =  的每个分支是路或圈，由色i0与ik的边交错组成，且 u，vk+1，vl 在H中的度( 1。 从而，该三顶点不可能同时在H的一分支中。这时只有二可能情形：  ① u 与vk+1不在H的同一分支中：将H的含vk+1分支中的色i0 与ik对换，得G 的除uvk+1外的正常（( +1）-边着色，其中u与vk+1上色i0都未表现。从而，G有一正常（( +1）-边着色。 ② u与vl不在H的同一分支中： 再继续调整边着色如下， 将uvj 改着色ij 并抹去边uvl 上的色 （il-1 ） k+1 ( j ( l-1 。 易见，上述更动并未涉及色i0与ik ，因此H 保持不变。将H中含u分支的色i0 与ik对换，得G 的除uvl外的正常（( +1）-边着色，其中u与vl上色i0都未表现。从而，G有一正常（( +1）-边着色。 ( 注1 对一般图有 Vizing定理 设G为无环图，则 ( ( (( ( ( + ( ，其中(是G的重数（连接G中每一顶点对上的最大边数） 。 注2 NP-complete prob。已给简单图G，是否有(( = ( ？ 注3 “2-边连通、3-正则、简单、平面图都有(( = 3” ( “4-色猜想成立”。 习题 6.2.1* 找出适当的边着色以证明(((K2N-1) = (((K2N) = 2n-1 。 6.2.2 ( 为奇数的非空正则简单图G有 (( = ( + 1 。 6.2.3(a) 设简单图G中( = 2n+1且( >n ( ，则(( = ( +1 ； (b) 利用(a)证明： ① 若G是从有偶数个顶点的简单图中剖分一条边所得的图，则(( = ( +1 ； ② 若G是从有奇数个顶点的简单k正则图中删去少于k/2条边所得的图，则 (( = ( + 1 。 6.2.4(a) 证明： 任一无环图G都有(-正则无环母图。 (b) 利用(a)及习题5.2.3(b)证明：若G 是无环图且( 是偶数，则(( ( 3( /2。 6.2.5 称G为唯一k-边可着色的，如果G的任意两个k-边着色都导致E有相同的划分。证明：每个唯一3-边可着色的3-正则图都是Hamilton 图 。 6.2.6 简单图的积图是指顶点集为V(G)×V(H)的简单图G×H，其中 (u,v)与(u’,v’)相邻 ( u = u’且v(’ ( E(H)； 或v = v’且uu’ ( E(G) (a) 利用Vizing定理证明：(((G×K2）= ((G×K2) 。 (b) 试证：若H是非平凡的，且(((H) = ((H)，则(((G×H) = ((G×H)。 6.2.7 叙述求简单图G的正常((+1)-边着色的好算法。 6.2.8* 证明：( ≥2的简单图G有一((-1)-边着色，使得所有(-1 种色在每个顶点上都表现。 排课表问题 问题 m位教师X1，……，Xm和n个班级Y1 ，……，Yn ，其中教师Xi要给班级Yj上pij节课。欲在最少节次p内排完所有的课。 ( 将偶图G = (X,Y,E) ((X(=m ，(Y(=n)的边集E划分成互不相交的p个匹配(E1，……，Ep) ( 求偶图G的((（=( =p）-边着色。 由习题6.1.4知，上述问题有好算法。 当上述问题中若教室数有限时（ 教室数≥ ），若要在p（( ( ）节内排完全部l（= (E(）节课，所需教室数c (  。 问题 能否适当排课，使全部l节课在p（( ( ）节内排完，且每节课所用 教室数(  ？（∴ ( 1( i ( p ） 引理6.3 设M，N为G的二不相交匹配，且(M(>(N(，则存在G的二不相交匹配M’，N’使(M’( =(M(-1 ，(N’( = (N(+1 ，且M’(N’ = M(N 。 证明：令H = G[M(N]，则H的每个分支为一路或圈，由M及N的边交错组成。且由于(M(>(N( ，存在H的一个分支，它是路P， 起、止于M 边。因此 M’ = M ( E(P) 及 N’ = N ( E(P) 即为所求。 定理6.3 设G为偶图，p ( ( ，则存在G的p个互不相交的匹配使 E = M1 ( ……( Mp 。 且  1 ( i ( p 。 证明：由定理6.1, E可划分为 ( 个互不相交的匹配 M1(，……，M(( 。 因此，对p ( ( ，G有p个互不相交的匹配 M1(，……，M((，……，Mp(。 （令Mi(= ( 当i > p) 使E = M1(( ……( Mp( 。对边数差 > 1的两个匹配，重复使用引理6.3，最后可得所求的匹配M1，……，Mp 。 ( 注 在实际应用中，教师和班级往往会提出一些，例如所上节次，的要求，问题变得很复杂。Even，Itai & Shmir（1976）证明：在教师和班级提出条件时，判定课表的存在性问题是个NP-complete问题。甚至当G为简单偶图，且学生不提出要求的情况下，也是如此。 独立集和团 独立集 定理7.1 S为图G的独立集 ( V\S 为G的覆盖。 证明：S为独立集 ( 不存在两端全在S中的边 ( G的每边至少有一端在V\S 中 ( V\S为G 的覆盖。 # S ( V为G的 团（clique） ( G[S]为一完全图。 独立数（independent number）((G( ( 最大独立集的元素个数。 覆盖数（coering number）((G( ( G的最小覆盖的元素个数。 推论7.1 ((((( 。 证明：设S为G的最大独立集，则V\S为其覆盖，因此 ( ( |V\S |= ( - ( 。 又，设K为G的最小覆盖，则V\K为其独立集，因此 ( ( |V\K| = ( - ( 。 ∴ ((((( 。 # 注 由上述证明知 S为G的最大独立集 ( V\S为G的最小覆盖 。 顶点着色 色数 正常（顶点）着色（proper （vertex） coluring） ( 每边两端不同色。 k-（顶点）着色（k-（Vertex）colouring） ( k种色在V(G)上的一种分配，且任二相邻（的不同）顶点不同色。 ( V的一个k-划分（V1，……，Vk）使每个Vi（可为(）都是G的一个 独立集。 k-（顶点）可着色（k-（vertex） colourable） ( G有一k-着色。 显然， G为k-可着色 ( G的基础简单图为k-可着色。 由此，我们约定 本章只讨论简单图。 例。 G为1-可着色的 ( G 为一空图。 G为k-可着色的 ( G 为k-部图。 　 G为k-可着色的 ( G为j-可着色的（k ( j）。 色数（chromatic number） ((G) = { k ( G为k-可着色的} 。 G为k-色图 ( ((G) = k。 G为临界的（crtical） ( ((H) < ((G) ( H ( G 。  ( G连通且满足 ((G-e) < ((G) ( e ( E(G) 。 G为k-临界的 ( G为临界图，且 ((G) = k。 显然，G为k-色图 ( G包含一k-临界子图。 例。1-临界图 ( K1 （唯一）。 2-临界图 ( K2 （唯一）。 3-临界图 ( 奇圈 。 4-临界图 例如：K4 ，Grotzsch图等。 注意 一图G的临界图不一定是它的导出子图。 定理8.1 G为k-临界图 ( ( ( k - 1 。 证明：反证，假设 ( < k-1 。取v ( V使d(v) = ( 。因G 为k-临界图的，G-v必是（k-1）-可着色的。令 （ V1，……，Vk-1） 为G-v 的(k-1)-着色。由于d(v) = ( < k-1，v一定与某一Vj中所有顶点都不相邻。从而 （ V1，……，Vj({v}，……，Vk-1） 是G的(k-1)-着色，于是((G) ( k - 1 ，矛盾。 # 推论8.1.1 ((G) = k ( G中至少有k个度 ( k-1 的顶点。 证明：令H为G的k-临界子图。由定理8.1知 dH(v) ( ((H) ( k-1 ( v ( V(H) 。 ∴ dG(v) ( dH(v) ( k-1 ( v ( V(H) 。 又因H为k-色的，必有 |V(H)| ( k 。 # 推论8.1.2 对任一图G都有 ( ( ( + 1 。 证明：由推论8.1.1知 ( ( ( - 1 。 # 令S为连通图G的一个点割。 V1，……，Vn为G - S 的各分支的顶点集。称 Gi = G[Vi(S] 为G的S分支。称G1，……，Gn上的各个着色在S上是一致的，当且仅当在各个着色中S中每顶点都被着以相同的色。 定理8.2 临界图的任一点割都不是团。 证明：反证，假设k-临界图G有一点割S是团。令G1，……，Gn是G的S分支。因G为k-临界的，每个Gi都必是（k-1）-可着色的。但S为团，每个Gi的任一（k-1）-着色都导致S中所有顶点彼此不同色。从而一定存在G1，……，Gn在S上一致的（k-1）-着色。这些着色一起构成G的一个（k-1）-着色，矛盾。 # 推论8.2 每一临界图是一个块。 证明：若v是一割点，则{v}是一个点割，且是团。故临界图不含割点，因而是个块。# 注 NP-complete prob. ： 对任给图G及正整数k ( |V| ，G是否为k-可着色的？ 从而，求任给图G的色数是个NP-hard prob. 。 贪心（greedy）着色法 ：用色1，2，… 逐步（按某一 顶点排序）一个个顶点进行着色，每次选用尽可能小的颜色进行着色。 例如，对任给图G，按任一顺序进行贪心着色，易见，至多用了( + 1 个色，从而得到了推论8.1.2另一证明。 显然，贪心着色法所用的颜色数完全取决于着色的顺序，即顶点的一个排序。假如我们事先知道图G的一个(-着色为 C = （E1，E2，……，E( ） 。 按E1，E2，……，E(任作一顶点排序（同一色集Ei内随意排序），按此顺序进行贪心着色，易见，一定恰好用了( 个色。因此，设法构想一适当的顶点排序进行贪心着色，往往可能得到关于着色的一个较好结果（如Brooks定理之证明）。下面是这方面的一些结果： 例。设图G 中度序列满足：d1 ( ……( d( ，则 ( (  。 证明：不妨设顶点排序 (：v1，……，v( 恰使d(vi ) = d i i=1,2,...,( 。沿( 进行贪心着色。设vk被着上了色( 。易见，它一定与前面 ( ( -1个不同色的顶点相邻，因此 dk＝ d(vk) ( ( - 1 。 又，显然 ｋ( ( 。 ∴ min {dk + 1，k} ( ( 得证。 # 例。试证：((G) ( 1+ max{ ((H) | H为G的导出子图}。 证明：作G的顶点排序 (：v1，……，v( 如下： v( 为图G的最小度顶点； v(-1 为图G-v( 的最小度顶点； v((( 为图G-{v(，v(-1} 的最小度顶点； ……………… 令L = max{ ((H) | H为G的导出子图}。注意到G，G-v( ，G-{v(，v(-1} ，…都是G 的导出子图。从而，每个dH(vi) ( L，于是每个vi 都只与前面( L个顶点相邻。因此贪心着色法至多用了L+1个色。故 ((G) ( 1+L = 1+ max{ ((H) | H为G的导出子图} 。 # 注 顶点着色问题的另一常用技巧是基于以下显而易见的命题： 设d(u) ( k-2 (k ( 2) ( u ( U ( V，而G-U为k-可着色的，则G也是k-可着色的。 例。试证 ((G)+((Gc) = ( +1。 证明：对( 进行归纳。当( ( 2时，显然成立。假设对顶点数< ( 时都成立，而((G)=( 。 情况1 当((G)( ((G)-1时：则 ((Gc)= (-1-((G)( ( - ((G) 。 ((Gc) ( ((Gc)+ 1( ( -((G)+1，得证。 情况2 当((G) < ((G)-1时：取u使 dG(u) = ((G) ( ((G) -2 。 因此，首先有 ((G1) = ((G) 。 其中G1=G - u 。由归纳假设知， ((G1) + ((G1c) = (。 ∴ ((G)+((Gc) = ((G1)+((Gc) ( ((G1)+((G1c) +1 = ( +1。 # 习题 8.1.1. 证明：若C =（E1，E2，……，E( ）是图G的一个(-着色，则任二Ei与Ej间至少有一边相连。 8.1.2. 证明：若G的任二奇圈都有公共顶点，则( ( 5 。 8.1.3. 证明： 设图G 中度序列满足：d1 ( ……( d( ，则 ( (  。 8.1.4. 利用习题8.1.3 证明： (a) ( (  。 (b) ((G)+((Gc) = ( +1。 (c) 推论8.1.1 。 8.1.5. 试证：((G) ( 1+ max{ ((H) | H为G的导出子图}。 8.1.6.* 设k-色图G上有这样一个正常着色（不一定为k-着色），其中每种色都至少分配给两个顶点。证明：G也有这样的k-着色 。 8.1.7. 证明：若G 是简单图，则 ( ( (2/((2 - 2( ) . 8.1.8. 若G 的任二k-着色都导出V的相同的k-划分，则称G为唯一k-可着色的。 8.1.9. 证明：k-临界图没有顶点割能导出唯一(k-1)-可着色子图。 8.1.10, (a) 证明：若u，v为临界图的二顶点，则不可能有N(u) (N(v) 。 (b) 试证：不存在恰有k+1个顶点的k-临界图。 8.1.11. (a) ((G1(G2) = ((G1) +((G2) ，其中G1(G2 称为图G1与G2的联图，它是将 它们间的每对顶点都用新边连起来所得的图。 (b) G1(G2是临界图，当且仅当G1与G2都是临界图。 8.1.12. 设G1与G2是恰有一公共顶点v的k-临界图，且vx和vy 分别是G1和G2的边， 则 (G1-vx)((G2-vy)+xy也是k-临界图。 8.1.13. 对 n = 4及 n ( 6 构造n个顶点的4-临界图。 8.1.14.* (a) 设V的2-划分（X，Y）使G[X]和G[Y]都是n-可着色的，且边 割 [X，Y] 最多有n-1条边，则G也是n-可着色的。 (b) 试证：每个k-临界图都是(k-1)-连通的。 Brooks 定理 定理8.4 设简单连通图G既为非奇圈、亦为非完全图，则( ( ( 。 证明：对( 进行归纳。当( ( 3时，显然成立。假设当( < n时都成立，而((G) = n。不妨设：① G为(-正则的。（不然，取u使d(u)= ( < ( ，由归纳假设，易见，G - u为 ( -可着色的，从而G亦然。） ② G为2-连通的。（不然，令v为G的割点，则存在E的2-划分（E1，E2）使G[E1]与G[E2]恰有一公共顶点v，从而易见，结论成立。）③ ( ( 3。（不然，G为圈，结论成立。） 今选取3个点 x1 ，x2，xn 如下： 若 ( ( 3，则任取一点为xn ，并取N(xn）中任二不相邻顶点作为 x1 与x2 。（ 这样的二顶点一定存在。不然，N(xn）( {xn} 是一团，从而G是完全图，矛盾。） 若 ( = 2，则选取xn使 ((G - xn )= 1。注意到G - xn中至少有2个endklocks （即，只含G的一个割点的G的块），每个至少含一G的非割点与xn 相邻接。取不在同一endklock中的两个这种顶点作为x1 与x2 。 在上述两种情况下，我们都有 G - {x1, x2} 连通； 且 xnx1 ， xnx1 ( E(G) 而x1x2 ( E(G) 。 下面我们来作V的一个排序： 取xn-1 ( V \{x1, x2, xn}; 取xn-2 ( V \{x1, x2, xn-1, }; ................................. 由于G - {x1， x2}之连通性，上述步骤可一直进行到底。得V的一个排序： x1， x2，……，xn 。 其中每个xi （i < n )都至少与某xj ，j > i，相邻接。又，x1 与x2不相邻。于是，贪心着色法只用了( ( 个色。 # 习题 8.2.1. 证明Brooks定理等价于下述命题：若G是k-临界图（k ( 4），且不是完全图，则2( ( ((k-1)+1 。 8.2.2. 利用Brooks定理证明：若G是( = 3的无环图，则(( ( 4。 围长和色数 易见，若G中最大团的顶点数k，则( ( k。下面的定理表明，一个有很大色数的图，其最大团的顶点数不一定也很大。 定理8.7 对任正整数k，都存在不含K3的图G使 ((G) = k 。 (即，可找到色数任意大的图，但其最大团顶点数却只为2。） 证明：对k进行归纳。当k = 1时，G1 = K1满足要求；当k = 2时，G2 = K2 也满足要求；一般，设Gk = (Vk , Ek ) ，Vk = {v1，……，vn）满足要求（k ( 2） ，则构造 Gk+1 = (Vk +1, Ek+1 )如下：令 Vk+1 = Vk ( {u1，……，un}( {v}。 其中 u1，……，un，v 为新加的顶点。将每个u i 与N(vi)中每个顶点用新边连起来；再将u与每个ui 也都新边连起来，所得图即为Gk+1 。 易见，Gk+1中不含K3。又，Gk的任一k-着色可扩充成Gk+1的（k+1）-着色如下：将每个ui着以vi上的色；再用一新色着在v上。显然，这是Gk+1的正常（k+1）-着色，从而Gk+1是（k+1）-可着色的。余下只要再证Gk+1不是k-可着色的即可：不然，不妨设在该k-着色中v被着以色k。这时无一ui被着以色k。今，将每个被着以色k的顶点vi都改着以顶点ui的色。易见，这是Gk+1的正常k-着色。它导致Gk的一个正常（k-1）-着色，这与Gk为k色图相矛盾。 # 注 Hajos曾提出似乎是可信的猜想： G为k-色图 ( G包含Kk的一个剖分。 当k=3及4时可证猜想成立。但1986年已证明该猜想不成立。 习题 8.3.1. 证明：定理8.7中的图Gk是一k-临界图。 8.3.2*(a) 设G是围长至少为6的k-色图（k ( 2）。作一新图H如下：取k(个新顶点集S及G的 个互不相交的拷贝，且建立G的拷贝与S的(个顶点的一一对应。再将G的每个拷贝与它在S中相对应的(个顶点之间用一匹配连接起来。证明：H的色数至少为k+1，其围长至少6。 (b) 试证：对任k ( 2，都存在围长为6的k-色图。 平面图 平图和平面图 图G可嵌入（embededable）于平面中 ( G可画在平面上，使它的边只在端点处才可能相交叉。 （该画法称为G的一个平面嵌入（planar embedding）或平图 （plane graph）） ( G为平面图（planar graph） 例。K5，K3,3 以及它们的剖分都是非平面图。它们中任一个去掉任一边后都是平面图。 注意 平面图和平图间的区别。后者是前者的一个几何实现（具体画法）。 Jordan 曲线定理 平面中任一Jordan 曲线J（连续不自交的闭曲线），将余下的平面划分成二不相交开集：J的内部（interior）和 J的外部（exterior），分别记为 int J和ext J。（它们的闭包分别记为Int J 和 Ext J）。连接int J中一点到ext J中一点的任一条曲线一定与J交于某一点。 定理9.1 K5为非平面图。 证明：反证，假设G为K5的一个平图。令G的五个顶点为v1，……，v5。注意到圈 C = v1v2v3v1 为平面上的一条Jordan 曲线，且v4必在int C 或ext C中。若v4 ( int C，则边v4v1， v4v2，与v4v3将int C划分成三个区域int C1，int C2，和int C3。 这时v5一定在上述三个区域及区域ext C之一。若v5 ( ext C，则因v4 ( int C，边v4v5 必与C交于某一点，这与G为平面图的假设相矛盾。其它情形类似地也导致矛盾。 # 定理9.2.’ K3,3为非平面图。 证明：类似，略。 平面嵌入的慨念可推广到其它平面上。称 图G可嵌入于曲面S上　( G可画在S上，使它的边仅在端点处才可能相交叉。 例。K5和K3,3都可嵌入于环面上； K3,3可嵌入于Mobius带上；每个图都可“嵌入”于三维空间R3中。 定理9.2 G可嵌入于平面上 ( G可嵌入于球面上。 证明：利用球极平面射影，略。 # 对偶图 平图G的面（face） ( G将平面划分出来的连通区域的闭包。 外部面（exterior face） ( G中唯一的无界面。 定理9.3. 对平面图G 的任一顶点，都存在G的一个平面嵌入，使它在该嵌入的外部面上。  证明： 先将G嵌入于球面上，并将球面的北极放在含该顶点的G的一个面中，再利用球极平面射影。 # 记号 F(G) = 平图G的面的集合。 ((G) = 平图G的面数。 b(f) = 面f的周界。 当G连通时，b(f)可当作一闭途径，其中G在b(f)中的每一割边在该途径中都恰被走过两次。当G为2-连通时，b(f) 为一圈。 例。 b(f1) = v1e1v2e5v4e8v6e9v6e8v4e4v1e6v7e7v7e6v1 。 b(f5) = v1e1v2e2v3e3v4e4v1 。 在平图G中面f与它的周界上的边和顶点相关联。称G的一边e分隔（seperate）与它相关联的面。易见， e为G的割边 ( e只与G的一个面相关联 ( e恰分隔G的一个面。 e为G的非割边 ( e恰与G的两个面相关联 ( e恰分隔G的两个面。 平图G中面f的度（degree） dG(f) = 与面f 相关联的边数（割边记为2）。 例如，d(f1) = 9。  平图G的对偶图（dual graph）G*是这样的一个图：它们之间有如下的一一对应关系 G的面f ( G*的顶点f* ； G的边e ( G*的边e* 。 且 G*的顶点f1* 与f2* 被边e* 连接 ( G的面f1与f2 被边e分隔。 例如，左面所示平图G的对偶图G* = (V* , E*) 为 V* = {f1*，……，f5*} ， E* = {e1* = f1*f5* ， e2* =f5*f5* ，e3* = f2*f5* ，……，e8* = f2*f3*} 。  易见，平图G的对偶图G*是一平面图，事实上存在G* 的一个平面嵌入（称为几何对偶）如下：在G的每个面f中放置顶点f*，对应于G的每一边e，画一条边e* 使它穿过e恰好一次（且不穿过G的其它边）。例如，上例平图G的对偶图G* 如右图所示。 由上述知，G* 一定是连通平面图。且有 e是G的环 ( e* 是G* 的割边。 e是G的割边( e* 是G* 的环。 有时，为方便计，把平图G的几何对偶G* 当作G的对偶图。这时，若G连通，则有  G** = (G* )* ( G。 （当G不连通时，上式不一定成立）。 注意 “平图G ( H ( G* ( H* ”不一定成立。 例如，右边二平图是同构的，但它们的对偶图并不同构。因此，对偶图的概念只对平图有意义，不能推广到平面图上。 由G* 的定义易知： ((G* ) = ((G) ((G* ) = ((G)  定理9.4 设G为平图，则  证明： 。 # 习题 9.2.1 .(a)证明：图G是平面图 ( G的每个块都是平面图。 (b)试证：极小非平面图是简单块。 9.2.2. 若一平图和它的对偶图同构，则称该平图为自对偶的。 (a) 若G为自对偶的，则( = 2( - 2 。 (b) 对每个 n ( 4 ，找出n顶点的自对偶平图 。 9.2.3. (a) 证明：B是平图G的键 ( { e* ( E(G* ) | e ( B } 是G* 的圈。 (b) 证明：C是平图G的圈 ( { e* ( E(G* ) | e ( C } 是G* 的键。 (c) 试证：Euler平图的对偶图是偶图。 9.2.4. 设G是平图，证明： (a) (G* )* ( G ( G是连通图。 (b) ((G** ) = ((G) 。 9.2.5. 设T是连通平图G的生成树，E* = 。证明：T* = G*[E*] 是G* 的生成树。 9.2.6. 每个面的度都是3的平图称为平面三角剖分图。证明：每个( ( 3的简单平图都是某简单平面三角剖分图的生成子图。 9.2.7. 设G是( ( 4的简单平面三角剖分图，证明：G*是简单2-边连通3-正则平面图。 9.2.8.* 证明：任何平面三角剖分图，都包含一个有2( (G)/3条边的偶子图。 Euler 公式 定理9.5 (Euler) 设G为连通平图，则 ( - ( + ( = 2 。 证明：对( 进行归纳。当( = 1时，G的每边为割边（因每边只分隔一个面）。又因G连通，从而G是树（定理2.4)，于是( = ( - 1，定理成立。 假设定理对( < n成立，而((G) = n ( 2。任取G的一条非割边e（它一定存在，不然导致( = 1，矛盾）。注意到e分隔G的两个面，有 ((G-e) = n-1 。 （e所分隔的G的两个面，在G - e 中合而为一）。因此由归纳假设有 ((G - e) - ((G - e) + ((G - e) = 2 。 但 ((G - e) = ((G)；((G - e) = ((G) - 1； ((G - e) = ((G) - 1 ，将它们代人上式，得证。 # 推论9.5.1 对平图G的任二平面嵌入H及R都有 ((H) = ((R) 。 证明：因 H ( R，它们的顶点数及边数都相等。再由本定理，得证。 # 推论9.5.2 当( ( 3时，若G为简单平面图，则 ( ( 3( - 6 。 证明：不妨设G为连通图。由于G为简单图， d(f) ( 3 ( f ( F。 再由定理9.4得 2( =  ( 3( = 3(( - ( + 2) 。 从而得证。 # 推论9.5.3 设G为简单平面图，则 ( ( 5 。 证明： 当( ( 2时显然成立。当( ( 3时，由定理1.1及推论9.5.2有 (( (  = 2( ( 6( - 12 < 6( ， ∴ ( ( 5 。 # 推论9.5.4 K5 为非平面图。 证明：若K5 为平面图，则推论9.5.2得 10 = ( ( 3*5 - 6 = 9 ， 矛盾。 # 推论9.5.5 K3，3 为非平面图。 证明：若K3，3 为平面图，由于它的每个圈长 ( 4，它的每个面的度 ( 4。因此 4( (  = 2( = 18 ， ( ( 4。 ∴ 2 = ( - ( + ( ( 6 - 9 + 4 = 1 ， 矛盾。 # 习题 9.3.1. (a) 证明：若G是围长k ( 3的连通平面图，则 ( ( k(( - 2)/(k - 2) (b) 利用(a)证明： Petersen图是非平面图。 9.3.2. 证明：每个平面图都是6顶点可着色的。 9.3.3. (a) 证明：若G是( ( 11的简单平面图，则Gc 是非平面图。 (b) 找出一个( = 8的简单平面图，使Gc 也是平面图。 9.3.4. 若G可表示为若干个平面图的并图，称这种平面图的最小个数为G的厚度，记为((G)。于是， ((G) = 1 ( G是平面图。 (a) 证明：((G) ( {( /（3( - 6）}； (b) 试证：((K() ( {((( - 1)/6(( - 2)} ，并利用习题9.3.3(b)证明，等式对所 有 ( ( 8成立。 9.3.5. 利用习题9.2.5.的结果推导Euler公式。 9.3.6. 证明：若G是平面三角剖分图，则( = 3( - 6。 9.3.7. 设S是平面上n ( 3个点的集合，其中任二点间的距离 ( 1。证明：最多有 3n - 6个点对其距离恰为1。 Kuratowski 定理 下面的两个引理是显然的： 引理9.10.1 G为非平面图 ( G的每个剖分图为非平面图。 引理9.10.2 G为平面图 ( G的每个子图为平面图。 定理9.10 (Kuratowski,1930) G为平面图 ( G不包含K5 或K3，3的剖分。 证明：略。 Wagner定理 G为非平面图 ( G包含可压缩（contractible）成K5或K3，3的一个子图。 （证明：略。） （一个简单图G的初等压缩（elementary contraction）是将G的一边uv去掉，并将顶点u和v合并成一个新顶点。图G可压缩成图H，是指G可经过一系列的初等压缩而变成H。） 例。Petersen图是非平面图。因它包含K3，3的一个剖分；它也可压缩成K5 。 五色定理和四色猜想 定理9.11 (Headwood,1890) 每个平面图是5-（顶点）可着色的。 证明：反证，假设定理不成立。令图G为最小反例。易见，G为简单连通图且( ( 6。选取一顶点u使d(u) = ( 。由推论9.5.3.知，( ( 5。由对G的假设知，G - u上可进行正常5-着色 （V1，……，V5）。 当u只与( 4个顶点相邻时，显然，G为5-可着色的，矛盾。因此u必恰与5个顶点相邻。不妨设它们按顺时针顺序为v1，……，v5 ，且每个vi ( Vi 。记 Gij = G[Vi ( Vj] i ( j， 1 ( i，j ( 5。 如果存在i，j使vi与vj不在Gij同一分支中。则将Gij中含vi的分支上的色i与j对换，得G - u 的一个新的5-着色，其中u只与4种色相邻，从而G为5-可着色的，矛盾。因此，每个Gij中都有一（vi ，vj）-路Pij ，由色i和j顶点交错组成。令圈 C = uv1P13v3u 。 由于C分隔v2和v4，由Jordan曲线定理，P24一定与C交于一点。由于G为平面图，这一点只能是G的顶点。但 P24上只有色2和4，而C上无此二色，这是不可能的，矛盾。# 4-色猜想（four colour conjecture） 所有（无环）平面图都是4-顶点可着色的。 平图G的k-面着色（k-face colouring） ( k种色在G的所有面的一个分配（不一定是正常着色） 平图G为k-面可着色的 ( G有一正常的k-面着色。 面色数（face chromatic number） (*(G) = min{k | G为k-面可着色的} 。 显然，对任一平图G都有 (*(G) = ((G* ) 。 定理9.12 以下诸命题是等价的： ① 每一平面图是4-（顶点）可着色的； ② 每一平图是4-面可着色的； ③ 每一简单、2-边连通、3-正则、平面图是3-边可着色的。 证明：① ( ② ： 显然。 ② ( ③ ： 设G为简单、2-边连通、3-正则、平面图；为其平面嵌入。由②为4-面可着色的。用摸2整数域上的向量 c0 = (0,0)，c1 = (0,1)，c2 = (1,0)，c3 = (1,1) 表示该4个色。今对 进行边着色如下：将的每边着以被它所分隔的两个面的色的和。 （设与顶点v相关联的3个面上的色为ci，cj，ck。则与顶点v相关联的3条边上的色为ci+cj，cj+ck，ck+ci。） 因的每边恰分隔两个不同的面（∵其每边为非割边），因此没有一边被着以色c0 ，从而上述边着色是一3-边着色。又，易见，关联于每个顶点的3条边被着以不同色 。因此上述边着色是正常3-边着色。 ③ ( ① ：反证，假设①不成立，则存在简单平面图G使 ((G) = 5。令为其平面嵌入。由习题9.2.6及9.2.7知，为某简单平面三角剖分图H的生成子图；且H的几何对偶H* 是简单、2-边连通、3-正则平图。于是我们可得以下之 断言 H* 是4-面可着色的。 由上述断言得： 5 = ((G) ( ((H) = (*(H* ) ( 4 , 矛盾，从而定理得证。 下面来证断言： 由③知，H* 有一正常3-边着色 （E1，E2，E3）。 易见，每个Ei 是H* 的一个完美匹配。令 Hij* = H*[Ei ( Ej] i ( j ， 则Hij* 是一些不相交圈的并。从而，易见，Hij* 是2-面可着色的。 注意到，H* 的每个面一定包含在H12* 的一个面及H23* 的一个面的交中。由H12*及H23* 上的2-面着色，可得H* 的4-面着色如下： 将每个H* 的每个面f ，着以包含f 的H12* 的面上的色 (12（=0，1） 及包含f 的H23* 的面上的色(23 （=0，1）组成的色对（(12，(23 ）。易见，这4-面着色是正常的。（设H* 的两个面f及f’有公共边e，每个面上的色分别为（(12，(23）及（(‘12，(‘23）。则，例如，当e ( E1时，必有 (12 ( (‘12 ，从而f及f’有不同色。） # 习题 9.5.1. 证明：2-边连通图G是2-面可着色的当且仅当G是Euler图 。 9.5.2.* 证明：平面三角剖分图G是3顶点可着色的当且仅当G是Euler图 。 9.5.3. 证明：每个Hamilton平图都是4-面可着色的。 9.5.4. 证明：每个Hamilton3-正则图都有Tait着色（即，3正则图的正常3-边着色）。 9.5.5. 按③ ( ② ( ① ( ③的顺序证明定理9.12。  9.5.6. 设G是(( = 2的3-正则图。 (a) 证明：存在G的子图G1和G2及不相邻的顶点对u1 ,v1 ( V(G1) 和 u2 ,v2 (V(G2)，使得G由图G1和图G2 以及在顶点u1,v1,u2,v2上由‘梯子’连接的图所组成。 (b) 证明：若G1 + u1v1 和G2 + u2v2 都有Tait着色，则G也有Tait着色。 (c) 根据定理9.12证明：四色猜想等价于Tait猜想，即每个简单3-正则、3-连通、平面图都有Tait着色。 9.5.7. 给出满足下列条件的例子各一个： (a) 不具有Tait着色的3-正则平面图； (b) 不具有Tait着色的3-正则、2-连通图。 平面性算法 设H为G（不一定为平面图）的真子图，称（边导出）子图B为G相对于桥（bridge），如果 ① B为边uv， u,v ( V(H) ，且 uv ( E(G)\E(H) 。 ② B为 G - V(H) 的一个分支，以及G中V(H)与该分支之间的连接边，所组成的子图。 易见，若B为H的一个桥，则 ① B为连通图； ② 对B中任二顶点x与y，B中存在一(x, y)-路内部不交于H。 称V(B) ( V(H)为接触顶点(vertices of attachment)。当G连通时，每个桥至少有一个接触顶点。 设H为G的平面子图，称其 平面嵌入为G-可容许的（G-admissible） ( G为平面图，且存在G的平面嵌入 (  。  例。 称H的桥B可画（drawable）在的一个面f中 ( B对于H的接触顶点全包含在f的周界上。 记号 F(B, ) = 使B可画于其中的的面的集合。 定理9.4 若 为G可容许的，则对H的任一桥B都有 F(B, ) ( ( 。 证明：由定义，存在G的平面嵌入 (  。B所对应的的子图必画在的一个面中，故 F(B, ) ( ( 。 # 显然， G为平面图 ( G的基础简单图的每个块都是平面图。因此，平面性问题只须考虑简单块之情形。 以下算法对简单块G求出其平面子图的增序列G1，G2，……及其平面嵌入1，2，……。当G为平面图时，每个i为G可容许的，且1，2，…… 终止于G的一个平面嵌入。 平面性算法（Demoucron，Malgrange & Pertuiset 1964） 令G1为G的一个圈。求G1的一个 平面嵌入1 。令 i = 1。 若E(G)\E(G1) = ( ，停止（完毕，得 ）。否则，找出G中Gi的所有桥，并对每个桥求出集合F(B,i ) 。 若存在B使 F(B,i ) = ( ，停止（由定理9.14，G为非平面图）。若存在B使 |F(B,i)| = 1，取f为 F(B,i ) 中的面；否则，任取一桥B，并且取 F(B,i )中任一面为f。 (4) 选一连接B对Gi的二接触顶点的路Pi ( B。令 Gi+1 = Gi ( Pi。通过把Pi 画在 i 的面f中，得 Gi+1 的平面嵌入i+1 。 算法证明大意 只要再证对平面图G算法不会停止于(3)。由定理9.14，只要证明算法求出的 1，2，…… 为G可容许的即可。  1 显然是G可容许的。设1，……，k 为G可容许的，来证k+1 也是G可容许的。由定义知，存在G的平面嵌入 ( k。令B，f为(3)中所取的桥和面。 ① 若在中B恰好画在f中（ 当|F(B,k) | = 1时，必是此情形 ）：由(4)知，k+1 为G可容许的。 ② 若在中B被画在 k 的另一面f′中： 这时的所有桥B都有 |F(B,k) | ( 2 。因此总可将 中被画在f中的桥 与被画在f′中的桥 通过公共周界进行交换，得G的另一平面嵌入，其中B恰好被画在f中，得前面的情形① 。   例。判定以下二图的平面性： 算法中要进行的运算为： 块中找一个圈G1。 在G中确定Gi的所有桥及它们对Gi的接触顶点。 对的每个面f确定b(f)。 对每个桥B确定F(B, i ) 。 在Gi的某个桥B中，找连接其二接触顶点的路P。 上述1. ~ 5. 都有好算法，因此平面性算法是好算法。 习题 9.6.1. 用本节的算法证明Petersen图是非平面图。 有向图 有向图 有向图（directed graph；digraph） D = ?（V，A）：  V(D) —— 顶点集。 A(D) —— 弧集。 弧a = (u,v) ：其头为 v，其尾为u；弧a从u连到（join to）v。 有向子图（subdigraph）。 有向图D的基础图（underlying graph） ( 对应于D的无向图G。  （称D为G的一个定向（orientation）图。） （无向）图的每个慨念，在有向图中仍然有效。 例如，右图是2-连通图；有Hamiton 圈；有完美匹配；( = (( = 3；vrswu是它的一条(v,u)-路；vyzwsrv是它的一个圈，等等。此外，有向图还有一些与方向有关的慨念，如有向途径（directed walk）、有向迹（directed trail）、有向路（directed path）、有向Euler环游（direted Euler tour）、有向圈（directed cycle）等等。例如上右图中， (v,e1,x,e2,y,e3,z,e4,w.e5,u) 为一 有向（v,u)-路，可简记为 （v,x,y,z,w,u) ； (y,z,w,s,r,x,y) 为一 有向圈。 称顶点v从u可达的（reachable from u） ( 存在有向（u，v）-路。 称顶点u与v为双向连通的（diconnected；strongly connected） ( u与v彼此可达的。 易见，双向连通性是V上的一个等价关系，它的等价类确定了V的一个划分（V1，……，Vm)，使 顶点u与v双向连通 ( u与v 同属某等价类Vi 。 称每个导出子图D[V1]，……，D[Vm]为有向图D的一个双向分支（dicomponent；strong component）。当D只有一个双向分支时，称D为双向连通的。易见，任二双向分支之间的弧都是一个方向的。  例。  入度（indegree）  。 出度（outdegree） 。 记号 (+，(( ：最小出、入度； (+ ， (- ：最大出、入度。 称有向图D为严格的（strict） ( 无环、且无二弧其端点及方向相同。 习题 10.1.1. 一个简单图有多少个定向图？ 10.1.2. 证明：  = ( =  。 10.1.3. 设有向图D中无有向圈，则 (a) (( = 0 ； (b) 存在一个顶点排序v1，……，v( ，使对1 ( i ( ( ，每条以vi为头的弧其尾都在{v1，……，vi-1} 中。 10.1.4. 证明：D是双向连通的 ( D是连通的，且D的每个块是双向连通的。 10.1.5. D的逆图 是把D中每弧的方向都改为其反向所得的有向图。试用逆图慨念及习题10.1.3.(a) 来证明： 若有向图D中无有向圈，则(+ = 0 。 10.1.6. 证明：严格有向图包含长 ( max{(( ，(+}的有向路。 10.1.7. 证明：严格有向图中若max{(( ，(+} = k ( 1，则D包含长( k+1 的有向圈。 10.1.8. 设( (( 矩阵A = [aij ]为有向图D的邻接矩阵，其中aij 是D中以vi为尾、以vj为头的弧数。证明：Ak的第(i,j)元素是D中长为k的（vi ,vj)-有向途径的数目。 10.1.9. 设D1，……，Dm为D的双向分支。D的凝聚图H是一有m个顶点w1，……，wm的有向图。H中存在以wi为尾、以wj为头的弧，当且仅当D中存在尾在Di 、而头在Dj中的弧。证明：H中不包含有向圈。 10.1.10. 证明：任一图G都有一个定向图D，使对每个顶点v都有|d+(v) - d-(v)| ( 1。 有向路 易见，有向图中最长路的长和最长有向路的长之间并无任何密切的关系，例如下面的有向图最长路的长为( （可任意大） ，而最长有向路的长为1。  定理10.1 (Roy,1967; Gallai,1968) 有向图D包含一长为 ( - 1 的有向路。 证明：令D( 为D的极大无有向圈、有向生成子图（注：D( 可由空生成子图作为开始，在保持无有向圈的条件下，通过逐步加弧而得） 。令k为D( 中最长有向路的长。今用色1，2，……，k+1对D( 进行顶点着色如下： 将v着以色i ( D( 中以v为起点的最长有向路的长为i - 1 。 来证这是D的正常(k+1)-顶点着色： 先证，D( 中任一有向(u,v)-路P的起、终点u与v一定不同色：设v被着以色i 。则由着色法知，在 D( 中以v为起点的一最长有向路，设为，Q的长为i - 1 。由于D( 中无有向圈，PQ为一有向路，起点为u，长 ( i 。从而u上的色j > i。 只要再证，D中任一弧(u,v)的两端一定不同色：当 (u,v)为D( 中的弧时，它就是D( 中的一有向(u,v)-路，从而u与v不同色。当 (u,v)不是D( 中的弧时，由D( 之极大性知 D( + (u,v) 包含一有向圈C。于是， C - (u,v) 是 D( 中的有向(v,u)-路，从而u与v也不同色。 由上述知，D为(k+1)-可着色的，因此 ( ( k+1 ，得k ( ( - 1 ，故D中有长为( - 1 的有向路。 # 注 定理10.1在如下意义下是最佳的： 对每个（无向）图G，都存在G的一个定向图，其最长有向路的长恰为( - 1。 证明：令 （V1，……，V(-1） 为G的正常 ( -顶点着色。今作G的定向图D如下： 边uv（不妨设， u ( Vi ，v ( Vj）定向为弧 (u,v) ( i < j 。 显然，D中不含长 > ( - 1的有向路。再由定理10.1得证。 # 称完全图的定向图为竞赛图（tournament） 推论10.1 (Redei,1934) 每个竞赛图都有一Hamilton 路。 证明：注意到( = ( 即可。 # 设(u,v)为有向图D中的一弧，则称u为v的内邻点（in-neighbour）；称v为u的外邻点（out-neighbour）。记  和  分别为有向图D中顶点v的内邻集和外邻集。 定理10.2 (Chavtal & Lavasz,1974) 无环有向图D包含一独立集S，使D中的每个不在S中顶点，都是从S中某顶点通过长 ( 2的有向路可达的。 证明：对( 进行归纳。当 ( = 1时，显然成立。假设定理对顶点数 < ( 成立，而D的顶点数 = ( （( 2）。任取D的一顶点v，由归纳假设知 D’ =D -（ ( {v}） 中有一独立集S’，使D’中的每个不在S’中顶点，都是从S’中某顶点通过长 ( 2的有向路可达的。在D中， ① 若v是S’中一顶点u的外邻点：则在D中，的每个顶点都可从u用长 = 2的有向路可达的，因此取S = S’即可满足要求。 ② 若v不是S’中任一顶点u的外邻点，则 S’中顶点都与v不相邻，这时独立集 S = S’ ( {v}满足要求。 # 推论10.2 每一竞赛图都包含一顶点，使其它顶点都是从它用长 ( 2的有向路可达的。 证明：注意到 ( ( 1 即可。 # 习题 10.2.1. 证明：每个竞赛图或者是双向连通的，或者是只要将其中某一弧改向就可变成双向连通的。 10.2.2.* 称有向图D是单连的（unilateral），当且仅当对于D中任二顶点u和v，或者v是从u可达的，或者u是从v可达的。证明：D是单连的当且仅当D有一条生成有向途径。 10.2.3.(a) 设P = （v1，……，vk）是竞赛图D中的一条极大有向路。如果P不是有向Hamilton 路，而v是不在P上的任一顶点，证明：存在某个i，使(vI, v)和(v, vI+1)都是D的弧。 (b) 证明：Redei定理。 10.2.4. 通过考察最大出度顶点来证明推论10.2。 10.2.5* (a) 设D是( > mn的有向图，而f是定义在V上的一个实函数。证明：D中或者存在一有向路(u0，u1，……，um) 满足f(u0)( f(u1)( ……( f(um)；或者存在一有向路 (v0，v1，……，vn) 满足f(v0)>f(v1)>……>f(vn) 。 (b) 试证：任意mn+1个不同整数的序列中，或者包含一个m项的递增子序列；或者包含一个n项的递减子序列 10.2.6.(a) 利用定理10.1和推论8.1.2证明：G有一个定向图，它的最长有向路的 长( ( 。 (b) 给出(a)的构造性证明。 圈 记号 （S，T）是D中尾在S内而头在T内的所有弧的集合。（S，T是V的子集）  定理10.3 (Moon,1966) ( ( 3的双向连通竞赛图D中，每个顶点包含在一有向k-圈中，3( k ( ( 。 证明：设u是D的任一顶点。用对k的归纳法来证明。当 k =3时， 令S = N+(u) ， T = N-(u) 。由D的双向连通性知， S，T，（S，T） 都是非空的。 因此D中存在一弧(v, w) 使v ( S，w ( T 。从而u在有向3-圈 (u,v,w,u) 中，结论成立。 假设对每一k，3 ( k ( n < ( ，u都在有向k圈中，来证u也在有向（n+1)-圈中：令 C = （v0，v1，……，vn）， 其中v0 = vn = u。 为一有向n-圈。 若V\V(C)中存在一顶点v，它既是尾在C中的一弧的头，又是头在C中的另一弧的尾：则易见，C中存在相邻的两个顶点vi和vi+1， 使(vi , v)和(v, vi+1 )都是D的弧。于是u在有向(n+1)-圈 (v0，v1，……，vi，v，vi+1，……，vn) 中（其中v0 = vn = u）。 否则，V\V(C) 可划分为二不相交集S与T，使连接S和C的每一弧的头都在S中；使连接T和C的每一弧的尾都在T中。由D的双向连通性知  S，T，（S，T） 都是非空的。 且D中存在一弧（v，w） 使 v ( S，w ( T。 从而D中存在有向(n+1)-圈 (v0，v，w，v2，……，vn) 其中v0 = vn = u。 结论也成立。 # 定理10.4 (Ghouila-Houri ,1960) 设D为严格的，且 min{(-，(+} ( (/2 > 1，则D包含一有向Hamilton 圈。 证明：反证，假设D不包含有向 Hamilton 圈。令 C = （v1，v2，……，vq，v1） D中一最长有向圈。易见，C的长 q > (/2（习题10.1.7)。 令P为 D - V(C) 中的一条最长有向路，其长为m，其起、终点分别为u和v。显然， ( ( q +m + 1 (1) m < ( /2 (2) 记 S = { i | (vi-1, u) ( A} ， T = { j | (v, vj) ( A} 。 则，首先有 S ( T = ( 。 （否则，假设 i ( S ( T ，则 Ci，i-1(vi-1，u) P( v, vi ) （Ci，j表示圈C的（vi，vj）-节） 为D 中有向圈，其长为 q+m+1 ，这与C的选择相矛盾。）后面我们将推导出以下 断言 |S ( T| ( q - m + 1 ，且S，T ( ( 。 (3) 于是，由 S ( T = ( 及 S，T ( ( 知， 存在 i，k > 0 使 i ( S， i+k ( T （ mod q ）  i+j( S ( T （ mod q ） 1 ( j < k 。 (4) 由(3)，(4)可得 k ( m 。 于是，D中存在一有向圈 Ci+k，i-1 (vi-1 , u) P (v , vi+k) ， 它的长 = q + m + 1 - k ( q + 1，矛盾。 来证断言：首先注意到，由于P为D - V(C)中的最长有向路，我们有  ， ∴  。 但  ， ∴ |S| ( (/2 - m 。 (5) 类似地 |T| ( (/2 - m 。 (6) ∴ |S ( T| = |S| + |T| ( ( - 2m ( (q + m + 1) - 2m (由(1)) = q - m +1 。 再由(2)及(5),(6)得 S，T ( ( 。 # 习题 10.3.1. 试用定理10.4推出定理4.3 。 10.3.2. D的有向Euler环游是指遍历D的每一弧恰好一次的有向闭途径。证明：D包含有向Euler环游 当且仅当 D是连通的，且对每个顶点有 d+(v) = d-(v) 。 设有向图D满足： ① d+(x) - d-(x) = m = d-(y) - d+(y) ; ② d+(v) = d-(v) , 对 ( v ( V\{x,y} 。 利用习题10.3.2.证明：D中存在m条弧不重的有向（x，y）-路。 10.3.3.* 证明：包含奇圈的双向连通有向图也包含有向奇圈。 10.3.4. 称非平凡有向图D是k-弧连通的，如果对V的每个非空真子集S，都有 |(S, (S)| ( k 。证明：非平凡有向图是双向连通的当且仅当它是1-弧连通的。 10.3.5. 图G的伴随有向图D(G)是指把G的每边e都用两条相反方向而和e有相同端点的弧代替所得的有向图。证明： (a) G中的路 和D(G)中的有向路 之间存在一一对应 ； (b) D(G)是k-弧连通的当且仅当G是k-边连通的。 工件排序问题 设一机器要加工几种工件J1，J2，……，Jn ；每当加工完一种工件Ji后，为了加工下一工件Jj ，机器必须用tij时间进行调整。 问题 求加工顺序，使总调整时间最短。 ( 在赋权（tij）有向图（V(D) = {J1，J2，……，Jn }，每对顶点间有二反向弧连接）中求一最小权有向Hamilton 路。 （如果生产过程是反复进行，则问题变成求最小权有向Hamilton 圈 。） 注 在赋权有向图中求最小权有向Hamilton 圈（路）问题是NP-hard prob. 。 代替办法 （Heurestic alg. ) 1. 作有向图D, 使V(D) = {v1，……，v(}，且 (vi, vj) ( A(D) ( tij ( tji ( i ( j 2. 在D中找一有向Hamilton 路P作为工作排序。（有‘好’算法）  注。 本算法去掉了矩阵[ tij ] 中较大的那一半，因此‘有理由’期望得到较好的结果。当然，这只是一种一厢情愿的想法而已。例如，右图情况下，“去掉了矩阵[ tij ] 中较大的那一半”后，得到的是右图中用直线段构成的竞赛图，其中的最短Hamilton 有向路的长为12；而最优解为4。 又，注意到“去掉了矩阵[ tij ] 中较大的那一半”后所得赋权图（包含竞赛图）中求该图的最小权Hamilton 有向路问题，由前述知，仍然是NP-hard 困难问题。 公路系统的单行线化 问题 任给一图G是否有一双向连通定向图？ 显然，G有一双向连通定向图 ( G为2-边连通图。 定理10.5 (Robins,1939) G为2-边连通图 ( G有一双向连通定向图 。 证明：由G为2-边连通知，G中含一圈G1 。归纳地定义G1，G2，……如下：若Gi不是G的生成子图，任取G不在Gi中的一个顶点vi 。由习题3.2.1.，易见，存在 vi 到Gi 的两条边不重的路Pi和Qi 。定义 Gi+1 = Gi ( Pi ( Qi 。 由于((Gi+1) > ((Gi) ，该序列一定终止于G的一生成子图Gn上。 今对Gn定向如下：把G1定向为一有向圈； 把Pi定向为一以vi为起点的有向路；把Qi 定向为以vi为终点的有向路。显然，每个Gi有一双向连通定向。由于Gn是G的一生成子图，G也存在双向连通定向图。 定理（Nash-Williams ，1960） G为2k-边连通的 ( G有k-弧连通定向图。 （证略） （即 |（S，(S ）| ( k ( ( ( S ( V） 上述定理的特殊情形为以下定理， 其证明较容易，留给读者来完成： 定理10.6 G为2k-边连通，且有一Euler 迹 ( G有一k-弧连通定向图。 习题 10.5.1 通过(考察Petersen图证明以下结论不成立：每个图都有一定向图，使得对每个S ( V，（S， ）和（，S）的弧数相差最多为1。 10.5.2. (a) 证明Nash-Williams定理下述命题： 若G的每个键至少有2k-条边，则存在G的一个定向图，其中每个键在每个方向上都至少有k-条弧。 (b) 通过考察Grotzsch图证明以下结论不成立：若G的每个圈至少有2k-条边，则存在G的一个定向图，其中每个圈在每个方向上都至少有k-条弧。 网络 流  一个网络（Network）N是由一有向图（称为基础有向图（underlying digraph）；二特定的不相交顶点子集X和Y；以及弧集A上定义的非负整数值函数c(()（称为容量函数） 组成的。其中，X的每个顶点称为发点（source）；Y的每个顶点称为收点（sink）；I = V \ (X ( Y)中每个顶点称为中间顶点（intermediate vertex）；每弧a上c(a)的值称为a的容量（capacity）。 设f(.)为定义在弧集A上的实函数，对任一弧子集K，记  。 当K=（S，(S ）时，记 f+(S) = f(S,(S) 。 类似地，记 f-(S) = f((S, S) 。 由此，特别地，有 f+(v) = ( {v}, V\{v} ) ； f -(v) = ( V\{v), {v} ) 。 定义在A(D)上的整数值函数f(·)若满足以下条件，就称为网络N上的流（flow）： ① 0 ( f(a) ( c(a) ， ( a ( A(D) 。 称为容量约束（capacity constraint）。 ② f+(v) = f -(v) ( v ( I 。 称为守恒条件（conservation condition）。 注 f(a)可当作物资沿弧a输送的流量。但不能将流当作水的流动！ 零流（zero flow）f ( f(a) = 0 ， ( a ( A(D)。 设f是网络N上的流，而S是其顶点子集。称 f+(S) - f-(S) 为流出S的合成流（resultant flow out of S） f-(S) - f+(S) 为流进S的合成流（resultant flow into S） 容易证明（习题）， f+(S) - f-(S) =  f+(X) - f-(X) = f-(Y) - f+(Y) （记为） = valf 称为流f的值 。 最大流（maximum flow）f ( 不存在流f＇使val f＇ > valf 。  求解最大流问题时，为简化计，可将多收、发点问题转化为单收、发点问题 ，如右图所示：往N中加两顶点x和y作为新网络N＇的发点和收点；并用容量为∞的一条新弧将x连接到X中每个顶点； 用容量为∞的一条新弧将Y中每个顶点连接到y。 N和N＇中的流f和f＇之间有一简单的对应关系：当f满足条件 f+(xi) - f-(xi) ( 0 ( xi ( X ； f-(yj) - f+(yj) ( 0 ( yj ( Y ； （不难证明，对求解最大流问题只要考虑这种情形就够了。）可定义f＇如下  易见，f＇确实是N＇上的流，且 valf＇= valf （习题） 反之，N＇的任一流f＇在N的弧集上的限制（restriction）f是N上的流，且 valf = valf＇（习题）。 由上述知网络N和N＇有相同的最大流的值，为简单计以下三节中将只讨论单收、发点之情形。 习题   11.1.1. 对于下列各网络，确定所有可能的流和最大流的值： 11.1.2. 证明：对N中任一流f及任一S ( V，都有  = f+(S) - f-(S) 。 11.1.3. 证明：对N中任一流f 有 f+(X) - f-(X) = f-(Y) - f+(Y) 。 割 设网络N只有一个收点x及一个发点y， S ( V(D) 。称 （S，(S ）为N中的 割（cut） ( x ( S， y ( (S 。 称 cap K =  为割 K = （S，((S ）的容量。 引理11.1 对N中任一流f及任一割（S，(S ） 有 valf = f+（S）- f-（S）。 证明：注意到  ， 因此有 valf =  = f+(S) - f-(S) 。 # 称弧a为： f-零的 ( f(a) = 0 ； f-正的 ( f(a) > 0 ； f-不饱和的 ( f(a) < c(a) ； f-饱和的 ( f(a) = c(a) 。 定理11.1 对N中任一流f及任一割K =（S，(S ）有 valf ( cap K ； 又，上式中等号成立 ( （S，(S）中每弧为f-饱和的， 且 （(S，S）中每弧为f-零的 。 证明：由容量约束知 f+(S) ( cap K (1) f-(S) ( 0 (2) 再由引理11.1知定理的第一个结论成立。又， (1)中等号成立 ( （S，(S）中每弧为f-饱和的 ； (2)中等号成立 ( （(S，S）中每弧为f-零的 ； 从而定理的第二个结论也成立。 # 最小割（minimum cut） ( 不存在割K 使 cap K < cap 。 显然，若 f* 为最大流，为 最小割，则 valf * ( cap 。 推论11.1 设 流f 及 割K 使 valf = cap K ， 则f为最大流，K为最小割。  习题 11.2.1. 在右图所示的网络中：求所有的割；求最小割的容量；并证明由粗体字所指出的流是最大流。 11.2.2. 证明：若N中不存在有向(x,y)-路，则其最大流的值及最小割的容量都是零。 11.2.3. 若( S,(S )和( T,(T )都是N中的最小割，证明：( S ( T, ) 和也都是N中的最小割。 最大流最小割定理 设f为网络N中的流，P为N中一条路，令  ；  =  。 称路P为 f-饱和的 (  = 0 ; f-不饱和的 (  > 0 ; f-可增路（f-incrementing path）P ( P是以发点x为起点，以收点y为终点的 f-不饱和路 。 若N中有一f-可增路P，则，易见，f不是最大流。这时，可沿P输送一附加流 而得一新流 f′：  。 (11.9) 这时， valf′= valf +  ， 并称 f′为基于P的修改流（revised flow based on P）。 定理11.2 N中的流f为最大流 ( N不含f-可增路 。 证明：( ： 反证，若N中含一f-可增路P，则f不是最大流，因为基于P的修改流 f′的值更大。 ( ： 令 S = { v | ( f-不饱和（x，v）-路} ， 则显然有 x ( S ； y ((S ； ∴ K = （S，(S ） 为割。 注意到，这时（S，(S ） 的任一弧 a = （u，v）一定是f-饱和的。否则，由于存在f-不饱和（x，u）-路Q， Q可通过a延伸为f-不饱和（x，v）-路，从而 v ( S，矛盾。 类似地，（(S，S）中任一弧 一定是f-零的。 因此，由定理11.1知，valf = cap K 。从而由推论11.1知，f为最大流。 # 定理11.3 (max-flow min-cut theorem , Ford & Fulkerson ,1956) 在任一网络中，最大流的值 = 最小割的容量。 上定理是图论的一重大结果，其它图论结果，例如，偶图的匹配、Menger定理等，可由它利用适当选取网络来导出。 求最大流的算法 原理 ： 以一已知流f（例如，零流）作为开始。 系统搜索f-可增路P。若P不存在，停止（f-为最大流）。 若P存在，求出基于P的修改流f′，令 f ( f′，并转到2°。 系统搜索f-可增路P标号法 （通过标号‘生长’f-不饱和树T） 开始，标x以l(x) = ( 。 （此后，在T的生长过程中，T中每个顶点 将标 以 l(v) = ( (Pv) ，其中Pv是T中惟一的(x, v)- 路。） (1) 若 a = （u，v）为f-不饱和弧，且u已标号， 而v未曾，则标v以 l(v) = min{ l(u), c (a) - f (a) } 。 (2) 若 a = （v，u）为f-正的，且u已标号，而v未曾，则标v以 l(v) = min{ l(u), f(a) } 上述标号过程一直进行到：或者y已标号（“breakthrough”，找到了f-可增路）；或者所有已标号顶点都已扫描，但无顶点可再标号（f为最大流）。 标号程序 （labelling method，Ford & Fulkerson ,1957) 以已给流f（例如，零流）作为开始。 ① 标x以 l(x) = ∞。扫描 （scan） x 。 ② 对正在扫描的（已标号）顶点u， (i) 检查每条以u为尾的弧 a = （u，v）。如果 a 为f-不饱和的，且顶点 v未标号，则标v以 l(v) = min{ l(u), c (a) - f (a) } 。 (ii) 检查每条以u为头的弧 a = （v，u）。如果 a 为f-正的，且顶点v未 标号，则标v以 l(v) = min{ l(u), f(a) } 。 ③ 若y已标号（‘break through’，找到了一条f-可增路），则转到④ ；否则选一未曾扫描的已标号顶点进行扫描，并回到②。如果已标号顶点都已扫描过，停止（得最大流。且由已标号顶点集S，得最小割（S，(S） ）。 ④ 找一f-可增路P，令  f (  ， 去掉全部标号，并回到① 。  注 上述算法还不是‘好’算法，例如右图中的网络，其最大流的值为2m。但若标号程序以零流开始，且反复地选取xuvy及xvuy为 f-可增路，则总共要进行2m+1次标号程序，因此其计算量为输入长（= O(log2m) )的指数函数。 Edmonds & Karp (1970) 证明，若在上述标号程序中采用first labelled first scan （即广度优先）法则，则，可使该算法成为好算法（复杂性为O(((2 ) ) 。 习题 11.3.1. 证明：由(11.9)式给出的函数f是valf′= valf +  的流。  11.3.2. 试求右图所示网络的最大流。（答：最大流的值=39） 11.3.3. 证明：在具有整数容量的任一网络N中，总存在一最大流f，使f(a)在每一弧a上都取整数值。 11.3.4. 考察在每条弧a上都伴随一整数 b(a) ( c(a)的网络N，试修改标号法，来求N中满足条件 b(a) ( f(a) ( c(a) , ( a ( A , 的最大流f。 （假设存在满足这个条件的初始流）。 11.3.5. 设网络N的每个中间顶点v都伴随一非负整数m(v)。试修改该网络，并将标号法应用于它，来求出满足条件 f -(v) ( m(v) , ( v ( V \ {x,y}， 的最大流f。 11.3.6 试用网络理论证明Hall定理（第五章）。 Menger 定理 引理11.4 设网络N的发点为x，收点为y，且每弧的容量都为1，则 (a) N中最大流的值 = N中弧不重的有向(x,y)-路的最大数目m。 (b) N中最小割的容量 = 破坏N中所有有向(x,y)-路所需去掉的最少弧数n。 证明：(a) 令f*为N中在每弧上取整数值的最大流；D* 为由D中去掉所有f*-零弧而得到的有向（生成子）图。显然， f*(a) = 1 ( a ( A(D* ) 。 因此，有 ①  ； ②  ( v ( V \ {x，y} ； 于是，由习题10.3.3.知，D*中，因而D中，有valf * 条弧不重的有向（x，y）-路。因此 m ( valf * 。 另一方面，设P1，……，Pm为N中任一组m条弧不重的有向（x，y）-路，定义函数 f(a) =  显然，f为N中值为m的流。由于f* 为最大流，得 valf* ( m ， 从而 valf* = m 。 (b) 令  = (S,(S )为N中的最小割，则易见N -  中从x不可达y。即  就是去掉它就破坏所有有向(x,y)-路的弧集，因此 n ( || = cap 。 另一方面，设Z为n条弧的集合，去掉Z后就破坏所有有向（x,y)-路。令S为N - Z中x可达的顶点集。显然，x ( S， y ((S ，从而 K = (S,(S )为N中的一个割。又，由S的定义知，N-Z中不含 (S,(S )的弧，因此 K ( Z，从而 cap ( capK = |K| ( |Z| = n ， ∴ n = cap 。 # 定理11.4 设x和y为有向图D中任二顶点，则 D中弧不重的有向(x,y)-路的最大数目 = 破坏D中所有有向(x,y)-路所需去掉的最少弧数。 证明：由D作网络N：其发点为x，收点为y，每弧容量1。再用引理11.4及 定理11.3即得。 # 定理11.5 设x和y为图G中任二顶点，则 G中边不重的(x,y)-路的最大数目 = 破坏G中所有(x,y)-路所需去掉的最少边数。 证明：作图G的伴随有向图（associated digraph），再用定理11.4即得。 # 推论11.5 (Menger 定理） G为k-边连通的 ( G中任二顶点都至少被k条边不重的路所连接。 证明：由k-边连通定义即得。 # 定理11.6 设x和y为有向图D中二不同顶点，且D中没有连x到y的弧，则 D中内部不相交的有向(x,y)-路的最大数目 = 破坏D中所有有向(x,y)-路所需去掉的最少顶点数。 证明：由D作有向图D’ 如下： ① 将每个 v ( V \ {x., y} 分成二新顶点v’ 及v’’ ，并连以新弧(v’,v’’)； ② 将D中以 v ( V \ {x., y} 头的弧代之以以 v’ 为头的弧；以v为尾的弧代之以以 v’’ 为尾的弧。 于是易见，D’ 中一有向(x,y)-路与D中一有向(x,y)-路之间存在1-1对应关系（通过将D’中一有向(x,y)-路上的每一(v’, v’’ )弧收缩成v；或将D中一有向(x,y)-路的每一顶点v分裂成弧(v’, v’’ )）。 又，易见， D’ 中二有向(x,y)-路为弧不重的 ( 对应的D中的二有向(x,y)-路为内部不 相交的。 因此， D’ 中弧不重的有向(x,y)-路的最大数目 = D中内部不相交的有向(x,y)-路的最大数目。 类似地，破坏 D’中所有有向(x,y)-路所需去掉的最少弧数。 = 破坏D中所有有向(x,y)-路所需去掉的最少顶点数。（习题11.4.1.) 再用定理11.4，定理得证。 # 定理11.7 设x和y为图G中二不相邻顶点，则 G中内部不相交的(x,y)-路的最大数目 = 破坏G中所有(x,y)-路所需去掉的最少顶点数。 证明：将定理11.6用于G的伴随有向图上即得。 # 推论11.7 （Menger 定理）设 ((G) ( k + 1，则 G为k-连通的 ( G中任二不相同顶点至少被k条内部不相交的路 所连接。 证明： 显然。 # 习题 证明在定理11.6的证明中提到的命题：破坏 D’中所有有向(x,y)-路所需去掉的最少弧数 = 破坏D中所有有向(x,y)-路所需去掉的最少顶点数。 从定理11.7导出Konig 定理。 设S和T是图G中二 不相交顶点子集。证明：起点在S、终点在T的 顶点不相交的路的最大数目 = 把S和T分离开来所需去掉的最少顶点数。（即，去掉后没有一个分支同时包含S和T中的顶点） * 证明：若G为k（ ( 2 ）-连通图，则G的任何k个顶点共圈。 可行流 在网络N的每个发点xi 上指定一非负整数((xi)，称为供给（supply）；在每个收点yj上指定一非负整数(yj)，称为需求（demand）。称N中的流 f为可行流（feasible flow） ( f+(xi) - f -(xi) ( ((xi) ( xi ( X； f -(yj) - f+(yj) ( (yj) ( yj ( Y。 问题 存在可行流的充要条件是什麽？ 记 ((S) =  ；  。 定理11.8 (Gale,1957) N中存在可行流 ( c(S, (S ) ( (Y ((S) - ((X ( (S) ( S ( V。 证明：由N作N’ 如下： ① 往N里添加二新顶点x及y； ② 从x到每个xi (X 连以容量为((xi) 的弧； ③ 从每个 yj ( Y到y 连以容量为 (yj) 的弧； ④ 将x和y分别当作N’ 的发点和收点 。 易见，N中有可行流 ( N’有一个流使割(Y, {y})中每一弧都饱和。 （习题11.5.1.) 但N’中对应流的值 = (Y) = cap(Y,{y}) 。由推论11.1知， 它是N’中的最大流，故 N中有可行流 ( 对N’ 中每一割(S({x}，(S ({y})都有 cap(S ( {x}，(S ({y}）( (Y) 。 但 cap(S ( {x}，(S ({y}） = c’(S,(S) + c’(S,{y}) + c’({x},(S ) (c’(.)表示N’中的容量函数） = c(S,(S) + (Y ( S ) + ((X ((S ) ， 而 (Y) = (Y ( (S ) + (Y ( S ) ，得证。 #