图论及其应用19537

《图论及其应用19537》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

图和子图图和简单图图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。简单图：（simplegraph）无环，无重边平凡图：仅有一个顶点的图（可有多条环）。一条边的端点：它的两个顶点。记号：。习题1.1.1若G为简单图，则。1.1.2n(³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)之间各存在一一对应关系，且这二对应关系保持关联关系。记为GF。注往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。58 注判定两个图是否同构是NP-hard问题。完全图(completegraph)Kn空图（emptyg.）ÛE=Æ。V’(ÍV)为独立集ÛV’中任二顶点都互不相邻。二部图（偶图，bipartiteg.）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.1G@HÞn(G)=n(H),e(G)=e(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).e(Km,n)=mn;(b).对简单二部图有e£n2/4.1.2.6记Tm,n为这样的一个完全m-部图：其顶点数为n，每个部分的顶点数为[n/m]或{n/m}个。证明：(a).e(Tm,n)=其中k=[n/m].(b)*.对任意的n顶点完全m-部图G，一定有e(G)£e(Tm,n)，且仅当G@Tm,n时等式才成立。1.2.7所谓k-方体是这样的图：其顶点是由0与1组成的有序k-元组，其二顶点相邻当且仅当它们恰有一个坐标不同。证明k-方体有个顶点，k*2k-1条边，且是一偶图。1.2.8简单图G的补图Gc是指和G有相同顶点集V的一个简单图，在Gc中两个顶点相邻当且仅当它们在G不相邻。(a).画出Kcn和Kcm,n。58 (b).如果G@Gc则称简单图G为自补的。证明：若G是自补的，则nº0,1(mod4)关联矩阵M(G)与邻接矩阵A(G)M(G)=[mi,j]n*e,A(G)=[ai,j]n*n,其中mi,j=顶点vi与边ej的关联次数=0,1,2.ai,j=连接顶点vi与vj的边数。例。子图子图(subgraph)HÍGÛV(H)ÍV(G),E(H)ÍE(G)。真子图HÌG。母图（supergraph）。生成子图（spanningsubg.）ÛHÍG且V(H)=V(G)。生成母图。基础简单图（underlyingsimpleg.）。导出子图（inducedsubg.）G[V’],(非空V’ÍV)Û以V’为顶点集，以G中两端都在V’上的边全体为边集构成的G的子图。边导出子图G[E’]非空E’ÍEÛ以E’为边集，以E’中所有边的端点为顶点集的的子图。例。58 以上两种子图，其实，对应于取子图的两种基本运算。下面是取子图的另两种基本运算：G-V’Û去掉V’及与V’相关联的一切边所得的剩余子图。Û即G[VV’]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[EE’]与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为一完全图，10)的2-划分为(X,Y),则|X|=|Y|。1.5.3在人数>1的人群中，总有二人在该人群中有相同的朋友数。58 1.5.4设V(G)={}，则称(d(v1),d(v2),......,d(vn))为G的度序列。证明：非负整数序列(d1,d2,......,dn)为某一图的度序列Û是偶数。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。内部顶点（internalvertex）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,......,Vw使每个Vi中的任二顶点u及v都连通（即存在(u,v)-路）。称每个G[Vi]i=1,2,......w为G的一个分支（component）;称w(G）为G的分支数。G为连通图Ûw(G)=1ÛG中任两点间都有一条路相连。G为非连通图Ûw(G)>1。记号对任一非空SÌV，令=VS,记（称为边割）[S,]=G中一端在S中，另一端在中的一切边的集合。例。（命题）G连通Û对任SÌV都有[S,]¹Æ例。（命题）简单图G中，d³kÞG中有长³k的路。习题1.6.1证明：G中长k为的(vi,vj)-途径的数目,就是Ak中的(I,j)元素。1.6.2证明：对简单图G有，58 ÞG连通。对于n>1，试给出的不连通简单图。1.6.3简单图G中，d>[n/2]-1ÞG连通。当n是偶数时，试给出一个不连通的([n/2]-1)正则简单图。1.6.4G不连通ÞGc连通。1.6.5对任意图G的任一边e，有w(G)£w(G-e)£w(G)+1。1.6.6G连通，且d(v)=偶数，"vÎVÞw(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。圈闭途径（closedwalk)Û起点=终点且长>0的途径。闭迹(closedtrail)Û边各不相同的闭途径。圈（cycle）Û顶点各不相同的闭迹。（可当作一图或子图。）例。闭途径：uyvyu;uywxywvu；uyuyu。闭迹：uyxwyvu。圈：yfvgy;uywvu。k-圈（k-cycle）Û长为k的圈。例。1-圈（即一条环），2-圈(由重边组成），3-圈（又称三角形）。奇圈(oddcycle)。偶圈(evencycle)。定理1.2G为二部图Û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不能相邻，不然，页码:6v(P’)-1Q’wv将是一奇圈，矛盾。#例。（命题）图G中d³2ÞG中含圈。例。（命题）简单图G，d³2ÞG含长e³d+1的圈。58 例。（命题）任一图中(a).e³nÞ含圈。(b)*.e³n+4Þ含二条边不重的圈。习题1.7.1若边e在G的一闭迹中，则e在G的一圈中。1.7.2证明：(a).e³nÞG含圈。(b)*.e³n+4ÞG含两个边不重的圈。最短路问题赋权图（weightedg.)(权º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(u0,u1)£d(u0,u2)£......记S0={u0},Sk={u0,u1,.............,uk}，=VS。Pi为最短(u0,ui)-路i=1,2,......(1).u1：u1是使w(u0u1)=min{w(u0v)½v¹u0}者.得S1=S0È{u1},P1=u0u1.(2).若已求得Sk-1;d(u0,u1),.........d(u0,uk-1);及最短(u0,ui)路Pii=1.2,...,k-1.uk：显然，d(u0,uk)=min{d(u0,v)|vÎ`}=d(u0,uj)+w(ujuk)某jÎ{1,2,......,k-1}=min{d(uo,u)+w(uuk)|uÎSk-1}=min{d(u0,u)+w(uv)|vÎ`,uÎSk-1}=min{l(v)|vÎ}其中，l(v)=min{d(uo,u)+w(uv)|uÎSk-1}(l(uk)=d(u0,uk))Sk=Sk-1È{uk},Pk=Pjujuk某jÎ{1,2,......,k-1}。update进行下一步时，只要更新l(v)即可：l(v)¬min{l(v),l(uk)+w(ukv)}"vÎDijkstra算法(1).作为开始：l(u0)¬0;l(v)¬¥"v¹u0;S0¬{u0};k¬0.(2).（这时已有Sk={u0,u1,.............,uk}）58 l(v)¬min{l(v),l(uk)+w(ukv)}"vÎ再计算min{l(v)}，设其最小值点为uk+1，令Sk+1=SkÈ{uk+1}。(3).若k=n-1,仃止；不然，令k¬k+1,并回到(2)。计算复杂性加法：n(n-1)/2比较：n(n-1)/2´2vÎ：(n-1)2+)________________________________________________共O(n2)凡是复杂性为p(n,e)的算法(p(.,.)为一多项式)称为“好算法”(“goodalgorithm”------J.Edmonds)。这是相对于指数型算法而言的：在10-6秒/步运算速度下：复杂性n=1020304050n3.001sec.008sec.027sec.064sec.125secn5.1sec3.2sec24.3sec1.7min5.2min2n.001sec1.0sec17.9min12.7days35.7years由上表可见，两种算法有天壤之别。注1.若只关心求d(u0,v0)则算法进行到v0ÎSk时停止。2.计算过程中，所得子图是一棵树。每步都是往其上增加一条边及一个顶点，因此该过程称为treegrowingprocedure。3.若要计录u0到每个顶点u的最短路，只要记录下该路中u的前一个顶点即可。习题1.8.1描述一个算法以确定(a).一图的各个分支；(b).一图的围长（即最短圈的长）。并说明你的算法好到什么程度。树树无圈图（acyclicg.；林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为无圈图相矛盾。#58 注意(1).当G无环时，易见，G是树ÛG中任二顶点间有唯一的路相连。(2).以下结论不一定成立：$闭途径Þ$圈。定理2.2G是树Þe=n-1。证明：对n进行归纳。当n=1时，G=K1，成立。假设定理对小于n个顶点的树成立，而G为n个顶点的树。任取G的一边uv。它是G中的一条路，由定理2.1知，G-uv不连通，且它恰有二分支（习题1.6.5），设为G1与G2。它们都是连通无圈图，因此是树。又，它们的顶点数都小于n。由归纳假设知e(GI)=n(GI)-1I=1,2.故，e(G)=e(G1)+e(G2)+1=n(G1)+n(G2)-1=n(G)-1。#推论2.2每棵非平凡树至少有两个度为1的顶点。证明：由于G为非平凡连通图，d(v)³1,"vÎV。再由定理1.1及2.2知，，由此知推论成立。例。（命题）恰只包含二度为一顶点的树是路。习题2.1.1证明：非平凡树中，任一最长路的起点和终点均是度为1的顶点。再由此去证明推论2.2。2.1.2当e=n-1时，证明以下三结论是等价的：(a)G是连通图；(b)G是无圈图；(c)G是树。2.1.3一树中若D³k，则其中至少有k个度为1的顶点。2.1.4G为林Ûe=n-w。2.1.5若林G恰有2k个奇点，则G中存在k条边不重的路P1,P2,..,Pk,使得E(G)=E(P1)ÈE(P2)È...ÈE(Pk)。2.1.6正整数序列(d1,d2,...,dn)是一棵树的度序列，当且仅当。2.1.7饱和烃分子形如CmHn,其中碳原子的价键为4，氢原子的价键为1，且任何价键序列都不构成圈。证明：对每个m，仅当n=2m+2时CmHn方能存在。割边和键e为割边(cutedge)Ûw(G-e)>w(G)。（即w(G-e)=w(G)+1）定理2.3e为G的割边Ûe不在G的任一圈中。证明：令e=xy，则x与y在G的同一分支中。于是，e为G的割边Ûw(G-e)=w(G)+1Ûx与y不G-e在同一分支中58 ÛG-e中无(x,y)-路ÛG中无含e的圈。#定理2.4图G连通，且每边是割边ÛG为树。证明：注意到以下事实即可，G无圈ÛG中每边不在任一圈中ÛG中每边是其割边。#连通图G的生成树（spanningtree)ÛG的生成子图，且为树。推论2.4.1每一连通图都包含一生成树。证明：令T为极小(minimal)连通生成子图（意指T的任一真子图都不是连通生成子图）（由定义，T可在保持连通性的前提下，用逐步从G中去边（所去的边一定在一圈中（即非割边））（每次破坏一圈）的办法求出。由T的定义知，w(T)=1，w(T-e)=2"eÎE(T)。即T的每边为割边，故由定理2.4知T为树。#注也可用极大无圈（生成）子图（即其真生成母图都含圈）来求生成树T。它可由V上的空图开始，在保持无圈的前提下，逐步由G中取边的办法求出。（为何是生成树？）推论2.4.2GÞe³n-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连通，且e=n-1ÛG连通。且e=n-1。图G的边割（edgecut）[S,]SÌVÛG中一端在S另一端在中的边的子集合。显然，在连通图G中，E’Ê边割Ûw(G-E’)>1。键（bond,割集cutset)Û极小非空边割。例。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的极小子集。Ûw(G-B)=2，且中每边的两端点分别在二分支中。58 边割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的一生成树（因其边数=n-1，且连通），从而G-B’连通，这与B’为G的键相矛盾。#附录设G连通，T为其任一生成树。对每一eÎ`T，T+e中有唯一圈C，因而可得C1,C2,......,Ce-n+1共e-n+1个不同的圈，每个称为G的一个基本圈。同样，对每一eÎT，`T+e中有唯一的键因而可得B1,B2,......,Bn-1共n-1个不同的键，每个称为的一个基本割集。设S1,S2为二集合，记其对称差(即（S1ÈS2）-（S1ÇS2）)为S1ÅS2称为它们的环和(ringsum)。性质1)图G的每一边割是G的一些割集的边不重并。2)设B1,B2为图的任二边割，则B1ÅB2也是G的边割。（对任二非空V1,V2ÌV，有[V1,V1]Å[V,V]=[V2,V2],其中V3=(V1ÇV2)È(`V1Ç`V2)）。3)设边子集E’与E”分别为G中一些圈的边不重并，则E’ÅE”亦然。4)G的每个圈可唯一地表为G的一些基本圈的环和。5)G的每个边割可唯一地表为G的一些基本割集的环和。6)边子集E’为G中一些边不重圈的并集Û边子集E’与G中每个边割有偶数条公共边。1)边子集B为G的一个边割Û边子集B与G的每个圈有偶数条公共边。7)G为一些圈的边不重并Ûd(v)=偶数"vÎV习题2.2.1设G连通且eÎE，证明：(a)e在G的每棵生成树中当且仅当e是G的边割。(b)e不在G的任一生成树中当且仅当e是G的环。58 2.2.2无环图G恰只有一棵生成树T，则G=T。2.2.3设F是G的极大（maximal）林，证明：(a)对G的每个分支H，FÇH是H的生成树；(b)e(F)=n(G)-w(G)。2.2.4证明：任一图G至少包含e-n+w个不同的圈。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的割点(cutvertex)ÛE可划分为二非空子集E1及E2，使G[E1]与G[E2]只有一公共顶点v。显然，当G无环时，v为割点Ûw(G-v)>w(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仍然是树。因此w(G-v)=1=w(G)，从而v不是割点。(iii)若d(v)>1，则G中存在与v相邻接的二不同顶点u,w。由定理2.1知，uvw是G中的唯一(u,w)-路，因此G-v中不含(u,w)-路，（即G-v中u,w不连通）w(G-v)>1，即v为G的割点。#推论2.7非平凡、无环、连通图中，至少有二顶点不是割点。证明：令T为G的一生成树，由推论2.2及定理2.7知，T中至少存在二顶点u与v不是T的割点，则它们也不是G的割点：这是因为对于u(及v)有1=w(T-u)³w(G-u)³1，∴w(G-u)=1=w(G)。#习题58 2.3.1设G为n³3的连通图，证明：(a)若G有割边，则G有顶点v使w(G-v)>w(G)；（即，割边必有一端点为割点）(b)(a)的逆命题不成立。2.3.2证明：恰有二顶点为非割点的简单连通图必是一条路。2.3.3在简单连通图G中证明：v为G的割点ÛG的任一生成树不以v为叶。生成树的计数及Caley公式本节只讨论无环连通图。将图G的关联An´e矩阵中每列的两个1元素之一改为-1，得一新矩阵，记为Aa（它是G的一个定向图的关联矩阵）。例如：记A为从Aa中删去某一行所得的(n-1)´e矩阵。引理1设A1为A的任一(n-1)阶子方阵，则det(A1)=±1ÛA1的列对应于G的一生成树。证明：令划去的行对应于顶点u，记H为以全体与A1的列相对应的边构成的生成子图。由于e(H)=n-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]n´n，其中58 例如对本节开头的例子有定理连通图G的生成树数目=K的任一元素的代数余子式证明：容易验证，K=AaAaT。又，K的任一行（列）的元素的代数和=0，因此K的所有代数余子式都相等。再，设Ak为从Aa中去掉第k行所得的(n-1)´e矩阵，易见，AkATk=从K中去掉第k行第k列后所得的子方阵故由引理2知本定理成立。#例。前例的图的生成树数目=K的(2,3)-元素的代数余子式==8。定理（Cayley）　Kn中共有　nn-2个不同的生成树。证明：用上述定理可直接证出（习题）。　　　　#习题2.4.1求Ｋ３，３的生成树数目。2.4.2若ｅ是Ｋｎ的一条边，　则　Ｋｎ－ｅ的生成树数目为　(n-2)nn-3。连线问题问题设城市vi与vj间建立直接通信线路的费用为cij（³0）。建设连接{}的通讯网使造价最省Û在赋权图G中求一最小权连通生成子图；Û在赋权图G中求一最小权生成树（最优树）。下面的Kruskal算法是在非赋权图中求生成树的“极大无圈子图”算法的改进，它是一种贪心算法（greedyalgorithm）：Kruskal’salgorithm(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.10Kruskal算法求出的生成树=G[{e1,e2,...,en-1}]是最优树。证明：反证，假设T*不是G的最优树。取G的一最优树T。令ek为{e1,e2,...,en-1}中（58 按顺序）第一个不属于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’连通，且其边数=n-1。）又，由于T的子图G[{e1,e2,...,ek-1}È{e’k}]也不含圈，由法算法知w(ek)£w(e’k)∴w(T’)£w(T)，即T’也是G的最优树，且{e1,e2,...,en-1}中第一个不属于T’的边的下标>k。这与k的取法相矛盾。#实现先按权的不减顺序将边集重排成a1,a2,...,ae。关于算法中无圈性的判定，我们有一简单的办法：当S={e1,e2,...,ei}已取定时，对候选边ajG[SÈ{aj}]无圈Ûaj的两端点在林G[S]（此处当作生成子图）的不同分支中。从而我们有求最优树的标记法：开始：取a1为候选边；并将vk标以k，k=1,2,...,n。若S={e1,e2,...,ei}已取定，当候选边aj的两端点有相同标号时，改取aj+1为候选边（丢掉aj永不再考虑）；否则选定ei+1=aj，并将G[S]中aj两端点所在的二分支的顶点重新标号，标以两者中的最小者。算法复杂性边排序O(e×log2e)比较边两端的标号e重新标号O((n-1)n)故为好算法（£O(n3)）。附录（A）Prim’salgorithm（也是一种贪心算法）T¬Æ,V’¬{u}forallvÎ`V’doL(v)¬w(uv)//initializingL(.);`V’=VV’while`V’¹Vdobeginfindvertexws.t.L(w)=min{L(v)|vÎ`V’}anddenotetheassociatededgefromV’towbyeT¬TÈ{e},V’¬V’È{w}forallvÎ`V’do//updatingL(v)fromnewvertexwL(v)¬ifw(vw)0)。当G为简单图时，k¢=n-1ÛG@Kn。称图G为k-边连通的（k-edgeconnected）Ûk¢(G)³kÛ至少去掉k条边才能使G变成不连通或平凡图。例如，所有非平凡连通图都是1-边连通的。称顶点子集V’为G的顶点割(vertexcut)ÛG-V’不连通。称顶点子集V’为G的k-(顶)点割(vertexcut)ÛV’为G的顶点割，且|V’|=k。显然，当G为无环连通图时，v为G的1-点割Ûv为G的割点。完全图无点割。G的连通度(connectivity)（=使G变成不连通或平凡图所需去掉的最少的顶点数。）例。当n³3时，k=1ÛG连通且有1-点割。k(Kn)=n-1。k(G)=n-1ÛG的基础简单图为完全图。称图G为k-连通的（k-connected）Ûk(G)³kÛ至少去掉k个顶点才能使G变成不连通或平凡图。例如，所有非平凡连通图都是1-连通的。定理3.1k£k¢£d。58 证明：先证k¢£d：当G为平凡图时，k¢=0£d，结论成立；当G为非平凡图时，选取v使d(v)=d,则E’=是G的一个边割，因此k¢£|E¢|£d结论成立。再来证k£k¢：不妨设G为简单、连通、非完全图，于是k¢£n-2。任取一k¢-边割B，及B中任一边e=xy。今，在B-e的每边上各取一个端点使之不等于x及y。令这些端点的集合为S。易见，|S|£k¢-1。记H=G-S。(i)若H不连通，则S为G的点割，从而k£|S|£k¢-1。(ii)若H连通，则e=xy为H的割边。但，n(H)=n(G)-|S|³n-(k¢-1)³3，因此，x与y必有一个为H的割点，设为x。于是SÈ{x}为G的点割，故k£|S|+1£k¢。#习题3.1.1(a)证明：若G是k-边连通的，且k>0，又E’为G的任k条边的集合，则w（G-E’)£2。(b)对k>0，找出一个k-连通图G以及G的k个顶点的集合S，使w(G-S)>2。3.1.2证明：若G是k-边连通的，则e³kn/2。3.1.3(a)证明：若G是简单图且d³n-2，则k=d。(b)找出一个简单图G，使得d=n-3且k1,NP-hardprob.当每边权º1且G为任意图时，问题变成求边数最少的k-连通生成子图。(仍然是NP-hardprob.)当G@Kn且每边权为1时，Harary(1962)作出边数最少的G的k-连通（k-边连通）生成子图Hk,n（边数={kn/2})（∴有好算法。）Hamilton圈与Euler环游Euler环游环游（tour）Û通过图中每边至少一次的闭途径。Euler环游Û通过图中每边恰一次的闭途径。Euler迹Û通过图中每边的迹。Û通过图中每边恰一次的途径。（可“一笔画成”。）Euler图Û包含Euler环游的图Û包含Euler闭迹的图。Û本身为闭迹的图。定理4.1设G为非空连通图，则G为Euler图ÛG中无度为奇数的顶点。证明：Þ：令C=u0e1u1e2u2...eeue(ue=u0)为G的一Euler环游，起点为u0。则对任一顶点v¹u0，当v每次作为内部顶点出现于C时，C上有二边与v相关联。由于C上包含了G的所有边且不重复，因此d(v)=偶数。类似地，d(u0)=偶数。Ü：反证，假设存在非空连通图，它的每个顶点的度都是偶数，但却不是Euler图。在这种图中选取G使其边数最少。由于d(G)³2，G包含圈。令C为G中的最长闭迹。由假设，C不会是Euler环游。因此G-E(C)中一定有一分支G’使e(G’)>0。由于C本身为Euler图，（由定理的必要条件知）C中每个顶点的度都是偶数，因此G’中无度为奇数的顶点。但e(G’)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算法（“过河拆桥，尽量不走独木桥“）1.任取一顶点v0，令w0=v0。2.若迹Wi=v0e1v1...eivi已取定，选ei+1ÎE{e1,...,ei}使(i)ei+1与vi相关联；(ii)除非无奈，选ei+1使它不是Gi=G-{e1,...,ei}的割边。3.若2.不能再进行下去，停止。定理4.7若G为Euler图，则由Fleury算法求得的G中的迹，是G的一Euler环游。证明：令Wn=v0e1v1...envnFleury算法求得的G中的迹，显然dGn(vn)=0,vn=v0。58 假设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)相矛盾。#定理之另证：其实只要再证以下断言即可：断言在算法进行过程中，每个Gi都是G的生成子图，其中只有一个分支是非空的（即其余分支每个都是孤立顶点），且vi与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）(书：“SelectedTopicsinGraphTheorey2”,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.EdmondsandE.L.Johnson解决（1972）。Hamilton圈Hamilton路Û生成路（spanningpath）Hamilton圈Û生成圈Hamilton图Û包含Hamilton圈的图定理4.2G为Hamilton图Þw(G-S)£|S|"SÌV58 证明：令C为G的一个Hamilton圈,则对任一SÌV必有w(C-S)£|S|，但w(G-S)£w(C-S)。#注意，定理4.2之逆不成立。例如，Pertersen图满足定理条件，但它是非Hamilton图。约定本节只讨论简单图。定理4.3（Dirac，1952）n³3的简单图G中，若d³n/2，则G为Hamilton图。证明：反证，设G为n³3满足d³n/2的极大非Hamilton简单图。（即任取一反例，在保持其为非Hamilton、简单图的前提下，尽量加边，直到不能再加为止。取之为G。）因n³3，G不能是完全图。任取G中二不相邻接顶点u及v，则G+uv为Hamilton图，且其中的每个Hamilton圈均含边uv。从而G中有Hamilton路v1v2............vn其中v1=u,vn=v。令S={vi|uvi+1ÎE}T={vj|vjvÎE}易见，vnÏSÈT，|SÈT|n/2，则G为Hamilton图。4.3.7.n³5个人围桌而坐，总有一新就座法，使每人的邻座都不相同。4.3.8.对下列问题给出一好算法：(a)构造一个图的闭包。(b)若某图的闭包为完全图，求该图的Hamilton圈。4.3.9.对任正整数n，完全3-部Kn,2n,3n为Hamilton图；而完全3-部Kn,2n,3n+1为非Hamilton图旅行售货员问题(travellingsalesmanprob.)问题在赋权完全图中找最小权Hamilton圈（最优圈）。（NP-hardprob。）（问题任给一图G，G是否为Hamilton图？（NP-completeprob。））代替办法找一reasonablygoodsolution。例如，先找一Hamilton圈C=v1v2...vnv1，再加以改进：对任i与j,1|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.5G的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是简单图，n是偶数，且d³1+n/2，则G有3-因子。5.1.6*证明：K2n+1可表为n个连通的2-因子的并。5.1.7证明：任连通偶图G=（X,Y,E）的2-划分（X，Y）是唯一的。58 偶图的匹配和覆盖邻集（neighbourset）N(S)（SÍV）：G中所有与S中顶点相邻接的顶点集合。定理5.2（Hall’stheorem,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。显然，SU与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(marriagetheorem)若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中。最小覆盖（minimumcovering）。对G中任一覆盖K及任一匹配M，显然，恒有½M½£½K½。特别地，有½M*½£½½。引理5.3设M与K分别为G中的匹配与覆盖，如果½M½=½K½则M为最大匹配，K为最小覆盖。（证明：略）定理5.3(Konig’stheorem,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与SU中顶点在M*下相匹配；N(S)=T。记58 =(XS)È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及e>(k-1)n，则G有边数为k的匹配。5.2.7*由Konig定理推导Hall定理。5.2.8*若非负实数矩阵Q的每行元素之和均为1，每列元素之和也均为1，则称Q为双随机矩阵。称一矩阵为置换矩阵如果它是每行和每列均恰只有一个1元素的（0，1）矩阵（∴是双随机的）。证明：(a)每个双随机矩阵一定是个方阵；(b)每个双随机矩阵Q都可表为置换矩阵的凸线性组合，即Q=c1P1+c2P2+……+ckPk。其中每个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的奇分支（oddcomponent）ÛH为G的分支，且其顶点数为奇数。称H为G的偶分支（evencomponent）Û……。记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中至少有一顶点ui与S中一顶点vi在M下相匹配。从而o(G-S)=n=½{v1，……，vn}½£½S½。58 Ü：反证。假设存在图G满足条件（*），但不含完美匹配。令G*为G的不含完美匹配的极大生成母图。由于G-S是G*-S的生成子图，o(G*-S)£o(G-S)£½S½"SÌV。即G*满足条件（*），又，上式中令S=Æ得o(G*)=0，因此n(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}中M1DM2的边导出子图H。显然，H中顶点的度都是2，因而H是一些圈的不相交并。且每圈都是偶圈，由M1与M2的边交错组成。情况1xz与yw不在H的同一圈中：设yw在圈C上，则C中所有M1边及C外所有M2边一起构成G*的一个完美匹配，矛盾。情况2xz与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-正则图，且n是偶数，则G有完美匹配。5.3.3设G为一树，证明：G有完美匹配Ûo(G-v)=1"vÎV。5.3.4*证明Tutte定理的推广：G的最大匹配的边数=(n-d)/2，其中（C.Berge)人员分派问题问题n个工人x1，……，xn及n个工作y1，……，yn，已知每个工人都胜任一些工作。能否使每个工人都分派到一件他所胜任的工作？（（thepersonnel）assignmentprob.)解在偶图G=(X,Y,E),½X½=½Y½,中求出其完美匹配（若存在的话）。Hungarianmethod(Edmonds,1965)以任一匹配M作为开始。（可取M=Æ）58 ①若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¬MDE(P)，并回到①。注1算法用生长“以u为根的M-交错树”的方法，来系统地搜索M-可扩路。树中除u外都是M-饱和的，直到碰到第一个M-不饱和的顶点时，即得一M-可扩路。当树不能再生长下去时，即为N(S)=T之时。注2本算法是个‘好’算法：从一个M到下一个，至多进行½X½次搜索运算；M至多扩大½X½次。习题5.4.1试述如何利用Hungarian算法求偶图的最大匹配。Optimalassignmentproblem问题求赋权图G=Kn，n的最大权匹配。称l为（feasiblevertexlabelling)（f.v.l.)Ûl为V上的实函数，且满足：l(x)+l(y)³w(xy)"xÎX，yÎY。例。下面是一可行顶点标号：记(相等子图，equalitysubgraph）Û以为边集的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-Munkeralgorithm（1955，1957；Edmonds改写（1967））以任f.v.l.l作为开始。定，并在上任取一匹配M作为开始的匹配。①若M饱和X的每个顶点，则M为最优匹配，停止；否则，任取一M-不饱和顶点u，S¬{u}，T¬Æ。58 ②若ÉT，转到③；否则，=T。计算=及f.v.l.：l¬，¬。③选取yÎT，若y为M-饱和的，则存在yxÎM，作S¬SÈ{x}，T¬TÈ{y}，并转到②；否则，令P为中的M-可扩-(u,y)路，M¬MDE(P)，并转到①。注1算法中每计算一次新的的计算量为O(n2)；在找到M-可扩路之前，至多进行½X½次搜索（每次可能作一次新的的计算）；而初始匹配M至多扩大½X½次。因此是个‘好’算法（计算复杂性为O(n4))注2本算法也可用于解人员分派问题。习题5.5.1所谓n×n矩阵的一条对角线是指它的任n个两两不同行、不同列元素的集合。对角线的权是指它的n个元素的和。试找出下列矩阵的最小权对角线：（答：权=30）边着色边色数前提本章只讨论无环图。k-边着色（k-edgecolouring）CÛk种色在图G的边集上的一种分配。ÛC是E(G)的一个k-划分，即C=（E1，。。。，Ek）（注：允许Ei=Æ）边着色C是正常的Û每个Ei都是G的一个匹配。G为k-边可着色的（k-edgecolurable）ÛG有一正常k-边着色。Û存在E(G)的一个k-划分C=（E1，。。。，Ek），使每个Ei都是G的一个匹配。（注：允许Ei=Æ）（显然，G为k-边可着色的ÞG为l-边可着色的（l³k））G的边色数（edgechromaticnumber）c¢(G)=min{k½G为k-边可着色的}G为k-边色的（k-edgechromatic）Ûc¢(G)=k。58 例。n个人举行一些两两会谈，每次会谈用一个单元时间。问最少要多少单元时间，才能安排完所有会谈？例。Peterson图有c¢=4。显然，c¢³D。称色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图每个顶点的度均为偶数）。令v0e1v1e2。。。eeve为G一的Euler环游（ve=v0）。令E1与E2分别为Euler环游中下标为奇数与偶数的边子集。则G的2-边着色C=（E1，E2）满足要求。(B)若G为非Euler环游：往G中加一新顶点v0，并将v0与G中每个度为奇数顶点都用一新边连起来，得图G’。显然，G’为一Euler图。令v0e1v1e2。。。eeve（ve=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-边着色（optimalk-edgecolouring）Û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)+1c(v)³c(v)"v¹u这与C为最优矛盾。#定理6.1设G为偶图，则c¢=D。证明：反证，假设c¢>D。令C为G的一个最优D-边着色，而uÎV为使c(u)0，则G有一d-边着色，使所有d种色在每一顶点上都表现。Vizing定理定理6.2(Vizing,1964)对简单图G有c¢=D或D+1。证明：（Bollobas）不妨设G中除uv1外都已用色1,2,……,D+1进行了正常边着色。注意到，G的每个顶点上都至少有一色未表现。令u，v1各有色i0，i1未表现。我们可逐步找到不同的色、边序列：i0，i1，i2，……，ij，……；uv1，uv2，……，uvj，……。其中，色ij是顶点vj上未表现的（任意取定的）一色；边uvj有色ij-1。j=2，3，……。显然，上述过程至多进行到某l（£D）次而停止（无法继续满足上述条件）。这时只有两种可能：(A)色il未表现于顶点u上（即没有一条u的关联边uvk有色il）：重新进行边着色如下uvj改着色ij1£j£l-1并抹去边uvl上的色il-1。得G中除uvl外的正常（D+1）边着色。其中u与vl　上色il同时不表现。将uvl改着色il即得G的正常（D+1）边着色。(B)il=ik某1£k£l-1：重新进行边着色如下将uvj改着色ij1£j£k并抹去边uvk+1上的色ik。易见，H=的每个分支是路或圈，由色i0与ik的边交错组成，且u，vk+1，vl在H中的度£1。从而，该三顶点不可能同时在H的一分支中。这时只有二可能情形：58 ①u与vk+1不在H的同一分支中：将H的含vk+1分支中的色i0与ik对换，得G的除uvk+1外的正常（D+1）-边着色，其中u与vk+1上色i0都未表现。从而，G有一正常（D+1）-边着色。②u与vl不在H的同一分支中：再继续调整边着色如下，将uvj改着色ij并抹去边uvl上的色（il-1）k+1£j£l-1。易见，上述更动并未涉及色i0与ik，因此H保持不变。将H中含u分支的色i0与ik对换，得G的除uvl外的正常（D+1）-边着色，其中u与vl上色i0都未表现。从而，G有一正常（D+1）-边着色。#注1对一般图有Vizing定理设G为无环图，则D£c¢£D+m，其中m是G的重数（连接G中每一顶点对上的最大边数）。注2NP-completeprob。已给简单图G，是否有c¢=D？注3“2-边连通、3-正则、简单、平面图都有c¢=3”Û“4-色猜想成立”。习题6.2.1*找出适当的边着色以证明c¢(K2N-1)=c¢(K2N)=2n-1。6.2.2n为奇数的非空正则简单图G有c¢=D+1。6.2.3(a)设简单图G中n=2n+1且e>nD，则c¢=D+1；(b)利用(a)证明：①若G是从有偶数个顶点的简单图中剖分一条边所得的图，则c¢=D+1；②若G是从有奇数个顶点的简单k正则图中删去少于k/2条边所得的图，则c¢=D+1。6.2.4(a)证明：任一无环图G都有D-正则无环母图。(b)利用(a)及习题5.2.3(b)证明：若G是无环图且D是偶数，则c¢£3D/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’且vn’ÎE(H)；或v=v’且uu’ÎE(G)(a)利用Vizing定理证明：c¢(G×K2）=D(G×K2)。(b)试证：若H是非平凡的，且c¢(H)=D(H)，则c¢(G×H)=D(G×H)。6.2.7叙述求简单图G的正常(D+1)-边着色的好算法。6.2.8*证明：d≥2的简单图G有一(d-1)-边着色，使得所有d-1种色在每个顶点上都表现。排课表问题问题m位教师X1，……，Xm和n个班级Y1，……，Yn，其中教师Xi要给班级Yj上pij节课。欲在最少节次p内排完所有的课。Û将偶图G=(X,Y,E)(½X½=m，½Y½=n)的边集E划分成互不相交的p个匹配(E1，……，Ep)Û求偶图G的c¢（=D=p）-边着色。由习题6.1.4知，上述问题有好算法。当上述问题中若教室数有限时（教室数≥），若要在p（³D）节内排完全部l（=½E½）节课，所需教室数c³。58 问题能否适当排课，使全部l节课在p（³D）节内排完，且每节课所用教室数£？（∴"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’=MDE(P)及N’=NDE(P)即为所求。定理6.3设G为偶图，p³D，则存在G的p个互不相交的匹配使E=M1È……ÈMp。且1£i£p。证明：由定理6.1,E可划分为D个互不相交的匹配M1¢，……，MD¢。因此，对p³D，G有p个互不相交的匹配M1¢，……，MD¢，……，Mp¢。（令Mi¢=Æ当i>p)使E=M1¢È……ÈMp¢。对边数差>1的两个匹配，重复使用引理6.3，最后可得所求的匹配M1，……，Mp。#注在实际应用中，教师和班级往往会提出一些，例如所上节次，的要求，问题变得很复杂。Even，Itai&Shmir（1976）证明：在教师和班级提出条件时，判定课表的存在性问题是个NP-complete问题。甚至当G为简单偶图，且学生不提出要求的情况下，也是如此。独立集和团独立集定理7.1S为图G的独立集ÛVS为G的覆盖。证明：S为独立集Û不存在两端全在S中的边ÛG的每边至少有一端在VS中ÛVS为G的覆盖。#SÍV为G的团（clique）ÛG[S]为一完全图。独立数（independentnumber）a(G)Û最大独立集的元素个数。覆盖数（coeringnumber）b(G)ÛG的最小覆盖的元素个数。推论7.1a+b=n。证明：设S为G的最大独立集，则VS为其覆盖，因此b£|VS|=n-a。又，设K为G的最小覆盖，则VK为其独立集，因此a³|VK|=n-b。∴a+b=n。#58 注由上述证明知S为G的最大独立集ÛVS为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）。色数（chromaticnumber）c(G)={k½G为k-可着色的}。G为k-色图Ûc(G)=k。G为临界的（crtical）Ûc(H)i，相邻接。又，x1与x2不相邻。于是，贪心着色法只用了£D个色。#习题8.2.1.证明Brooks定理等价于下述命题：若G是k-临界图（k³4），且不是完全图，则2e³n(k-1)+1。8.2.2.利用Brooks定理证明：若G是D=3的无环图，则c¢£4。围长和色数易见，若G中最大团的顶点数k，则c³k。下面的定理表明，一个有很大色数的图，其最大团的顶点数不一定也很大。定理8.7对任正整数k，都存在不含K3的图G使c(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为新加的顶点。将每个ui与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如下：取kn个新顶点集S及G的个互不相交的拷贝，且建立G的拷贝与S的n个顶点的一一对应。再将G的每个拷贝与它在S中相对应的n个顶点之间用一匹配连接起来。证明：H的色数至少为k+1，其围长至少6。(b)试证：对任k³2，都存在围长为6的k-色图。58 平面图平图和平面图图G可嵌入（embededable）于平面中ÛG可画在平面上，使它的边只在端点处才可能相交叉。（该画法称为G的一个平面嵌入（planarembedding）或平图（planegraph））ÛG为平面图（planargraph）例。K5，K3,3以及它们的剖分都是非平面图。它们中任一个去掉任一边后都是平面图。注意平面图和平图间的区别。后者是前者的一个几何实现（具体画法）。Jordan曲线定理平面中任一Jordan曲线J（连续不自交的闭曲线），将余下的平面划分成二不相交开集：J的内部（interior）和J的外部（exterior），分别记为intJ和extJ。（它们的闭包分别记为IntJ和ExtJ）。连接intJ中一点到extJ中一点的任一条曲线一定与J交于某一点。定理9.1K5为非平面图。证明：反证，假设G为K5的一个平图。令G的五个顶点为v1，……，v5。注意到圈C=v1v2v3v1为平面上的一条Jordan曲线，且v4必在intC或extC中。若v4ÎintC，则边v4v1，v4v2，与v4v3将intC划分成三个区域intC1，intC2，和intC3。这时v5一定在上述三个区域及区域extC之一。若v5ÎextC，则因v4ÎintC，边v4v5必与C交于某一点，这与G为平面图的假设相矛盾。其它情形类似地也导致矛盾。#定理9.2.’K3,3为非平面图。证明：类似，略。平面嵌入的慨念可推广到其它平面上。称图G可嵌入于曲面S上　ÛG可画在S上，使它的边仅在端点处才可能相交叉。例。K5和K3,3都可嵌入于环面上；K3,3可嵌入于Mobius带上；每个图都可“嵌入”于三维空间R3中。定理9.2G可嵌入于平面上ÛG可嵌入于球面上。证明：利用球极平面射影，略。#对偶图平图G的面（face）ÛG将平面划分出来的连通区域的闭包。外部面（exteriorface）ÛG中唯一的无界面。定理9.3.对平面图G的任一顶点，都存在G的一个平面嵌入，使它在该嵌入的外部面上。58 证明：先将G嵌入于球面上，并将球面的北极放在含该顶点的G的一个面中，再利用球极平面射影。#记号F(G)=平图G的面的集合。f(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的对偶图（dualgraph）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*的定义易知：n(G*)=f(G)e(G*)=e(G)定理9.4设G为平图，则58 证明：。#习题9.2.1.(a)证明：图G是平面图ÛG的每个块都是平面图。(b)试证：极小非平面图是简单块。9.2.2.若一平图和它的对偶图同构，则称该平图为自对偶的。(a)若G为自对偶的，则e=2n-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)c(G**)=c(G)。9.2.5.设T是连通平图G的生成树，E*=。证明：T*=G*[E*]是G*的生成树。9.2.6.每个面的度都是3的平图称为平面三角剖分图。证明：每个n³3的简单平图都是某简单平面三角剖分图的生成子图。9.2.7.设G是n³4的简单平面三角剖分图，证明：G*是简单2-边连通3-正则平面图。9.2.8.*证明：任何平面三角剖分图，都包含一个有2e(G)/3条边的偶子图。Euler公式定理9.5(Euler)设G为连通平图，则n-e+f=2。证明：对f进行归纳。当f=1时，G的每边为割边（因每边只分隔一个面）。又因G连通，从而G是树（定理2.4)，于是e=n-1，定理成立。假设定理对fi。只要再证，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)-可着色的，因此c£k+1，得k³c-1，故D中有长为c-1的有向路。#注定理10.1在如下意义下是最佳的：对每个（无向）图G，都存在G的一个定向图，其最长有向路的长恰为c-1。58 证明：令（V1，……，Vc-1）为G的正常c-顶点着色。今作G的定向图D如下：边uv（不妨设，uÎVi，vÎVj）定向为弧(u,v)Ûic-1的有向路。再由定理10.1得证。#称完全图的定向图为竞赛图（tournament）推论10.1(Redei,1934)每个竞赛图都有一Hamilton路。证明：注意到c=n即可。#设(u,v)为有向图D中的一弧，则称u为v的内邻点（in-neighbour）；称v为u的外邻点（out-neighbour）。记和分别为有向图D中顶点v的内邻集和外邻集。定理10.2(Chavtal&Lavasz,1974)无环有向图D包含一独立集S，使D中的每个不在S中顶点，都是从S中某顶点通过长£2的有向路可达的。证明：对n进行归纳。当n=1时，显然成立。假设定理对顶点数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有一个定向图，它的最长有向路的长£D。(b)给出(a)的构造性证明。圈记号（S，T）是D中尾在S内而头在T内的所有弧的集合。（S，T是V的子集）58 定理10.3(Moon,1966)n³3的双向连通竞赛图D中，每个顶点包含在一有向k-圈中，3£k£n。证明：设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£n1，则D包含一有向Hamilton圈。证明：反证，假设D不包含有向Hamilton圈。令C=（v1，v2，……，vq，v1）D中一最长有向圈。易见，C的长q>n/2（习题10.1.7)。令P为D-V(C)中的一条最长有向路，其长为m，其起、终点分别为u和v。显然，n³q+m+1(1)m0使iÎS，i+kÎT（modq）i+jÏSÈT（modq）1£jn(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.6G为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-条弧。58 网络流一个网络（Network）N是由一有向图（称为基础有向图（underlyingdigraph）；二特定的不相交顶点子集X和Y；以及弧集A上定义的非负整数值函数c(×)（称为容量函数）组成的。其中，X的每个顶点称为发点（source）；Y的每个顶点称为收点（sink）；I=V(XÈY)中每个顶点称为中间顶点（intermediatevertex）；每弧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)。称为容量约束（capacityconstraint）。②f+(v)=f-(v)"vÎI。称为守恒条件（conservationcondition）。注f(a)可当作物资沿弧a输送的流量。但不能将流当作水的流动！零流（zeroflow）fÛf(a)=0，"aÎA(D)。设f是网络N上的流，而S是其顶点子集。称f+(S)-f-(S)为流出S的合成流（resultantflowoutofS）f-(S)-f+(S)为流进S的合成流（resultantflowintoS）容易证明（习题），f+(S)-f-(S)=f+(X)-f-(X)=f-(Y)-f+(Y)（记为）=valf称为流f的值。最大流（maximumflow）fÛ不存在流f＇使valf＇>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；58 （不难证明，对求解最大流问题只要考虑这种情形就够了。）可定义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。称capK=为割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)0;f-可增路（f-incrementingpath）PÛP是以发点x为起点，以收点y为终点的f-不饱和路。若N中有一f-可增路P，则，易见，f不是最大流。这时，可沿P输送一附加流而得一新流f′：58 。(11.9)这时，valf′=valf+，并称f′为基于P的修改流（revisedflowbasedonP）。定理11.2N中的流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=capK。从而由推论11.1知，f为最大流。#定理11.3(max-flowmin-cuttheorem,Ford&Fulkerson,1956)在任一网络中，最大流的值=最小割的容量。上定理是图论的一重大结果，其它图论结果，例如，偶图的匹配、Menger定理等，可由它利用适当选取网络来导出。求最大流的算法原理：1°以一已知流f（例如，零流）作为开始。2°系统搜索f-可增路P。若P不存在，停止（f-为最大流）。3°若P存在，求出基于P的修改流f′，令f¬f′，并转到2°。系统搜索f-可增路P标号法（通过标号‘生长’f-不饱和树T）开始，标x以l(x)=¥。（此后，在T的生长过程中，T中每个顶点将标以l(v)=i(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为最大流）。标号程序（labellingmethod，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以58 l(v)=min{l(u),f(a)}。③若y已标号（‘breakthrough’，找到了一条f-可增路），则转到④；否则选一未曾扫描的已标号顶点进行扫描，并回到②。如果已标号顶点都已扫描过，停止（得最大流。且由已标号顶点集S，得最小割（S，`S））。④找一f-可增路P，令f¬，去掉全部标号，并回到①。注上述算法还不是‘好’算法，例如右图中的网络，其最大流的值为2m。但若标号程序以零流开始，且反复地选取xuvy及xvuy为f-可增路，则总共要进行2m+1次标号程序，因此其计算量为输入长（=O(log2m))的指数函数。Edmonds&Karp(1970)证明，若在上述标号程序中采用firstlabelledfirstscan（即广度优先）法则，则，可使该算法成为好算法（复杂性为O(ne2))。习题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*。58 另一方面，设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的伴随有向图（associateddigraph），再用定理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)-路的最大数目58 =破坏G中所有(x,y)-路所需去掉的最少顶点数。证明：将定理11.6用于G的伴随有向图上即得。#推论11.7（Menger定理）设n(G)³k+1，则G为k-连通的ÛG中任二不相同顶点至少被k条内部不相交的路所连接。证明：显然。#习题11.4.1.证明在定理11.6的证明中提到的命题：破坏D’中所有有向(x,y)-路所需去掉的最少弧数=破坏D中所有有向(x,y)-路所需去掉的最少顶点数。11.4.2.从定理11.7导出Konig定理。11.4.3.设S和T是图G中二不相交顶点子集。证明：起点在S、终点在T的顶点不相交的路的最大数目=把S和T分离开来所需去掉的最少顶点数。（即，去掉后没有一个分支同时包含S和T中的顶点）11.4.4.*证明：若G为k（³2）-连通图，则G的任何k个顶点共圈。可行流在网络N的每个发点xi上指定一非负整数s(xi)，称为供给（supply）；在每个收点yj上指定一非负整数(yj)，称为需求（demand）。称N中的流f为可行流（feasibleflow）Ûf+(xi)-f-(xi)£s(xi)"xiÎX；f-(yj)-f+(yj)³(yj)"yjÎY。问题存在可行流的充要条件是什麽？记s(S)=；。定理11.8(Gale,1957)N中存在可行流Ûc(S,`S)³(YÇ`S)-s(XÇ`S)"SÍV。证明：由N作N’如下：①往N里添加二新顶点x及y；②从x到每个xiÎX连以容量为s(xi)的弧；③从每个yjÎY到y连以容量为(yj)的弧；④将x和y分别当作N’的发点和收点。易见，N中有可行流ÛN’有一个流使割(Y,{y})中每一弧都饱和。（习题11.5.1.)但N’中对应流的值=(Y)=cap(Y,{y})。由推论11.1知，它是N’中的最大流，故58 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)+s(XÇ`S)，而(Y)=(YÇ`S)+(YÇS)，得证。#58