圖論及其應(yīng)用19537

《圖論及其應(yīng)用19537》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

圖和子圖圖和簡單圖圖G=(V,E)，其中V={}V---頂點(diǎn)集，---頂點(diǎn)數(shù)E={}E---邊集，---邊數(shù)例。左圖中，V={a,b,......,f},E={p,q,ae,af,......,ce,cf}注意，左圖僅僅是圖G的幾何實(shí)現(xiàn)（代表），它們有無窮多個(gè)。真正的圖G是上面所給出式子，它與頂點(diǎn)的位置、邊的形狀等無關(guān)。不過今后對兩者將經(jīng)常不加以區(qū)別。稱邊ad與頂點(diǎn)a(及d)相關(guān)聯(lián)。也稱頂點(diǎn)b(及f)與邊bf相關(guān)聯(lián)。稱頂點(diǎn)a與e相鄰。稱有公共端點(diǎn)的一些邊彼此相鄰，例如p與af。環(huán)（loop，selfloop）：如邊l。棱（link）：如邊ae。重邊：如邊p及邊q。簡單圖：（simplegraph）無環(huán)，無重邊平凡圖：僅有一個(gè)頂點(diǎn)的圖（可有多條環(huán)）。一條邊的端點(diǎn)：它的兩個(gè)頂點(diǎn)。記號(hào)：。習(xí)題1.1.1若G為簡單圖，則。1.1.2n(34)個(gè)人中，若每4人中一定有一人認(rèn)識(shí)其他3人，則一定有一人認(rèn)識(shí)其他n-1人。同構(gòu)在下圖中，圖G恒等于圖H,記為G=H?VG)=V(H),E(G)=E(H)。圖G同構(gòu)于圖F?V(G)與V(F),E(G)與E(F)之間各存在一一對應(yīng)關(guān)系，且這二對應(yīng)關(guān)系保持關(guān)聯(lián)關(guān)系。記為GF。注往往將同構(gòu)慨念引伸到非標(biāo)號(hào)圖中，以表達(dá)兩個(gè)圖在結(jié)構(gòu)上是否相同。58 注判定兩個(gè)圖是否同構(gòu)是NP-hard問題。完全圖(completegraph)Kn空圖（emptyg.）?E=?。V’(íV)為獨(dú)立集?V’中任二頂點(diǎn)都互不相鄰。二部圖（偶圖，bipartiteg.）G=(X,Y;E)?存在V(G)的一個(gè)2-劃分(X,Y),使X與Y都是獨(dú)立集。完全二部圖Km,n?二部圖G=(X,Y)，其中X和Y之間的每對頂點(diǎn)都相鄰，且|X|=m,|Y|=n。類似地可定義，完全三部圖（例如Km,n,p），完全n-部圖等。例。用標(biāo)號(hào)法判定二部圖。習(xí)題1.2.1G@HTn(G)=n(H),e(G)=e(H)。并證明其逆命題不成立。1..2.2證明下面兩個(gè)圖不同構(gòu)：1.2.3證明下面兩個(gè)圖是同構(gòu)的：1.2.4證明兩個(gè)簡單圖G和H同構(gòu)?存在一一映射f:V(G)?V(H)，使得uv?E(G)當(dāng)且僅當(dāng)f(u)f(v)?E(H)。1.2.5證明：(a).e(Km,n)=mn;(b).對簡單二部圖有e￡n2/4.1.2.6記Tm,n為這樣的一個(gè)完全m-部圖：其頂點(diǎn)數(shù)為n，每個(gè)部分的頂點(diǎn)數(shù)為[n/m]或{n/m}個(gè)。證明：(a).e(Tm,n)=其中k=[n/m].(b)*.對任意的n頂點(diǎn)完全m-部圖G，一定有e(G)￡e(Tm,n)，且僅當(dāng)G@Tm,n時(shí)等式才成立。1.2.7所謂k-方體是這樣的圖：其頂點(diǎn)是由0與1組成的有序k-元組，其二頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們恰有一個(gè)坐標(biāo)不同。證明k-方體有個(gè)頂點(diǎn)，k*2k-1條邊，且是一偶圖。1.2.8簡單圖G的補(bǔ)圖Gc是指和G有相同頂點(diǎn)集V的一個(gè)簡單圖，在Gc中兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們在G不相鄰。(a).畫出Kcn和Kcm,n。58 (b).如果G@Gc則稱簡單圖G為自補(bǔ)的。證明：若G是自補(bǔ)的，則no0,1(mod4)關(guān)聯(lián)矩陣M(G)與鄰接矩陣A(G)M(G)=[mi,j]n*e,A(G)=[ai,j]n*n,其中mi,j=頂點(diǎn)vi與邊ej的關(guān)聯(lián)次數(shù)=0,1,2.ai,j=連接頂點(diǎn)vi與vj的邊數(shù)。例。子圖子圖(subgraph)HíG?V(H)íV(G),E(H)íE(G)。真子圖HìG。母圖（supergraph）。生成子圖（spanningsubg.）?HíG且V(H)=V(G)。生成母圖?；A(chǔ)簡單圖（underlyingsimpleg.）。導(dǎo)出子圖（inducedsubg.）G[V’],(非空V’íV)?以V’為頂點(diǎn)集，以G中兩端都在V’上的邊全體為邊集構(gòu)成的G的子圖。邊導(dǎo)出子圖G[E’]非空E’íE?以E’為邊集，以E’中所有邊的端點(diǎn)為頂點(diǎn)集的的子圖。例。58 以上兩種子圖，其實(shí)，對應(yīng)于取子圖的兩種基本運(yùn)算。下面是取子圖的另兩種基本運(yùn)算：G-V’?去掉V’及與V’相關(guān)聯(lián)的一切邊所得的剩余子圖。?即G[VV’]G-E’?從中去掉E’后所得的生成子圖例。G-{b,d,g},(=G[E{b,d,g}])G-{b,c,d,g},(1G[E{b,c,d,g}])G-{a,e,f,g}.(1G[E{a,e,f,g}])注意G[EE’]與G-E’雖有相同的邊集，但兩者不一定相等：后者一定是生成子圖，而前者則不然。上述四種運(yùn)算是最基本取子圖運(yùn)算，今后老要遇到，一定要認(rèn)真掌握好。關(guān)于子圖的一些定義還有：G+E’?往G上加新邊集E’所得的（G的母）圖。為簡單計(jì)，今后將G±{e}簡計(jì)為G±e；G-{v}簡計(jì)為G-v。設(shè)G1,G2íG，稱G1與G2為不相交的（disjiont）?V(G1)?V(G2)=?(E(G1)?E(G2)=?)邊不相交（edge-distjiont）?E(G1)?E(G2)=?。(但這時(shí)G1與G2仍可能為相交的）。并圖G1èG2,當(dāng)不相交時(shí)可簡記為G1+G2.交圖G1?G2.習(xí)題1.4.1證明：完全圖的每個(gè)導(dǎo)出子圖是完全圖；偶圖的每個(gè)導(dǎo)出子圖是偶圖。1.4.2設(shè)G為一完全圖，10)的2-劃分為(X,Y),則|X|=|Y|。1.5.3在人數(shù)>1的人群中，總有二人在該人群中有相同的朋友數(shù)。58 1.5.4設(shè)V(G)={}，則稱(d(v1),d(v2),......,d(vn))為G的度序列。證明：非負(fù)整數(shù)序列(d1,d2,......,dn)為某一圖的度序列?是偶數(shù)。1.5.5證明：任一無環(huán)圖G都包含一偶生成子圖H，使得dH(v)3dG(v)/2對所有v?V成立。1.5.6*設(shè)平面上有n個(gè)點(diǎn)，其中任二點(diǎn)間的距離31，證明：最多有3n對點(diǎn)的距離=1。路和連通性途徑（walk)例如（u，x）-途徑W=ueyfvgyhwbvgydxdydx(有限非空序列）=uyvywvyxyx(簡寫法---當(dāng)不引起混淆時(shí)）起點(diǎn)（origin）u。終點(diǎn)（terminus）x。內(nèi)部頂點(diǎn)（internalvertex）y,v,w,x。（注意，中間出現(xiàn)的x也叫內(nèi)部頂點(diǎn)。）長?邊數(shù)（重復(fù)計(jì)算）。節(jié)（段，section）。例如W的(y,w)-節(jié)=yvw。W-1（逆途徑）,WW’（兩條途徑W與W’相銜接）。跡(trail)?邊各不相同的途徑。例如，yvwyx。路(path)?頂點(diǎn)各不相同的途徑。（可當(dāng)作一個(gè)圖或子圖)。例如，yvwx。d(u,v)=u與v之間最短路的長。例。（命題）G中存在(u,v)-途徑?G中存在(u,v)-路。G中頂點(diǎn)u與v為連通的(connected)?G中存在(u,v)-路(?G中存在(u,v)-途徑。)V上的連通性是V上的等價(jià)關(guān)系，它將V劃分為（等價(jià)類）：V1,......,Vw使每個(gè)Vi中的任二頂點(diǎn)u及v都連通（即存在(u,v)-路）。稱每個(gè)G[Vi]i=1,2,......w為G的一個(gè)分支（component）;稱w(G）為G的分支數(shù)。G為連通圖?w(G)=1?G中任兩點(diǎn)間都有一條路相連。G為非連通圖?w(G)>1。記號(hào)對任一非空SìV，令=VS,記（稱為邊割）[S,]=G中一端在S中，另一端在中的一切邊的集合。例。（命題）G連通?對任SìV都有[S,]1?例。（命題）簡單圖G中，d3kTG中有長3k的路。習(xí)題1.6.1證明：G中長k為的(vi,vj)-途徑的數(shù)目,就是Ak中的(I,j)元素。1.6.2證明：對簡單圖G有，58 TG連通。對于n>1，試給出的不連通簡單圖。1.6.3簡單圖G中，d>[n/2]-1TG連通。當(dāng)n是偶數(shù)時(shí)，試給出一個(gè)不連通的([n/2]-1)正則簡單圖。1.6.4G不連通TGc連通。1.6.5對任意圖G的任一邊e，有w(G)￡w(G-e)￡w(G)+1。1.6.6G連通，且d(v)=偶數(shù)，"v?VTw(G-v)3d(v)/2,"v?V.1.6.7連通圖中，任二最長路必有公共頂點(diǎn)。1.6.8對任一圖的任三個(gè)頂點(diǎn)u,v,w都有d(u,v)+d(v,w)3d(u,w)。1.6.9任一簡單圖非完全圖中，一定有三個(gè)頂點(diǎn)u,v,w，使得uv,vw?E而uw?E。圈閉途徑（closedwalk)?起點(diǎn)=終點(diǎn)且長>0的途徑。閉跡(closedtrail)?邊各不相同的閉途徑。圈（cycle）?頂點(diǎn)各不相同的閉跡。（可當(dāng)作一圖或子圖。）例。閉途徑：uyvyu;uywxywvu；uyuyu。閉跡：uyxwyvu。圈：yfvgy;uywvu。k-圈（k-cycle）?長為k的圈。例。1-圈（即一條環(huán)），2-圈(由重邊組成），3-圈（又稱三角形）。奇圈(oddcycle)。偶圈(evencycle)。定理1.2G為二部圖?G不含奇圈。證明：T：設(shè)G的2-劃分為（X,Y），由G的定義，G的任一圈中，X和Y的頂點(diǎn)一定交錯(cuò)出現(xiàn)，從而其長必為偶數(shù)。ü：不妨設(shè)G為連通的。任取一頂點(diǎn)u,令X={x?V|d(u,x)=偶數(shù)},Y={y?V|d(u,y)=奇數(shù)}。由于，易見，(X,Y)為V的2-劃分，只要再證X和Y都是G的獨(dú)立集（即X（或Y）中任二頂點(diǎn)v，w都不相鄰）即可：令P與Q分別為最短(u,v)-路與最短(u,w)-路。設(shè)u’為P與Q的最后一個(gè)公共頂點(diǎn)；而P’與Q’分別為P的(u’,v)-節(jié)與Q的(u’,w)-節(jié)。則P’與Q’只有一公共頂點(diǎn)。又，由于P與Q的(u,u’)-節(jié)的長相等，P’與Q’的長有相同的奇偶性，因此v與w不能相鄰，不然，頁碼:6v(P’)-1Q’wv將是一奇圈，矛盾。#例。（命題）圖G中d32TG中含圈。例。（命題）簡單圖G，d32TG含長e3d+1的圈。58 例。（命題）任一圖中(a).e3nT含圈。(b)*.e3n+4T含二條邊不重的圈。習(xí)題1.7.1若邊e在G的一閉跡中，則e在G的一圈中。1.7.2證明：(a).e3nTG含圈。(b)*.e3n+4TG含兩個(gè)邊不重的圈。最短路問題賦權(quán)圖（weightedg.)(權(quán)o1之推廣)權(quán)(weight)w(e)30.w(H)=,HíG.路P的長=w(P)頂點(diǎn)u與v距離d(u,v)=最短(u,v)-路的長。問題求最短(u0,v0)-路。轉(zhuǎn)求最短(u0,v)-路,"v?V{u0}.簡化只考慮簡單圖，且w(e)>0"e?E.（w(uv)=0時(shí)，可合并u與v為一頂點(diǎn)）。原理逐步求出頂點(diǎn)序列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)?v1u0}者.得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進(jìn)行下一步時(shí)，只要更新l(v)即可：l(v)?min{l(v),l(uk)+w(ukv)}"v?Dijkstra算法(1).作為開始：l(u0)?0;l(v)?￥"v1u0;S0?{u0};k?0.(2).（這時(shí)已有Sk={u0,u1,.............,uk}）58 l(v)?min{l(v),l(uk)+w(ukv)}"v?再計(jì)算min{l(v)}，設(shè)其最小值點(diǎn)為uk+1，令Sk+1=Skè{uk+1}。(3).若k=n-1,仃止；不然，令k?k+1,并回到(2)。計(jì)算復(fù)雜性加法：n(n-1)/2比較：n(n-1)/2′2v?：(n-1)2+)________________________________________________共O(n2)凡是復(fù)雜性為p(n,e)的算法(p(.,.)為一多項(xiàng)式)稱為“好算法”(“goodalgorithm”------J.Edmonds)。這是相對于指數(shù)型算法而言的：在10-6秒/步運(yùn)算速度下：復(fù)雜性n=1020304050n3.001sec.008sec.027sec.064sec.125secn5.1sec3.2sec24.3sec1.7min5.2min2n.001sec1.0sec17.9min12.7days35.7years由上表可見，兩種算法有天壤之別。注1.若只關(guān)心求d(u0,v0)則算法進(jìn)行到v0?Sk時(shí)停止。2.計(jì)算過程中，所得子圖是一棵樹。每步都是往其上增加一條邊及一個(gè)頂點(diǎn)，因此該過程稱為treegrowingprocedure。3.若要計(jì)錄u0到每個(gè)頂點(diǎn)u的最短路，只要記錄下該路中u的前一個(gè)頂點(diǎn)即可。習(xí)題1.8.1描述一個(gè)算法以確定(a).一圖的各個(gè)分支；(b).一圖的圍長（即最短圈的長）。并說明你的算法好到什么程度。樹樹無圈圖（acyclicg.；林forest）。樹（tree）?連通無圈圖。葉(leave)?樹中度為1的頂點(diǎn)。定理2.1樹中任二頂點(diǎn)間有唯一的路相連。證明：反證，假設(shè)存在樹G，其中有二頂點(diǎn)u與v，其間有二不同(u,v)-路P1和P2相連。因P11P2，一定存在P1的一條邊e=xy，它不是P2的邊。顯然，圖P1èP2-e是連通的，從而其中包含一條(x,y)-路P。于是P+e是G中的一圈，這與G為無圈圖相矛盾。#58 注意(1).當(dāng)G無環(huán)時(shí)，易見，G是樹?G中任二頂點(diǎn)間有唯一的路相連。(2).以下結(jié)論不一定成立：$閉途徑T$圈。定理2.2G是樹Te=n-1。證明：對n進(jìn)行歸納。當(dāng)n=1時(shí)，G=K1，成立。假設(shè)定理對小于n個(gè)頂點(diǎn)的樹成立，而G為n個(gè)頂點(diǎn)的樹。任取G的一邊uv。它是G中的一條路，由定理2.1知，G-uv不連通，且它恰有二分支（習(xí)題1.6.5），設(shè)為G1與G2。它們都是連通無圈圖，因此是樹。又，它們的頂點(diǎn)數(shù)都小于n。由歸納假設(shè)知e(GI)=n(GI)-1I=1,2.故，e(G)=e(G1)+e(G2)+1=n(G1)+n(G2)-1=n(G)-1。#推論2.2每棵非平凡樹至少有兩個(gè)度為1的頂點(diǎn)。證明：由于G為非平凡連通圖，d(v)31,"v?V。再由定理1.1及2.2知，，由此知推論成立。例。（命題）恰只包含二度為一頂點(diǎn)的樹是路。習(xí)題2.1.1證明：非平凡樹中，任一最長路的起點(diǎn)和終點(diǎn)均是度為1的頂點(diǎn)。再由此去證明推論2.2。2.1.2當(dāng)e=n-1時(shí)，證明以下三結(jié)論是等價(jià)的：(a)G是連通圖；(b)G是無圈圖；(c)G是樹。2.1.3一樹中若D3k，則其中至少有k個(gè)度為1的頂點(diǎn)。2.1.4G為林?e=n-w。2.1.5若林G恰有2k個(gè)奇點(diǎn)，則G中存在k條邊不重的路P1,P2,..,Pk,使得E(G)=E(P1)èE(P2)è...èE(Pk)。2.1.6正整數(shù)序列(d1,d2,...,dn)是一棵樹的度序列，當(dāng)且僅當(dāng)。2.1.7飽和烴分子形如CmHn,其中碳原子的價(jià)鍵為4，氫原子的價(jià)鍵為1，且任何價(jià)鍵序列都不構(gòu)成圈。證明：對每個(gè)m，僅當(dāng)n=2m+2時(shí)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為樹。證明：注意到以下事實(shí)即可，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.2GTe3n-1。定理2.4.5設(shè)T為G的一生成樹，e為G中不屬于T的邊，則T+e含唯一的圈。證明：由于T無圈，T+e中的每個(gè)圈都包含e。又，C為T+e的一圈?C-e為T中連接e的兩個(gè)端點(diǎn)的路。但，由定理2.1知，T中恰只有一條這樣的路，因此T+e中包含唯一的圈。小結(jié)G為樹?G中任二頂點(diǎn)間有唯一的路相連，且無環(huán)?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}都是邊割，其中后兩個(gè)為鍵。而E’={zu,zv,zy,uv}不是G的邊割，當(dāng)然更不是G的鍵，雖然G-E’變成不連通。易見，當(dāng)G連通且S1?時(shí)，邊子集B為G的鍵?B是使G不連通的E的極小子集。?w(G-B)=2，且中每邊的兩端點(diǎn)分別在二分支中。58 邊割B=[S,]為鍵?G[S],G[]都連通。（習(xí)題）設(shè)H為G的子圖，稱子圖G-E(H)為G中H的補(bǔ)圖，記為：`H(G)。特別地，當(dāng)T為G的生成樹時(shí)，稱`T為G的余樹。定理2.6設(shè)T為連通圖G的一個(gè)生成樹，e為T的一條邊，則(1).余樹`T不包含G的鍵；(2).`T+e中唯一包含的G的一個(gè)鍵。證明：(1).因G-E(`T)=T連通，則不包含G的邊割，從而也不包含G的鍵。(2).注意到e為的T割邊，令S與`S分別為T-e的二分支的頂點(diǎn)集?？紤]B=[S,`S]G由于G[S](包含T-e的一個(gè)分支T[S])與G[`S](包含T-e的一個(gè)分支T[`S])都連通，B必是G鍵，包含于``T+e中。來證B為包含在`T+e中的唯一鍵,只要再證對包含在`T+e中的G的任一鍵B’，一定有B=B’即可：假設(shè)不然，由于鍵的極小性，B’不會(huì)包含B，從而一定存在B的一邊b?B’。于是G-B’êT-e+b(注意到B’í`T+eTG-B’êT-e)但T-e+b也是G的一生成樹（因其邊數(shù)=n-1，且連通），從而G-B’連通，這與B’為G的鍵相矛盾。#附錄設(shè)G連通，T為其任一生成樹。對每一e?`T，T+e中有唯一圈C，因而可得C1,C2,......,Ce-n+1共e-n+1個(gè)不同的圈，每個(gè)稱為G的一個(gè)基本圈。同樣，對每一e?T，`T+e中有唯一的鍵因而可得B1,B2,......,Bn-1共n-1個(gè)不同的鍵，每個(gè)稱為的一個(gè)基本割集。設(shè)S1,S2為二集合，記其對稱差(即（S1èS2）-（S1?S2）)為S1?S2稱為它們的環(huán)和(ringsum)。性質(zhì)1)圖G的每一邊割是G的一些割集的邊不重并。2)設(shè)B1,B2為圖的任二邊割，則B1?B2也是G的邊割。（對任二非空V1,V2ìV，有[V1,V1]?[V,V]=[V2,V2],其中V3=(V1?V2)è(`V1?`V2)）。3)設(shè)邊子集E’與E”分別為G中一些圈的邊不重并，則E’?E”亦然。4)G的每個(gè)圈可唯一地表為G的一些基本圈的環(huán)和。5)G的每個(gè)邊割可唯一地表為G的一些基本割集的環(huán)和。6)邊子集E’為G中一些邊不重圈的并集?邊子集E’與G中每個(gè)邊割有偶數(shù)條公共邊。1)邊子集B為G的一個(gè)邊割?邊子集B與G的每個(gè)圈有偶數(shù)條公共邊。7)G為一些圈的邊不重并?d(v)=偶數(shù)"v?V習(xí)題2.2.1設(shè)G連通且e?E，證明：(a)e在G的每棵生成樹中當(dāng)且僅當(dāng)e是G的邊割。(b)e不在G的任一生成樹中當(dāng)且僅當(dāng)e是G的環(huán)。58 2.2.2無環(huán)圖G恰只有一棵生成樹T，則G=T。2.2.3設(shè)F是G的極大（maximal）林，證明：(a)對G的每個(gè)分支H，F(xiàn)?H是H的生成樹；(b)e(F)=n(G)-w(G)。2.2.4證明：任一圖G至少包含e-n+w個(gè)不同的圈。2.2.5(a)若G的每個(gè)頂點(diǎn)均為偶點(diǎn)（即，度為偶數(shù)的頂點(diǎn)），則G沒有割邊；(b)若G是k-正則偶圖且k32，則沒有割邊。2.2.6當(dāng)G連通且S1?時(shí)，邊割B=[S,]為鍵?G[S],G[]都連通。2.2.7圖G的每一邊割是G的一些鍵（即，割集）的邊不重并。2.2.8在圖G中，設(shè)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棵邊不重的生成樹，則對于頂點(diǎn)集每一劃分(V1,V2,...,Vn)，端點(diǎn)在這個(gè)劃分的不同部分的邊的數(shù)目至少為k(n-1)。割點(diǎn)稱頂點(diǎn)v為G的割點(diǎn)(cutvertex)?E可劃分為二非空子集E1及E2，使G[E1]與G[E2]只有一公共頂點(diǎn)v。顯然，當(dāng)G無環(huán)時(shí)，v為割點(diǎn)?w(G-v)>w(G)。?存在二頂點(diǎn)x及y，使G中任一(x,y)-路一定包含v。例。（邊割）為G的鍵?v不是的G的割點(diǎn)。定理2.7在樹G中v為割點(diǎn)?d(v)>1。證明：(i)若d(v)=0，則G@K1，v不是割點(diǎn)。(ii)若d(v)=1，則G-v仍然是樹。因此w(G-v)=1=w(G)，從而v不是割點(diǎn)。(iii)若d(v)>1，則G中存在與v相鄰接的二不同頂點(diǎn)u,w。由定理2.1知，uvw是G中的唯一(u,w)-路，因此G-v中不含(u,w)-路，（即G-v中u,w不連通）w(G-v)>1，即v為G的割點(diǎn)。#推論2.7非平凡、無環(huán)、連通圖中，至少有二頂點(diǎn)不是割點(diǎn)。證明：令T為G的一生成樹，由推論2.2及定理2.7知，T中至少存在二頂點(diǎn)u與v不是T的割點(diǎn)，則它們也不是G的割點(diǎn)：這是因?yàn)閷τ趗(及v)有1=w(T-u)3w(G-u)31，∴w(G-u)=1=w(G)。#習(xí)題58 2.3.1設(shè)G為n33的連通圖，證明：(a)若G有割邊，則G有頂點(diǎn)v使w(G-v)>w(G)；（即，割邊必有一端點(diǎn)為割點(diǎn)）(b)(a)的逆命題不成立。2.3.2證明：恰有二頂點(diǎn)為非割點(diǎn)的簡單連通圖必是一條路。2.3.3在簡單連通圖G中證明：v為G的割點(diǎn)?G的任一生成樹不以v為葉。生成樹的計(jì)數(shù)及Caley公式本節(jié)只討論無環(huán)連通圖。將圖G的關(guān)聯(lián)An′e矩陣中每列的兩個(gè)1元素之一改為-1，得一新矩陣，記為Aa（它是G的一個(gè)定向圖的關(guān)聯(lián)矩陣）。例如：記A為從Aa中刪去某一行所得的(n-1)′e矩陣。引理1設(shè)A1為A的任一(n-1)階子方陣，則det(A1)=±1?A1的列對應(yīng)于G的一生成樹。證明：令劃去的行對應(yīng)于頂點(diǎn)u，記H為以全體與A1的列相對應(yīng)的邊構(gòu)成的生成子圖。由于e(H)=n-1,因此有H連通?H為G的生成樹。（1）當(dāng)H不是G的生成樹時(shí)，由上述知，H不連通。令S為H中不含u的一個(gè)分支的頂點(diǎn)集。易見，A1中對應(yīng)于S的全體行向量之和為一零向量。因此，det(A1)=0。（2）當(dāng)H是G的生成樹時(shí)，重排A1的行、列如下：取H的一個(gè)度為1的頂點(diǎn)u1，并使u11u。記u1在H中的關(guān)聯(lián)邊為e1;再取H-u1中的一個(gè)度為1的頂點(diǎn)u2，并使u21u,記u2在H-u1中的關(guān)聯(lián)邊為e2;......。按u1,u2,...及e1,e2,,,,,,,的順序重排A1的行、列，得矩陣A1’。易見，A’1為下三角型。且主對角線元素全為±1,因此|detA1|=|detA1’|=1。#Binet-Cauchy定理設(shè)矩陣P=[pij]m′n，Q=[qij]n′m，且m￡n則引理2連通圖的生成樹數(shù)目=det（AAT）。證明：由Binet-Cauchy定理知，det(AAT)=∑(detA1)2(對A的所有v-1階子方陣A1求和）但由引理1知|detA1|=得證。#無環(huán)圖G的度矩陣K=[kij]n′n，其中58 例如對本節(jié)開頭的例子有定理連通圖G的生成樹數(shù)目=K的任一元素的代數(shù)余子式證明：容易驗(yàn)證，K=AaAaT。又，K的任一行（列）的元素的代數(shù)和=0，因此K的所有代數(shù)余子式都相等。再，設(shè)Ak為從Aa中去掉第k行所得的(n-1)′e矩陣，易見，AkATk=從K中去掉第k行第k列后所得的子方陣故由引理2知本定理成立。#例。前例的圖的生成樹數(shù)目=K的(2,3)-元素的代數(shù)余子式==8。定理（Cayley）　Kn中共有　nn-2個(gè)不同的生成樹。證明：用上述定理可直接證出（習(xí)題）。　　　　#習(xí)題2.4.1求Ｋ３，３的生成樹數(shù)目。2.4.2若ｅ是Ｋｎ的一條邊，　則　Ｋｎ－ｅ的生成樹數(shù)目為　(n-2)nn-3。連線問題問題設(shè)城市vi與vj間建立直接通信線路的費(fèi)用為cij（30）。建設(shè)連接{}的通訊網(wǎng)使造價(jià)最省?在賦權(quán)圖G中求一最小權(quán)連通生成子圖；?在賦權(quán)圖G中求一最小權(quán)生成樹（最優(yōu)樹）。下面的Kruskal算法是在非賦權(quán)圖中求生成樹的“極大無圈子圖”算法的改進(jìn)，它是一種貪心算法（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)不能再進(jìn)行下去時(shí)，停止。否則，回到?(2)。定理2.10Kruskal算法求出的生成樹=G[{e1,e2,...,en-1}]是最優(yōu)樹。證明：反證，假設(shè)T*不是G的最優(yōu)樹。取G的一最優(yōu)樹T。令ek為{e1,e2,...,en-1}中（58 按順序）第一個(gè)不屬于T的邊，且令T為最優(yōu)樹中使k為最大者。則T+ek中唯一的圈C包含ek，且C中必含一條邊e’k?T*(不然，CíT*，矛盾。）但T’=T+ek-e’k也是G的生成樹。（因e’k不是T+ek的割邊（定理2。3），從而T’連通，且其邊數(shù)=n-1。）又，由于T的子圖G[{e1,e2,...,ek-1}è{e’k}]也不含圈，由法算法知w(ek)￡w(e’k)∴w(T’)￡w(T)，即T’也是G的最優(yōu)樹，且{e1,e2,...,en-1}中第一個(gè)不屬于T’的邊的下標(biāo)>k。這與k的取法相矛盾。#實(shí)現(xiàn)先按權(quán)的不減順序?qū)⑦吋嘏懦蒩1,a2,...,ae。關(guān)于算法中無圈性的判定，我們有一簡單的辦法：當(dāng)S={e1,e2,...,ei}已取定時(shí)，對候選邊ajG[Sè{aj}]無圈?aj的兩端點(diǎn)在林G[S]（此處當(dāng)作生成子圖）的不同分支中。從而我們有求最優(yōu)樹的標(biāo)記法：開始：取a1為候選邊；并將vk標(biāo)以k，k=1,2,...,n。若S={e1,e2,...,ei}已取定，當(dāng)候選邊aj的兩端點(diǎn)有相同標(biāo)號(hào)時(shí)，改取aj+1為候選邊（丟掉aj永不再考慮）；否則選定ei+1=aj，并將G[S]中aj兩端點(diǎn)所在的二分支的頂點(diǎn)重新標(biāo)號(hào)，標(biāo)以兩者中的最小者。算法復(fù)雜性邊排序O(e×log2e)比較邊兩端的標(biāo)號(hào)e重新標(biāo)號(hào)O((n-1)n)故為好算法（￡O(n3)）。附錄（A）Prim’salgorithm（也是一種貪心算法）T??,V’?{u}forallv?`V’doL(v)?w(uv)//initializingL(.);`V’=VV’while`V’1Vdobeginfindvertexws.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)。當(dāng)G為簡單圖時(shí)，k￠=n-1?G@Kn。稱圖G為k-邊連通的（k-edgeconnected）?k￠(G)3k?至少去掉k條邊才能使G變成不連通或平凡圖。例如，所有非平凡連通圖都是1-邊連通的。稱頂點(diǎn)子集V’為G的頂點(diǎn)割(vertexcut)?G-V’不連通。稱頂點(diǎn)子集V’為G的k-(頂)點(diǎn)割(vertexcut)?V’為G的頂點(diǎn)割，且|V’|=k。顯然，當(dāng)G為無環(huán)連通圖時(shí)，v為G的1-點(diǎn)割?v為G的割點(diǎn)。完全圖無點(diǎn)割。G的連通度(connectivity)（=使G變成不連通或平凡圖所需去掉的最少的頂點(diǎn)數(shù)。）例。當(dāng)n33時(shí)，k=1?G連通且有1-點(diǎn)割。k(Kn)=n-1。k(G)=n-1?G的基礎(chǔ)簡單圖為完全圖。稱圖G為k-連通的（k-connected）?k(G)3k?至少去掉k個(gè)頂點(diǎn)才能使G變成不連通或平凡圖。例如，所有非平凡連通圖都是1-連通的。定理3.1k￡k￠￡d。58 證明：先證k￠￡d：當(dāng)G為平凡圖時(shí)，k￠=0￡d，結(jié)論成立；當(dāng)G為非平凡圖時(shí)，選取v使d(v)=d,則E’=是G的一個(gè)邊割，因此k￠￡|E￠|￡d結(jié)論成立。再來證k￡k￠：不妨設(shè)G為簡單、連通、非完全圖，于是k￠￡n-2。任取一k￠-邊割B，及B中任一邊e=xy。今，在B-e的每邊上各取一個(gè)端點(diǎn)使之不等于x及y。令這些端點(diǎn)的集合為S。易見，|S|￡k￠-1。記H=G-S。(i)若H不連通，則S為G的點(diǎn)割，從而k￡|S|￡k￠-1。(ii)若H連通，則e=xy為H的割邊。但，n(H)=n(G)-|S|3n-(k￠-1)33，因此，x與y必有一個(gè)為H的割點(diǎn)，設(shè)為x。于是Sè{x}為G的點(diǎn)割，故k￡|S|+1￡k￠。#習(xí)題3.1.1(a)證明：若G是k-邊連通的，且k>0，又E’為G的任k條邊的集合，則w（G-E’)￡2。(b)對k>0，找出一個(gè)k-連通圖G以及G的k個(gè)頂點(diǎn)的集合S，使w(G-S)>2。3.1.2證明：若G是k-邊連通的，則e3kn/2。3.1.3(a)證明：若G是簡單圖且d3n-2，則k=d。(b)找出一個(gè)簡單圖G，使得d=n-3且k1,NP-hardprob.當(dāng)每邊權(quán)o1且G為任意圖時(shí)，問題變成求邊數(shù)最少的k-連通生成子圖。(仍然是NP-hardprob.)當(dāng)G@Kn且每邊權(quán)為1時(shí)，Harary(1962)作出邊數(shù)最少的G的k-連通（k-邊連通）生成子圖Hk,n（邊數(shù)={kn/2})（∴有好算法。）Hamilton圈與Euler環(huán)游Euler環(huán)游環(huán)游（tour）?通過圖中每邊至少一次的閉途徑。Euler環(huán)游?通過圖中每邊恰一次的閉途徑。Euler跡?通過圖中每邊的跡。?通過圖中每邊恰一次的途徑。（可“一筆畫成”。）Euler圖?包含Euler環(huán)游的圖?包含Euler閉跡的圖。?本身為閉跡的圖。定理4.1設(shè)G為非空連通圖，則G為Euler圖?G中無度為奇數(shù)的頂點(diǎn)。證明：T：令C=u0e1u1e2u2...eeue(ue=u0)為G的一Euler環(huán)游，起點(diǎn)為u0。則對任一頂點(diǎn)v1u0，當(dāng)v每次作為內(nèi)部頂點(diǎn)出現(xiàn)于C時(shí)，C上有二邊與v相關(guān)聯(lián)。由于C上包含了G的所有邊且不重復(fù)，因此d(v)=偶數(shù)。類似地，d(u0)=偶數(shù)。ü：反證，假設(shè)存在非空連通圖，它的每個(gè)頂點(diǎn)的度都是偶數(shù)，但卻不是Euler圖。在這種圖中選取G使其邊數(shù)最少。由于d(G)32，G包含圈。令C為G中的最長閉跡。由假設(shè)，C不會(huì)是Euler環(huán)游。因此G-E(C)中一定有一分支G’使e(G’)>0。由于C本身為Euler圖，（由定理的必要條件知）C中每個(gè)頂點(diǎn)的度都是偶數(shù)，因此G’中無度為奇數(shù)的頂點(diǎn)。但e(G’)0個(gè)奇點(diǎn)，則G中存在k條邊不重的跡Q1,Q2,...,Qk使得E(G)=E(Q1)èE(Q2)è...èE(Qk)。4.1.5設(shè)G為非平凡Euler圖，且v?V。證明：G中任一條以v為起點(diǎn)的跡都能延伸成一Euler環(huán)游當(dāng)且僅當(dāng)G-v為林。（O.Ore）中國郵遞員問題問題在一賦權(quán)圖G中，求一最小權(quán)環(huán)游（即最優(yōu)環(huán)游）。當(dāng)G為Euler圖時(shí)，其任一Euler環(huán)游都是最優(yōu)環(huán)游，此時(shí)有求最優(yōu)環(huán)游的好算法，如Fleury算法（“過河拆橋，盡量不走獨(dú)木橋“）1.任取一頂點(diǎn)v0，令w0=v0。2.若跡Wi=v0e1v1...eivi已取定，選ei+1?E{e1,...,ei}使(i)ei+1與vi相關(guān)聯(lián)；(ii)除非無奈，選ei+1使它不是Gi=G-{e1,...,ei}的割邊。3.若2.不能再進(jìn)行下去，停止。定理4.7若G為Euler圖，則由Fleury算法求得的G中的跡，是G的一Euler環(huán)游。證明：令Wn=v0e1v1...envnFleury算法求得的G中的跡，顯然dGn(vn)=0,vn=v0。58 假設(shè)Wn不是Euler環(huán)游，令S={v|dGn(v)>0}，`S=VS。易見，S1?；vn?`S。令vm為Wn在S中的最后一個(gè)頂點(diǎn)，則，顯然，。又，=偶數(shù)，"v?V。因此Gn中無割邊，特別地，Gn中與相關(guān)聯(lián)的任一邊e是Gn中的非割邊，因而也是中的非割邊。但1e(∵?Gn)，于是在中，割邊與非割邊e都和相關(guān)聯(lián)，而跡Wn卻取的是割邊，這與算法之2.(ii)相矛盾。#定理之另證：其實(shí)只要再證以下斷言即可：斷言在算法進(jìn)行過程中，每個(gè)Gi都是G的生成子圖，其中只有一個(gè)分支是非空的（即其余分支每個(gè)都是孤立頂點(diǎn)），且vi與v0同在該非空分支中。證明：對i進(jìn)行歸納。當(dāng)i=1時(shí)，G1=G-e1，由于G中無割邊，G1連通，從而結(jié)論成立。假設(shè)當(dāng)i≤n-1時(shí)都成立，來證當(dāng)i=n（＜ε）時(shí)也成立：由歸納假設(shè)，Gn-1=G-{e1,......,en-1}中，vn-1和v0在其唯一的非空分支中。于是，算法2.(i)所選vn-1的關(guān)聯(lián)邊en必在該分支中。當(dāng)en不是Gn-1的割邊時(shí)，（對Gn）結(jié)論成立。當(dāng)en是Gn-1的割邊時(shí)，由算法知，Gn-1中與vn-1相關(guān)聯(lián)的邊必都是Gn-1的割邊。由習(xí)題（見下）知，與vn-1相關(guān)聯(lián)的邊中至多有一條割邊，從而Gn-1中與vn-1相關(guān)聯(lián)的邊恰只有en這條邊。因此，Gn中原Gn-1的非空分支變成一個(gè)孤立頂點(diǎn)vn-1及一個(gè)含vn與v0的非空分支。結(jié)論仍成立。#習(xí)題若連通圖G中只有二奇點(diǎn)，則與任一奇點(diǎn)相關(guān)聯(lián)的邊中至多有一條是G的割邊。中國郵遞員問題?在一賦權(quán)圖G中，求一最小權(quán)環(huán)游（即最優(yōu)環(huán)游）?(i)找賦權(quán)連通圖G的一個(gè)Euler母圖G*，它是由重復(fù)（duplicated）G的一些邊而得，且使w(E(G*)E(G))=min；(ii)在G*中找出其Euler環(huán)游。[附錄（關(guān)梅谷，1960）(書：“SelectedTopicsinGraphTheorey2”,p.35)連通圖G（每邊權(quán)o1）中的“郵路”（最優(yōu)環(huán)游）為C?在C中G的每邊至多出現(xiàn)兩次，且G的任一閉跡中至多有半數(shù)的邊重復(fù)出現(xiàn)于C。]當(dāng)賦權(quán)圖G中恰只有二度為奇數(shù)頂點(diǎn)u,v時(shí),G*可由G加上(重復(fù))G中的最短(u,v)-路P而得。證明：易見，G1*=G*[E*E]中只有u，v為奇點(diǎn)，它們一定在G*的同一分支中。令P*為其中的（u，v）-路，則有w(E*E)3w(P*)3w(P)。但G+P也是G的一Euler母圖，故G*=G+P。#當(dāng)G中有34個(gè)奇點(diǎn)時(shí)，已由J.EdmondsandE.L.Johnson解決（1972）。Hamilton圈Hamilton路?生成路（spanningpath）Hamilton圈?生成圈Hamilton圖?包含Hamilton圈的圖定理4.2G為Hamilton圖Tw(G-S)￡|S|"SìV58 證明：令C為G的一個(gè)Hamilton圈,則對任一SìV必有w(C-S)￡|S|，但w(G-S)￡w(C-S)。#注意，定理4.2之逆不成立。例如，Pertersen圖滿足定理?xiàng)l件，但它是非Hamilton圖。約定本節(jié)只討論簡單圖。定理4.3（Dirac，1952）n33的簡單圖G中，若d3n/2，則G為Hamilton圖。證明：反證，設(shè)G為n33滿足d3n/2的極大非Hamilton簡單圖。（即任取一反例，在保持其為非Hamilton、簡單圖的前提下，盡量加邊，直到不能再加為止。取之為G。）因n33，G不能是完全圖。任取G中二不相鄰接頂點(diǎn)u及v，則G+uv為Hamilton圖，且其中的每個(gè)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.n35個(gè)人圍桌而坐，總有一新就座法，使每人的鄰座都不相同。4.3.8.對下列問題給出一好算法：(a)構(gòu)造一個(gè)圖的閉包。(b)若某圖的閉包為完全圖，求該圖的Hamilton圈。4.3.9.對任正整數(shù)n，完全3-部Kn,2n,3n為Hamilton圖；而完全3-部Kn,2n,3n+1為非Hamilton圖旅行售貨員問題(travellingsalesmanprob.)問題在賦權(quán)完全圖中找最小權(quán)Hamilton圈（最優(yōu)圈）。（NP-hardprob。）（問題任給一圖G，G是否為Hamilton圖？（NP-completeprob。））代替辦法找一reasonablygoodsolution。例如，先找一Hamilton圈C=v1v2...vnv1，再加以改進(jìn)：對任i與j,1|M|，H中一定有一分支是一條路P，且其起點(diǎn)與終點(diǎn)都是M*飽和的。從而P是G中的M-可擴(kuò)路，矛盾。#習(xí)題5.1.1(a)證明：每個(gè)k-方體都有完美匹配(k33)。(b)求K2n與Kn,n中不同的完美匹配的個(gè)數(shù)。5.1.2證明：一樹中最多只有一個(gè)完美匹配。5.1.3對每個(gè)k>1，找出一個(gè)無完美匹配的k-正則簡單圖的例子。5.1.4兩人在圖G上做游戲，交替地選取不同的頂點(diǎn)v0,v1,v2,.........，使對每個(gè)i>0，都有vi與vi-1相鄰。最后一個(gè)頂點(diǎn)的選擇者勝。證明：第一個(gè)選點(diǎn)人有一得勝策略當(dāng)且僅當(dāng)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是偶數(shù)，且d31+n/2，則G有3-因子。5.1.6*證明：K2n+1可表為n個(gè)連通的2-因子的并。5.1.7證明：任連通偶圖G=（X,Y,E）的2-劃分（X，Y）是唯一的。58 偶圖的匹配和覆蓋鄰集（neighbourset）N(S)（SíV）：G中所有與S中頂點(diǎn)相鄰接的頂點(diǎn)集合。定理5.2（Hall’stheorem,1935)在偶圖G=(X,Y,E)中G包含使X中每個(gè)頂點(diǎn)都飽和的匹配?|N（S）|3|S|"SíX（*）證明：T：顯然。ü：反證，假設(shè)存在偶圖G，它滿足條件（*）但不包含使X中每個(gè)頂點(diǎn)都飽和的匹配。令M*為G的最大匹配，u為X中M*不飽和的頂點(diǎn)。記Z={v?$M*-交錯(cuò)（u，v）-路}由于M*為最大匹配，由定理5.1，u為Z中唯一M*-不飽和頂點(diǎn)。令S=Z?X，T=Z?Y。顯然，SU與T的頂點(diǎn)在M*下相匹配（注意到：任一M*-邊若有一端點(diǎn)在Z中，則其另一端一定也在Z中）。因此，?T?=?S?-1；N(S)êT。但N(S)íT，故N(S)=T，從而?N(S)?=?T?=?S?-10)，則G有完美匹配。證明：設(shè)G的2-劃分為(X,Y)，則k?X?=?E?=k?Y?，?X?=?Y?。又，對任SíX，令E1和E2分別為與S和N(S)相關(guān)聯(lián)的邊集。易見，E1íE2?！鄈|S|=|E1|￡|E2|=k|N(S)|∴|S|￡|N(S)|"SíX。故G中有使X中每個(gè)頂點(diǎn)都飽和的匹配M，它也是完美匹配。#稱K（íV）為G的一個(gè)覆蓋（covering）?G中每邊至少有一端在K中。最小覆蓋（minimumcovering）。對G中任一覆蓋K及任一匹配M，顯然，恒有?M?￡?K?。特別地，有?M*?￡??。引理5.3設(shè)M與K分別為G中的匹配與覆蓋，如果?M?=?K?則M為最大匹配，K為最小覆蓋。（證明：略）定理5.3(Konig’stheorem,1931)設(shè)M*，分別為偶圖G的最大匹配和最小覆蓋，則?M*?=??。證明：設(shè)G的2-劃分為（X，Y）。記U={u?X?u為M*-不飽和的}Z={v?V?$M*-交錯(cuò)（u，v）-路}S=Z?X，T=Z?Y。與定理5.2之證明類似，我們有：T中每頂點(diǎn)都是M*-飽和的；T與SU中頂點(diǎn)在M*下相匹配；N(S)=T。記58 =(XS)èT。易見，G中每邊至少有一端在中，即為G的覆蓋（不然，與N(S)=T相矛盾）。又，顯然，?M*?=??。再由引理5.3知為最小覆蓋。#習(xí)題5.2.1證明：一個(gè)5′5方格棋盤去掉其對角上的兩個(gè)1′1方格之后，不可能用1′2長方格恰好添滿。5.2.2(a)證明：偶圖G有完美匹配當(dāng)且僅當(dāng)對所有SíV都有?N(S)?3?S?。(b)舉例說明：去掉偶圖這個(gè)條件之后，上述不成立。5.2.3對于k>0，證明：(a)每個(gè)k-正則偶圖都是1-可因子分解的；(b)*每個(gè)2k-正則圖都是2-可因子分解的。5.2.4設(shè)A1，A2，……，An是某集S的子集。族（A1，A2，……，An）的一個(gè)相異代表系是指S的一個(gè)子集{a1，a2，……，an}使ai?Ai（1￡i￡n），且ai1aj（當(dāng)i1j）。證明：（A1，A2，……，An）有一個(gè)相異代表系當(dāng)且僅當(dāng)??3?J?"Jí{1,2,...,n}。5.2.5矩陣的一行或一列統(tǒng)稱一條線。證明：一（0,1)-矩陣中，含所有1元素的線的最小條數(shù)=兩兩都不在相同線上的1元素的最大個(gè)數(shù)。5.2.6(a)證明：Hall定理的一個(gè)推廣：偶圖G=（X,Y;E)的最大匹配的邊數(shù)是?X?-{?S?-?N(S)?}。(b)試證：若G為簡單偶圖，且?X?=?Y?=n及e>(k-1)n，則G有邊數(shù)為k的匹配。5.2.7*由Konig定理推導(dǎo)Hall定理。5.2.8*若非負(fù)實(shí)數(shù)矩陣Q的每行元素之和均為1，每列元素之和也均為1，則稱Q為雙隨機(jī)矩陣。稱一矩陣為置換矩陣如果它是每行和每列均恰只有一個(gè)1元素的（0，1）矩陣（∴是雙隨機(jī)的）。證明：(a)每個(gè)雙隨機(jī)矩陣一定是個(gè)方陣；(b)每個(gè)雙隨機(jī)矩陣Q都可表為置換矩陣的凸線性組合，即Q=c1P1+c2P2+……+ckPk。其中每個(gè)Pi都是置換矩陣，每個(gè)ci都是非負(fù)實(shí)數(shù)，且。5.2.9若偶圖G=(X,Y,E)中，X中每頂點(diǎn)的度3Y中每頂點(diǎn)的度，則G有使X每頂點(diǎn)都飽和的匹配。5.2.10設(shè)偶圖G=(X,Y,E)中，Y’為匹配M在Y中的端點(diǎn)集，則存在G的最大匹配M*，其端點(diǎn)集包含Y’。完美匹配稱H為G的奇分支（oddcomponent）?H為G的分支，且其頂點(diǎn)數(shù)為奇數(shù)。稱H為G的偶分支（evencomponent）?……。記o(G)=G中奇分支數(shù)。定理5.4(Tutte,1947)G有完美匹配?o(G-S)￡?S?"SìV(*)證明：（Lavasz證法）只要對簡單圖情形加以證明即可。T：設(shè)G有完美匹配M。對任SìV，令G1，……，Gn為G-S中的奇分支。因每個(gè)Gi的頂點(diǎn)數(shù)都是奇數(shù)，每個(gè)Gi中至少有一頂點(diǎn)ui與S中一頂點(diǎn)vi在M下相匹配。從而o(G-S)=n=?{v1，……，vn}?￡?S?。58 ü：反證。假設(shè)存在圖G滿足條件（*），但不含完美匹配。令G*為G的不含完美匹配的極大生成母圖。由于G-S是G*-S的生成子圖，o(G*-S)￡o(G-S)￡?S?"SìV。即G*滿足條件（*），又，上式中令S=?得o(G*)=0，因此n(G*)=偶數(shù)。令。因G不含完美匹配，U1V。斷言G*-S是一些完全圖的不相交并。從而，由于o(G*-U)￡?U?，G*-U中至多有?U?個(gè)奇分支。于是，由斷言易見，G*中有完美匹配，這與G*之假設(shè)矛盾。來證斷言反證。假設(shè)G*-U有一分支不是完全圖，則其中一定存在3個(gè)頂點(diǎn)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的邊導(dǎo)出子圖H。顯然，H中頂點(diǎn)的度都是2，因而H是一些圈的不相交并。且每圈都是偶圈，由M1與M2的邊交錯(cuò)組成。情況1xz與yw不在H的同一圈中：設(shè)yw在圈C上，則C中所有M1邊及C外所有M2邊一起構(gòu)成G*的一個(gè)完美匹配，矛盾。情況2xz與yw同在H的某一圈C上：不妨設(shè)x，y，w，z以這順序出現(xiàn)于C上。這時(shí)，C的yw……z節(jié)中的所有M1邊，及不在該節(jié)中的所有M2邊，以及邊yz，一起構(gòu)成G*的一個(gè)完美匹配，矛盾。#推論5.4(Peterson,1891)每一不含割邊的3-正則圖都有一完美匹配。證明：對任SìV，令G1，……，Gn為G-S中的所有奇分支。記mi為一端在Gi中而另一端在S中的邊數(shù)。則。但G中無割邊，因此mi33。從而3?S?=?！?S?3n=o(G-S)"SìV。故由定理5.4，G有完美匹配。#習(xí)題5.3.1*用Tutte定理推導(dǎo)Hall定理。5.3.2推廣推論5.4：若G是（k-1）邊連通的k-正則圖，且n是偶數(shù)，則G有完美匹配。5.3.3設(shè)G為一樹，證明：G有完美匹配?o(G-v)=1"v?V。5.3.4*證明Tutte定理的推廣：G的最大匹配的邊數(shù)=(n-d)/2，其中（C.Berge)人員分派問題問題n個(gè)工人x1，……，xn及n個(gè)工作y1，……，yn，已知每個(gè)工人都勝任一些工作。能否使每個(gè)工人都分派到一件他所勝任的工作？（（thepersonnel）assignmentprob.)解在偶圖G=(X,Y,E),?X?=?Y?,中求出其完美匹配（若存在的話）。Hungarianmethod(Edmonds,1965)以任一匹配M作為開始。（可取M=?）58 ①若M飽和X的每個(gè)頂點(diǎn)，停止（M為完美匹配）。否則，取X中M-不飽和頂點(diǎn)u，S?{u}，T??。②若N(S)éT,轉(zhuǎn)到③；否則，N(S)=T,停止（無完美匹配）。③取y?N(S)T。若y為M-飽和的，設(shè)yz?M，則S?Sè{z}，T?Tè{y}，回到②；否則，存在M-可擴(kuò)路P。M?MDE(P)，并回到①。注1算法用生長“以u(píng)為根的M-交錯(cuò)樹”的方法，來系統(tǒng)地搜索M-可擴(kuò)路。樹中除u外都是M-飽和的，直到碰到第一個(gè)M-不飽和的頂點(diǎn)時(shí)，即得一M-可擴(kuò)路。當(dāng)樹不能再生長下去時(shí)，即為N(S)=T之時(shí)。注2本算法是個(gè)‘好’算法：從一個(gè)M到下一個(gè)，至多進(jìn)行?X?次搜索運(yùn)算；M至多擴(kuò)大?X?次。習(xí)題5.4.1試述如何利用Hungarian算法求偶圖的最大匹配。Optimalassignmentproblem問題求賦權(quán)圖G=Kn，n的最大權(quán)匹配。稱l為（feasiblevertexlabelling)（f.v.l.)?l為V上的實(shí)函數(shù)，且滿足：l(x)+l(y)3w(xy)"x?X，y?Y。例。下面是一可行頂點(diǎn)標(biāo)號(hào)：記(相等子圖，equalitysubgraph）?以為邊集的G的生成子圖。定理5.5設(shè)偶圖G的可行頂點(diǎn)標(biāo)號(hào)l使包含一完美匹配，則是G的最優(yōu)匹配。證明：顯然，也是G的完美匹配，且。但對G的任一完美匹配M有。因此w(M)￡w()，即是G的最優(yōu)匹配。#下面是求最優(yōu)匹配算法的基本思想：任取一f.v.l.l作為開始。定，并在上任取一匹配M作為開始的匹配。用Hungarian算法在上找完美匹配。若找到，它就是G的最優(yōu)匹配；否則Hungarian算法停止于某匹配M’（不是完美匹配）及一M’交錯(cuò)樹H，它不能再“生長”。將l適當(dāng)修改成新的f.v.l.：使仍包含M’及H，且H在中又可繼續(xù)“生長”。重復(fù)上述過程。Kuhn-Munkeralgorithm（1955，1957；Edmonds改寫（1967））以任f.v.l.l作為開始。定，并在上任取一匹配M作為開始的匹配。①若M飽和X的每個(gè)頂點(diǎn)，則M為最優(yōu)匹配，停止；否則，任取一M-不飽和頂點(diǎn)u，S?{u}，T??。58 ②若éT，轉(zhuǎn)到③；否則，=T。計(jì)算=及f.v.l.：l?，?。③選取y?T，若y為M-飽和的，則存在yx?M，作S?Sè{x}，T?Tè{y}，并轉(zhuǎn)到②；否則，令P為中的M-可擴(kuò)-(u,y)路，M?MDE(P)，并轉(zhuǎn)到①。注1算法中每計(jì)算一次新的的計(jì)算量為O(n2)；在找到M-可擴(kuò)路之前，至多進(jìn)行?X?次搜索（每次可能作一次新的的計(jì)算）；而初始匹配M至多擴(kuò)大?X?次。因此是個(gè)‘好’算法（計(jì)算復(fù)雜性為O(n4))注2本算法也可用于解人員分派問題。習(xí)題5.5.1所謂n×n矩陣的一條對角線是指它的任n個(gè)兩兩不同行、不同列元素的集合。對角線的權(quán)是指它的n個(gè)元素的和。試找出下列矩陣的最小權(quán)對角線：（答：權(quán)=30）邊著色邊色數(shù)前提本章只討論無環(huán)圖。k-邊著色（k-edgecolouring）C?k種色在圖G的邊集上的一種分配。?C是E(G)的一個(gè)k-劃分，即C=（E1，。。。，Ek）（注：允許Ei=?）邊著色C是正常的?每個(gè)Ei都是G的一個(gè)匹配。G為k-邊可著色的（k-edgecolurable）?G有一正常k-邊著色。?存在E(G)的一個(gè)k-劃分C=（E1，。。。，Ek），使每個(gè)Ei都是G的一個(gè)匹配。（注：允許Ei=?）（顯然，G為k-邊可著色的TG為l-邊可著色的（l3k））G的邊色數(shù)（edgechromaticnumber）c￠(G)=min{k?G為k-邊可著色的}G為k-邊色的（k-edgechromatic）?c￠(G)=k。58 例。n個(gè)人舉行一些兩兩會(huì)談，每次會(huì)談?dòng)靡粋€(gè)單元時(shí)間。問最少要多少單元時(shí)間，才能安排完所有會(huì)談？例。Peterson圖有c￠=4。顯然，c￠3D。稱色i表現(xiàn)（rrepresented）于頂點(diǎn)v?與v相關(guān)聯(lián)的某一邊有色i。引理6.1.1設(shè)連通圖G不是奇圈，則G有一2-邊著色，使該二色表現(xiàn)于G的每個(gè)度32的頂點(diǎn)。證明：不妨設(shè)G為非平凡的。(A)若G為Euler圖：①若G為一圈：則G為偶圈，從而G的一個(gè)正常2-邊著色滿足要求。②若G不是個(gè)圈：則一定存在頂點(diǎn)v0，使d(v0)34(∵Euler圖每個(gè)頂點(diǎn)的度均為偶數(shù)）。令v0e1v1e2。。。eeve為G一的Euler環(huán)游（ve=v0）。令E1與E2分別為Euler環(huán)游中下標(biāo)為奇數(shù)與偶數(shù)的邊子集。則G的2-邊著色C=（E1，E2）滿足要求。(B)若G為非Euler環(huán)游：往G中加一新頂點(diǎn)v0，并將v0與G中每個(gè)度為奇數(shù)頂點(diǎn)都用一新邊連起來，得圖G’。顯然，G’為一Euler圖。令v0e1v1e2。。。eeve（ve=v0）為G的一Euler環(huán)游。與(A)②一樣定義C=（E1，E2），易見C’=(E1?E，E2?E）滿足要求。#記號(hào)c(v)=邊著色C表現(xiàn)于v的不同顏色數(shù)。顯然，c(v)￡d(v)"v?V。C為正常邊著色?c(v)=d(v)"v?V。稱G的k-邊著色C’為其k-邊著色C的一個(gè)改進(jìn)?。C為最優(yōu)k-邊著色（optimalk-edgecolouring）?C不能再改進(jìn)。引理6.1.2設(shè)C=（E1，。。。，Ek）為G的一個(gè)最優(yōu)k-邊著色。若G中有一頂點(diǎn)u及色i與j，使i不表現(xiàn)于u，而j在u上至少表現(xiàn)2次。則G[EièEj]中含u的分支是一奇圈。證明：令H為G[EièEj]中含u的分支。假設(shè)H不是奇圈，由引理6.1.1.，H有一2-邊著色，使該二色表現(xiàn)于H的每個(gè)度32頂點(diǎn)上。以這方式，用色i與j對H重新邊著色，得G的一個(gè)新的k-邊著色C’。顯然，c’(u)=c(u)+1c(v)3c(v)"v1u這與C為最優(yōu)矛盾。#定理6.1設(shè)G為偶圖，則c￠=D。證明：反證，假設(shè)c￠>D。令C為G的一個(gè)最優(yōu)D-邊著色，而u?V為使c(u)0，則G有一d-邊著色，使所有d種色在每一頂點(diǎn)上都表現(xiàn)。Vizing定理定理6.2(Vizing,1964)對簡單圖G有c￠=D或D+1。證明：（Bollobas）不妨設(shè)G中除uv1外都已用色1,2,……,D+1進(jìn)行了正常邊著色。注意到，G的每個(gè)頂點(diǎn)上都至少有一色未表現(xiàn)。令u，v1各有色i0，i1未表現(xiàn)。我們可逐步找到不同的色、邊序列：i0，i1，i2，……，ij，……；uv1，uv2，……，uvj，……。其中，色ij是頂點(diǎn)vj上未表現(xiàn)的（任意取定的）一色；邊uvj有色ij-1。j=2，3，……。顯然，上述過程至多進(jìn)行到某l（￡D）次而停止（無法繼續(xù)滿足上述條件）。這時(shí)只有兩種可能：(A)色il未表現(xiàn)于頂點(diǎn)u上（即沒有一條u的關(guān)聯(lián)邊uvk有色il）：重新進(jìn)行邊著色如下uvj改著色ij1￡j￡l-1并抹去邊uvl上的色il-1。得G中除uvl外的正常（D+1）邊著色。其中u與vl　上色il同時(shí)不表現(xiàn)。將uvl改著色il即得G的正常（D+1）邊著色。(B)il=ik某1￡k￡l-1：重新進(jìn)行邊著色如下將uvj改著色ij1￡j￡k并抹去邊uvk+1上的色ik。易見，H=的每個(gè)分支是路或圈，由色i0與ik的邊交錯(cuò)組成，且u，vk+1，vl在H中的度￡1。從而，該三頂點(diǎn)不可能同時(shí)在H的一分支中。這時(shí)只有二可能情形：58 ①u與vk+1不在H的同一分支中：將H的含vk+1分支中的色i0與ik對換，得G的除uvk+1外的正常（D+1）-邊著色，其中u與vk+1上色i0都未表現(xiàn)。從而，G有一正常（D+1）-邊著色。②u與vl不在H的同一分支中：再繼續(xù)調(diào)整邊著色如下，將uvj改著色ij并抹去邊uvl上的色（il-1）k+1￡j￡l-1。易見，上述更動(dòng)并未涉及色i0與ik，因此H保持不變。將H中含u分支的色i0與ik對換，得G的除uvl外的正常（D+1）-邊著色，其中u與vl上色i0都未表現(xiàn)。從而，G有一正常（D+1）-邊著色。#注1對一般圖有Vizing定理設(shè)G為無環(huán)圖，則D￡c￠￡D+m，其中m是G的重?cái)?shù)（連接G中每一頂點(diǎn)對上的最大邊數(shù)）。注2NP-completeprob。已給簡單圖G，是否有c￠=D？注3“2-邊連通、3-正則、簡單、平面圖都有c￠=3”?“4-色猜想成立”。習(xí)題6.2.1*找出適當(dāng)?shù)倪呏宰C明c￠(K2N-1)=c￠(K2N)=2n-1。6.2.2n為奇數(shù)的非空正則簡單圖G有c￠=D+1。6.2.3(a)設(shè)簡單圖G中n=2n+1且e>nD，則c￠=D+1；(b)利用(a)證明：①若G是從有偶數(shù)個(gè)頂點(diǎn)的簡單圖中剖分一條邊所得的圖，則c￠=D+1；②若G是從有奇數(shù)個(gè)頂點(diǎn)的簡單k正則圖中刪去少于k/2條邊所得的圖，則c￠=D+1。6.2.4(a)證明：任一無環(huán)圖G都有D-正則無環(huán)母圖。(b)利用(a)及習(xí)題5.2.3(b)證明：若G是無環(huán)圖且D是偶數(shù)，則c￠￡3D/2。6.2.5稱G為唯一k-邊可著色的，如果G的任意兩個(gè)k-邊著色都導(dǎo)致E有相同的劃分。證明：每個(gè)唯一3-邊可著色的3-正則圖都是Hamilton圖。6.2.6簡單圖的積圖是指頂點(diǎn)集為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種色在每個(gè)頂點(diǎn)上都表現(xiàn)。排課表問題問題m位教師X1，……，Xm和n個(gè)班級(jí)Y1，……，Yn，其中教師Xi要給班級(jí)Yj上pij節(jié)課。欲在最少節(jié)次p內(nèi)排完所有的課。?將偶圖G=(X,Y,E)(?X?=m，?Y?=n)的邊集E劃分成互不相交的p個(gè)匹配(E1，……，Ep)?求偶圖G的c￠（=D=p）-邊著色。由習(xí)題6.1.4知，上述問題有好算法。當(dāng)上述問題中若教室數(shù)有限時(shí)（教室數(shù)≥），若要在p（3D）節(jié)內(nèi)排完全部l（=?E?）節(jié)課，所需教室數(shù)c3。58 問題能否適當(dāng)排課，使全部l節(jié)課在p（3D）節(jié)內(nèi)排完，且每節(jié)課所用教室數(shù)￡？（∴"1￡i￡p）引理6.3設(shè)M，N為G的二不相交匹配，且?M?>?N?，則存在G的二不相交匹配M’，N’使?M’?=?M?-1，?N’?=?N?+1，且M’èN’=MèN。證明：令H=G[MèN]，則H的每個(gè)分支為一路或圈，由M及N的邊交錯(cuò)組成。且由于?M?>?N?，存在H的一個(gè)分支，它是路P，起、止于M邊。因此M’=MDE(P)及N’=NDE(P)即為所求。定理6.3設(shè)G為偶圖，p3D，則存在G的p個(gè)互不相交的匹配使E=M1è……èMp。且1￡i￡p。證明：由定理6.1,E可劃分為D個(gè)互不相交的匹配M1￠，……，MD￠。因此，對p3D，G有p個(gè)互不相交的匹配M1￠，……，MD￠，……，Mp￠。（令Mi￠=?當(dāng)i>p)使E=M1￠è……èMp￠。對邊數(shù)差>1的兩個(gè)匹配，重復(fù)使用引理6.3，最后可得所求的匹配M1，……，Mp。#注在實(shí)際應(yīng)用中，教師和班級(jí)往往會(huì)提出一些，例如所上節(jié)次，的要求，問題變得很復(fù)雜。Even，Itai&Shmir（1976）證明：在教師和班級(jí)提出條件時(shí)，判定課表的存在性問題是個(gè)NP-complete問題。甚至當(dāng)G為簡單偶圖，且學(xué)生不提出要求的情況下，也是如此。獨(dú)立集和團(tuán)獨(dú)立集定理7.1S為圖G的獨(dú)立集?VS為G的覆蓋。證明：S為獨(dú)立集?不存在兩端全在S中的邊?G的每邊至少有一端在VS中?VS為G的覆蓋。#SíV為G的團(tuán)（clique）?G[S]為一完全圖。獨(dú)立數(shù)（independentnumber）a(G)?最大獨(dú)立集的元素個(gè)數(shù)。覆蓋數(shù)（coeringnumber）b(G)?G的最小覆蓋的元素個(gè)數(shù)。推論7.1a+b=n。證明：設(shè)S為G的最大獨(dú)立集，則VS為其覆蓋，因此b￡|VS|=n-a。又，設(shè)K為G的最小覆蓋，則VK為其獨(dú)立集，因此a3|VK|=n-b?！郺+b=n。#58 注由上述證明知S為G的最大獨(dú)立集?VS為G的最小覆蓋。頂點(diǎn)著色色數(shù)正常（頂點(diǎn)）著色（proper（vertex）coluring）?每邊兩端不同色。k-（頂點(diǎn)）著色（k-（Vertex）colouring）?k種色在V(G)上的一種分配，且任二相鄰（的不同）頂點(diǎn)不同色。?V的一個(gè)k-劃分（V1，……，Vk）使每個(gè)Vi（可為?）都是G的一個(gè)獨(dú)立集。k-（頂點(diǎn)）可著色（k-（vertex）colourable）?G有一k-著色。顯然，G為k-可著色TG的基礎(chǔ)簡單圖為k-可著色。由此，我們約定本章只討論簡單圖。例。G為1-可著色的?G為一空圖。G為k-可著色的?G為k-部圖?！為k-可著色的TG為j-可著色的（k￡j）。色數(shù)（chromaticnumber）c(G)={k?G為k-可著色的}。G為k-色圖?c(G)=k。G為臨界的（crtical）?c(H)i，相鄰接。又，x1與x2不相鄰。于是，貪心著色法只用了￡D個(gè)色。#習(xí)題8.2.1.證明Brooks定理等價(jià)于下述命題：若G是k-臨界圖（k34），且不是完全圖，則2e3n(k-1)+1。8.2.2.利用Brooks定理證明：若G是D=3的無環(huán)圖，則c￠￡4。圍長和色數(shù)易見，若G中最大團(tuán)的頂點(diǎn)數(shù)k，則c3k。下面的定理表明，一個(gè)有很大色數(shù)的圖，其最大團(tuán)的頂點(diǎn)數(shù)不一定也很大。定理8.7對任正整數(shù)k，都存在不含K3的圖G使c(G)=k。(即，可找到色數(shù)任意大的圖，但其最大團(tuán)頂點(diǎn)數(shù)卻只為2。）證明：對k進(jìn)行歸納。當(dāng)k=1時(shí)，G1=K1滿足要求；當(dāng)k=2時(shí)，G2=K2也滿足要求；一般，設(shè)Gk=(Vk,Ek)，Vk={v1，……，vn）滿足要求（k32），則構(gòu)造Gk+1=(Vk+1,Ek+1)如下：令Vk+1=Vkè{u1，……，un}è{v}。其中u1，……，un，v為新加的頂點(diǎn)。將每個(gè)ui與N(vi)中每個(gè)頂點(diǎn)用新邊連起來；再將u與每個(gè)ui也都新邊連起來，所得圖即為Gk+1。易見，Gk+1中不含K3。又，Gk的任一k-著色可擴(kuò)充成Gk+1的（k+1）-著色如下：將每個(gè)ui著以vi上的色；再用一新色著在v上。顯然，這是Gk+1的正常（k+1）-著色，從而Gk+1是（k+1）-可著色的。余下只要再證Gk+1不是k-可著色的即可：不然，不妨設(shè)在該k-著色中v被著以色k。這時(shí)無一ui被著以色k。今，將每個(gè)被著以色k的頂點(diǎn)vi都改著以頂點(diǎn)ui的色。易見，這是Gk+1的正常k-著色。它導(dǎo)致Gk的一個(gè)正常（k-1）-著色，這與Gk為k色圖相矛盾。#注Hajos曾提出似乎是可信的猜想：G為k-色圖TG包含Kk的一個(gè)剖分。當(dāng)k=3及4時(shí)可證猜想成立。但1986年已證明該猜想不成立。習(xí)題8.3.1.證明：定理8.7中的圖Gk是一k-臨界圖。8.3.2*(a)設(shè)G是圍長至少為6的k-色圖（k32）。作一新圖H如下：取kn個(gè)新頂點(diǎn)集S及G的個(gè)互不相交的拷貝，且建立G的拷貝與S的n個(gè)頂點(diǎn)的一一對應(yīng)。再將G的每個(gè)拷貝與它在S中相對應(yīng)的n個(gè)頂點(diǎn)之間用一匹配連接起來。證明：H的色數(shù)至少為k+1，其圍長至少6。(b)試證：對任k32，都存在圍長為6的k-色圖。58 平面圖平圖和平面圖圖G可嵌入（embededable）于平面中?G可畫在平面上，使它的邊只在端點(diǎn)處才可能相交叉。（該畫法稱為G的一個(gè)平面嵌入（planarembedding）或平圖（planegraph））?G為平面圖（planargraph）例。K5，K3,3以及它們的剖分都是非平面圖。它們中任一個(gè)去掉任一邊后都是平面圖。注意平面圖和平圖間的區(qū)別。后者是前者的一個(gè)幾何實(shí)現(xiàn)（具體畫法）。Jordan曲線定理平面中任一Jordan曲線J（連續(xù)不自交的閉曲線），將余下的平面劃分成二不相交開集：J的內(nèi)部（interior）和J的外部（exterior），分別記為intJ和extJ。（它們的閉包分別記為IntJ和ExtJ）。連接intJ中一點(diǎn)到extJ中一點(diǎn)的任一條曲線一定與J交于某一點(diǎn)。定理9.1K5為非平面圖。證明：反證，假設(shè)G為K5的一個(gè)平圖。令G的五個(gè)頂點(diǎn)為v1，……，v5。注意到圈C=v1v2v3v1為平面上的一條Jordan曲線，且v4必在intC或extC中。若v4?intC，則邊v4v1，v4v2，與v4v3將intC劃分成三個(gè)區(qū)域intC1，intC2，和intC3。這時(shí)v5一定在上述三個(gè)區(qū)域及區(qū)域extC之一。若v5?extC，則因v4?intC，邊v4v5必與C交于某一點(diǎn)，這與G為平面圖的假設(shè)相矛盾。其它情形類似地也導(dǎo)致矛盾。#定理9.2.’K3,3為非平面圖。證明：類似，略。平面嵌入的慨念可推廣到其它平面上。稱圖G可嵌入于曲面S上　?G可畫在S上，使它的邊僅在端點(diǎn)處才可能相交叉。例。K5和K3,3都可嵌入于環(huán)面上；K3,3可嵌入于Mobius帶上；每個(gè)圖都可“嵌入”于三維空間R3中。定理9.2G可嵌入于平面上?G可嵌入于球面上。證明：利用球極平面射影，略。#對偶圖平圖G的面（face）?G將平面劃分出來的連通區(qū)域的閉包。外部面（exteriorface）?G中唯一的無界面。定理9.3.對平面圖G的任一頂點(diǎn)，都存在G的一個(gè)平面嵌入，使它在該嵌入的外部面上。58 證明：先將G嵌入于球面上，并將球面的北極放在含該頂點(diǎn)的G的一個(gè)面中，再利用球極平面射影。#記號(hào)F(G)=平圖G的面的集合。f(G)=平圖G的面數(shù)。b(f)=面f的周界。當(dāng)G連通時(shí)，b(f)可當(dāng)作一閉途徑，其中G在b(f)中的每一割邊在該途徑中都恰被走過兩次。當(dāng)G為2-連通時(shí)，b(f)為一圈。例。b(f1)=v1e1v2e5v4e8v6e9v6e8v4e4v1e6v7e7v7e6v1。b(f5)=v1e1v2e2v3e3v4e4v1。在平圖G中面f與它的周界上的邊和頂點(diǎn)相關(guān)聯(lián)。稱G的一邊e分隔（seperate）與它相關(guān)聯(lián)的面。易見，e為G的割邊?e只與G的一個(gè)面相關(guān)聯(lián)?e恰分隔G的一個(gè)面。e為G的非割邊?e恰與G的兩個(gè)面相關(guān)聯(lián)?e恰分隔G的兩個(gè)面。平圖G中面f的度（degree）dG(f)=與面f相關(guān)聯(lián)的邊數(shù)（割邊記為2）。例如，d(f1)=9。平圖G的對偶圖（dualgraph）G*是這樣的一個(gè)圖：它們之間有如下的一一對應(yīng)關(guān)系G的面f?G*的頂點(diǎn)f*；G的邊e?G*的邊e*。且G*的頂點(diǎn)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*是一平面圖，事實(shí)上存在G*的一個(gè)平面嵌入（稱為幾何對偶）如下：在G的每個(gè)面f中放置頂點(diǎn)f*，對應(yīng)于G的每一邊e，畫一條邊e*使它穿過e恰好一次（且不穿過G的其它邊）。例如，上例平圖G的對偶圖G*如右圖所示。由上述知，G*一定是連通平面圖。且有e是G的環(huán)?e*是G*的割邊。e是G的割邊?e*是G*的環(huán)。有時(shí)，為方便計(jì)，把平圖G的幾何對偶G*當(dāng)作G的對偶圖。這時(shí)，若G連通，則有G**=(G*)*@G。（當(dāng)G不連通時(shí)，上式不一定成立）。注意“平圖G@HTG*@H*”不一定成立。例如，右邊二平圖是同構(gòu)的，但它們的對偶圖并不同構(gòu)。因此，對偶圖的概念只對平圖有意義，不能推廣到平面圖上。由G*的定義易知：n(G*)=f(G)e(G*)=e(G)定理9.4設(shè)G為平圖，則58 證明：。#習(xí)題9.2.1.(a)證明：圖G是平面圖?G的每個(gè)塊都是平面圖。(b)試證：極小非平面圖是簡單塊。9.2.2.若一平圖和它的對偶圖同構(gòu)，則稱該平圖為自對偶的。(a)若G為自對偶的，則e=2n-2。(b)對每個(gè)n34，找出n頂點(diǎ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.設(shè)G是平圖，證明：(a)(G*)*@G?G是連通圖。(b)c(G**)=c(G)。9.2.5.設(shè)T是連通平圖G的生成樹，E*=。證明：T*=G*[E*]是G*的生成樹。9.2.6.每個(gè)面的度都是3的平圖稱為平面三角剖分圖。證明：每個(gè)n33的簡單平圖都是某簡單平面三角剖分圖的生成子圖。9.2.7.設(shè)G是n34的簡單平面三角剖分圖，證明：G*是簡單2-邊連通3-正則平面圖。9.2.8.*證明：任何平面三角剖分圖，都包含一個(gè)有2e(G)/3條邊的偶子圖。Euler公式定理9.5(Euler)設(shè)G為連通平圖，則n-e+f=2。證明：對f進(jìn)行歸納。當(dāng)f=1時(shí)，G的每邊為割邊（因每邊只分隔一個(gè)面）。又因G連通，從而G是樹（定理2.4)，于是e=n-1，定理成立。假設(shè)定理對fi。只要再證，D中任一弧(u,v)的兩端一定不同色：當(dāng)(u,v)為D￠中的弧時(shí)，它就是D￠中的一有向(u,v)-路，從而u與v不同色。當(dāng)(u,v)不是D￠中的弧時(shí)，由D￠之極大性知D￠+(u,v)包含一有向圈C。于是，C-(u,v)是D￠中的有向(v,u)-路，從而u與v也不同色。由上述知，D為(k+1)-可著色的，因此c￡k+1，得k3c-1，故D中有長為c-1的有向路。#注定理10.1在如下意義下是最佳的：對每個(gè)（無向）圖G，都存在G的一個(gè)定向圖，其最長有向路的長恰為c-1。58 證明：令（V1，……，Vc-1）為G的正常c-頂點(diǎn)著色。今作G的定向圖D如下：邊uv（不妨設(shè)，u?Vi，v?Vj）定向?yàn)榛?u,v)?ic-1的有向路。再由定理10.1得證。#稱完全圖的定向圖為競賽圖（tournament）推論10.1(Redei,1934)每個(gè)競賽圖都有一Hamilton路。證明：注意到c=n即可。#設(shè)(u,v)為有向圖D中的一弧，則稱u為v的內(nèi)鄰點(diǎn)（in-neighbour）；稱v為u的外鄰點(diǎn)（out-neighbour）。記和分別為有向圖D中頂點(diǎn)v的內(nèi)鄰集和外鄰集。定理10.2(Chavtal&Lavasz,1974)無環(huán)有向圖D包含一獨(dú)立集S，使D中的每個(gè)不在S中頂點(diǎn)，都是從S中某頂點(diǎn)通過長￡2的有向路可達(dá)的。證明：對n進(jìn)行歸納。當(dāng)n=1時(shí)，顯然成立。假設(shè)定理對頂點(diǎn)數(shù)mn的有向圖，而f是定義在V上的一個(gè)實(shí)函數(shù)。證明：D中或者存在一有向路(u0，u1，……，um)滿足f(u0)￡f(u1)￡……￡f(um)；或者存在一有向路(v0，v1，……，vn)滿足f(v0)>f(v1)>……>f(vn)。(b)試證：任意mn+1個(gè)不同整數(shù)的序列中，或者包含一個(gè)m項(xiàng)的遞增子序列；或者包含一個(gè)n項(xiàng)的遞減子序列10.2.6.(a)利用定理10.1和推論8.1.2證明：G有一個(gè)定向圖，它的最長有向路的長￡D。(b)給出(a)的構(gòu)造性證明。圈記號(hào)（S，T）是D中尾在S內(nèi)而頭在T內(nèi)的所有弧的集合。（S，T是V的子集）58 定理10.3(Moon,1966)n33的雙向連通競賽圖D中，每個(gè)頂點(diǎn)包含在一有向k-圈中，3￡k￡n。證明：設(shè)u是D的任一頂點(diǎn)。用對k的歸納法來證明。當(dāng)k=3時(shí)，令S=N+(u)，T=N-(u)。由D的雙向連通性知，S，T，（S，T）都是非空的。因此D中存在一弧(v,w)使v?S，w?T。從而u在有向3-圈(u,v,w,u)中，結(jié)論成立。假設(shè)對每一k，3￡k￡n1，則D包含一有向Hamilton圈。證明：反證，假設(shè)D不包含有向Hamilton圈。令C=（v1，v2，……，vq，v1）D中一最長有向圈。易見，C的長q>n/2（習(xí)題10.1.7)。令P為D-V(C)中的一條最長有向路，其長為m，其起、終點(diǎn)分別為u和v。顯然，n3q+m+1(1)m0使i?S，i+k?T（modq）i+j?SèT（modq）1￡jn(Gi)，該序列一定終止于G的一生成子圖Gn上。今對Gn定向如下：把G1定向?yàn)橐挥邢蛉?；把Pi定向?yàn)橐灰詖i為起點(diǎn)的有向路；把Qi定向?yàn)橐詖i為終點(diǎn)的有向路。顯然，每個(gè)Gi有一雙向連通定向。由于Gn是G的一生成子圖，G也存在雙向連通定向圖。定理（Nash-Williams，1960）G為2k-邊連通的TG有k-弧連通定向圖。（證略）（即|（S，`S）|3k"?1SìV）上述定理的特殊情形為以下定理，其證明較容易，留給讀者來完成：定理10.6G為2k-邊連通，且有一Euler跡TG有一k-弧連通定向圖。習(xí)題10.5.1通過`考察Petersen圖證明以下結(jié)論不成立：每個(gè)圖都有一定向圖，使得對每個(gè)SíV，（S，）和（，S）的弧數(shù)相差最多為1。10.5.2.(a)證明Nash-Williams定理下述命題：若G的每個(gè)鍵至少有2k-條邊，則存在G的一個(gè)定向圖，其中每個(gè)鍵在每個(gè)方向上都至少有k-條弧。(b)通過考察Grotzsch圖證明以下結(jié)論不成立：若G的每個(gè)圈至少有2k-條邊，則存在G的一個(gè)定向圖，其中每個(gè)圈在每個(gè)方向上都至少有k-條弧。58 網(wǎng)絡(luò)流一個(gè)網(wǎng)絡(luò)（Network）N是由一有向圖（稱為基礎(chǔ)有向圖（underlyingdigraph）；二特定的不相交頂點(diǎn)子集X和Y；以及弧集A上定義的非負(fù)整數(shù)值函數(shù)c(×)（稱為容量函數(shù)）組成的。其中，X的每個(gè)頂點(diǎn)稱為發(fā)點(diǎn)（source）；Y的每個(gè)頂點(diǎn)稱為收點(diǎn)（sink）；I=V(XèY)中每個(gè)頂點(diǎn)稱為中間頂點(diǎn)（intermediatevertex）；每弧a上c(a)的值稱為a的容量（capacity）。設(shè)f(.)為定義在弧集A上的實(shí)函數(shù)，對任一弧子集K，記。當(dāng)K=（S，`S）時(shí)，記f+(S)=f(S,`S)。類似地，記f-(S)=f(`S,S)。由此，特別地，有f+(v)=({v},V{v})；f-(v)=(V{v),{v})。定義在A(D)上的整數(shù)值函數(shù)f(·)若滿足以下條件，就稱為網(wǎng)絡(luò)N上的流（flow）：①0￡f(a)￡c(a)，"a?A(D)。稱為容量約束（capacityconstraint）。②f+(v)=f-(v)"v?I。稱為守恒條件（conservationcondition）。注f(a)可當(dāng)作物資沿弧a輸送的流量。但不能將流當(dāng)作水的流動(dòng)！零流（zeroflow）f?f(a)=0，"a?A(D)。設(shè)f是網(wǎng)絡(luò)N上的流，而S是其頂點(diǎn)子集。稱f+(S)-f-(S)為流出S的合成流（resultantflowoutofS）f-(S)-f+(S)為流進(jìn)S的合成流（resultantflowintoS）容易證明（習(xí)題），f+(S)-f-(S)=f+(X)-f-(X)=f-(Y)-f+(Y)（記為）=valf稱為流f的值。最大流（maximumflow）f?不存在流f＇使valf＇>valf。求解最大流問題時(shí)，為簡化計(jì)，可將多收、發(fā)點(diǎn)問題轉(zhuǎn)化為單收、發(fā)點(diǎn)問題，如右圖所示：往N中加兩頂點(diǎn)x和y作為新網(wǎng)絡(luò)N＇的發(fā)點(diǎn)和收點(diǎn)；并用容量為∞的一條新弧將x連接到X中每個(gè)頂點(diǎn)；用容量為∞的一條新弧將Y中每個(gè)頂點(diǎn)連接到y(tǒng)。N和N＇中的流f和f＇之間有一簡單的對應(yīng)關(guān)系：當(dāng)f滿足條件f+(xi)-f-(xi)30"xi?X；f-(yj)-f+(yj)30"yj?Y；58 （不難證明，對求解最大流問題只要考慮這種情形就夠了。）可定義f＇如下易見，f＇確實(shí)是N＇上的流，且valf＇=valf（習(xí)題）反之，N＇的任一流f＇在N的弧集上的限制（restriction）f是N上的流，且valf=valf＇（習(xí)題）。由上述知網(wǎng)絡(luò)N和N＇有相同的最大流的值，為簡單計(jì)以下三節(jié)中將只討論單收、發(fā)點(diǎn)之情形。習(xí)題11.1.1.對于下列各網(wǎng)絡(luò)，確定所有可能的流和最大流的值：11.1.2.證明：對N中任一流f及任一SíV，都有=f+(S)-f-(S)。11.1.3.證明：對N中任一流f有f+(X)-f-(X)=f-(Y)-f+(Y)。割設(shè)網(wǎng)絡(luò)N只有一個(gè)收點(diǎn)x及一個(gè)發(fā)點(diǎn)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是以發(fā)點(diǎn)x為起點(diǎn)，以收點(diǎn)y為終點(diǎn)的f-不飽和路。若N中有一f-可增路P，則，易見，f不是最大流。這時(shí)，可沿P輸送一附加流而得一新流f′：58 。(11.9)這時(shí)，valf′=valf+，并稱f′為基于P的修改流（revisedflowbasedonP）。定理11.2N中的流f為最大流?N不含f-可增路。證明：T：反證，若N中含一f-可增路P，則f不是最大流，因?yàn)榛赑的修改流f′的值更大。ü：令S={v|$f-不飽和（x，v）-路}，則顯然有x?S；y?`S；∴K=（S，`S）為割。注意到，這時(shí)（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)在任一網(wǎng)絡(luò)中，最大流的值=最小割的容量。上定理是圖論的一重大結(jié)果，其它圖論結(jié)果，例如，偶圖的匹配、Menger定理等，可由它利用適當(dāng)選取網(wǎng)絡(luò)來導(dǎo)出。求最大流的算法原理：1°以一已知流f（例如，零流）作為開始。2°系統(tǒng)搜索f-可增路P。若P不存在，停止（f-為最大流）。3°若P存在，求出基于P的修改流f′，令f?f′，并轉(zhuǎn)到2°。系統(tǒng)搜索f-可增路P標(biāo)號(hào)法（通過標(biāo)號(hào)‘生長’f-不飽和樹T）開始，標(biāo)x以l(x)=￥。（此后，在T的生長過程中，T中每個(gè)頂點(diǎn)將標(biāo)以l(v)=i(Pv)，其中Pv是T中惟一的(x,v)-路。）(1)若a=（u，v）為f-不飽和弧，且u已標(biāo)號(hào)，而v未曾，則標(biāo)v以l(v)=min{l(u),c(a)-f(a)}。(2)若a=（v，u）為f-正的，且u已標(biāo)號(hào)，而v未曾，則標(biāo)v以l(v)=min{l(u),f(a)}上述標(biāo)號(hào)過程一直進(jìn)行到：或者y已標(biāo)號(hào)（“breakthrough”，找到了f-可增路）；或者所有已標(biāo)號(hào)頂點(diǎn)都已掃描，但無頂點(diǎn)可再標(biāo)號(hào)（f為最大流）。標(biāo)號(hào)程序（labellingmethod，F(xiàn)ord&Fulkerson,1957)以已給流f（例如，零流）作為開始。①標(biāo)x以l(x)=∞。掃描（scan）x。②對正在掃描的（已標(biāo)號(hào)）頂點(diǎn)u，(i)檢查每條以u(píng)為尾的弧a=（u，v）。如果a為f-不飽和的，且頂點(diǎn)v未標(biāo)號(hào)，則標(biāo)v以l(v)=min{l(u),c(a)-f(a)}。(ii)檢查每條以u(píng)為頭的弧a=（v，u）。如果a為f-正的，且頂點(diǎn)v未標(biāo)號(hào)，則標(biāo)v以58 l(v)=min{l(u),f(a)}。③若y已標(biāo)號(hào)（‘breakthrough’，找到了一條f-可增路），則轉(zhuǎn)到④；否則選一未曾掃描的已標(biāo)號(hào)頂點(diǎn)進(jìn)行掃描，并回到②。如果已標(biāo)號(hào)頂點(diǎn)都已掃描過，停止（得最大流。且由已標(biāo)號(hào)頂點(diǎn)集S，得最小割（S，`S））。④找一f-可增路P，令f?，去掉全部標(biāo)號(hào)，并回到①。注上述算法還不是‘好’算法，例如右圖中的網(wǎng)絡(luò)，其最大流的值為2m。但若標(biāo)號(hào)程序以零流開始，且反復(fù)地選取xuvy及xvuy為f-可增路，則總共要進(jìn)行2m+1次標(biāo)號(hào)程序，因此其計(jì)算量為輸入長（=O(log2m))的指數(shù)函數(shù)。Edmonds&Karp(1970)證明，若在上述標(biāo)號(hào)程序中采用firstlabelledfirstscan（即廣度優(yōu)先）法則，則，可使該算法成為好算法（復(fù)雜性為O(ne2))。習(xí)題11.3.1.證明：由(11.9)式給出的函數(shù)f是valf′=valf+的流。11.3.2.試求右圖所示網(wǎng)絡(luò)的最大流。（答：最大流的值=39）11.3.3.證明：在具有整數(shù)容量的任一網(wǎng)絡(luò)N中，總存在一最大流f，使f(a)在每一弧a上都取整數(shù)值。11.3.4.考察在每條弧a上都伴隨一整數(shù)b(a)￡c(a)的網(wǎng)絡(luò)N，試修改標(biāo)號(hào)法，來求N中滿足條件b(a)￡f(a)￡c(a),"a?A,的最大流f。（假設(shè)存在滿足這個(gè)條件的初始流）。11.3.5.設(shè)網(wǎng)絡(luò)N的每個(gè)中間頂點(diǎn)v都伴隨一非負(fù)整數(shù)m(v)。試修改該網(wǎng)絡(luò)，并將標(biāo)號(hào)法應(yīng)用于它，來求出滿足條件f-(v)￡m(v),"v?V{x,y}，的最大流f。11.3.6試用網(wǎng)絡(luò)理論證明Hall定理（第五章）。Menger定理引理11.4設(shè)網(wǎng)絡(luò)N的發(fā)點(diǎn)為x，收點(diǎn)為y，且每弧的容量都為1，則(a)N中最大流的值=N中弧不重的有向(x,y)-路的最大數(shù)目m。(b)N中最小割的容量=破壞N中所有有向(x,y)-路所需去掉的最少弧數(shù)n。證明：(a)令f*為N中在每弧上取整數(shù)值的最大流；D*為由D中去掉所有f*-零弧而得到的有向（生成子）圖。顯然，f*(a)=1"a?A(D*)。因此，有①；②"v?V{x，y}；于是，由習(xí)題10.3.3.知，D*中，因而D中，有valf*條弧不重的有向（x，y）-路。因此m3valf*。58 另一方面，設(shè)P1，……，Pm為N中任一組m條弧不重的有向（x，y）-路，定義函數(shù)f(a)=顯然，f為N中值為m的流。由于f*為最大流，得valf*3m，從而valf*=m。(b)令=(S,`S)為N中的最小割，則易見N-中從x不可達(dá)y。即就是去掉它就破壞所有有向(x,y)-路的弧集，因此n￡||=cap。另一方面，設(shè)Z為n條弧的集合，去掉Z后就破壞所有有向（x,y)-路。令S為N-Z中x可達(dá)的頂點(diǎn)集。顯然，x?S，y?`S，從而K=(S,`S)為N中的一個(gè)割。又，由S的定義知，N-Z中不含(S,`S)的弧，因此KíZ，從而cap￡capK=|K|￡|Z|=n，∴n=cap。#定理11.4設(shè)x和y為有向圖D中任二頂點(diǎn)，則D中弧不重的有向(x,y)-路的最大數(shù)目=破壞D中所有有向(x,y)-路所需去掉的最少弧數(shù)。證明：由D作網(wǎng)絡(luò)N：其發(fā)點(diǎn)為x，收點(diǎn)為y，每弧容量1。再用引理11.4及定理11.3即得。#定理11.5設(shè)x和y為圖G中任二頂點(diǎn)，則G中邊不重的(x,y)-路的最大數(shù)目=破壞G中所有(x,y)-路所需去掉的最少邊數(shù)。證明：作圖G的伴隨有向圖（associateddigraph），再用定理11.4即得。#推論11.5(Menger定理）G為k-邊連通的?G中任二頂點(diǎn)都至少被k條邊不重的路所連接。證明：由k-邊連通定義即得。#定理11.6設(shè)x和y為有向圖D中二不同頂點(diǎn)，且D中沒有連x到y(tǒng)的弧，則D中內(nèi)部不相交的有向(x,y)-路的最大數(shù)目=破壞D中所有有向(x,y)-路所需去掉的最少頂點(diǎn)數(shù)。證明：由D作有向圖D’如下：①將每個(gè)v?V{x.,y}分成二新頂點(diǎn)v’及v’’，并連以新弧(v’,v’’)；②將D中以v?V{x.,y}頭的弧代之以以v’為頭的?。灰詖為尾的弧代之以以v’’為尾的弧。于是易見，D’中一有向(x,y)-路與D中一有向(x,y)-路之間存在1-1對應(yīng)關(guān)系（通過將D’中一有向(x,y)-路上的每一(v’,v’’)弧收縮成v；或?qū)中一有向(x,y)-路的每一頂點(diǎn)v分裂成弧(v’,v’’)）。又，易見，D’中二有向(x,y)-路為弧不重的?對應(yīng)的D中的二有向(x,y)-路為內(nèi)部不相交的。因此，D’中弧不重的有向(x,y)-路的最大數(shù)目=D中內(nèi)部不相交的有向(x,y)-路的最大數(shù)目。類似地，破壞D’中所有有向(x,y)-路所需去掉的最少弧數(shù)。=破壞D中所有有向(x,y)-路所需去掉的最少頂點(diǎn)數(shù)。（習(xí)題11.4.1.)再用定理11.4，定理得證。#定理11.7設(shè)x和y為圖G中二不相鄰頂點(diǎn)，則G中內(nèi)部不相交的(x,y)-路的最大數(shù)目58 =破壞G中所有(x,y)-路所需去掉的最少頂點(diǎn)數(shù)。證明：將定理11.6用于G的伴隨有向圖上即得。#推論11.7（Menger定理）設(shè)n(G)3k+1，則G為k-連通的?G中任二不相同頂點(diǎn)至少被k條內(nèi)部不相交的路所連接。證明：顯然。#習(xí)題11.4.1.證明在定理11.6的證明中提到的命題：破壞D’中所有有向(x,y)-路所需去掉的最少弧數(shù)=破壞D中所有有向(x,y)-路所需去掉的最少頂點(diǎn)數(shù)。11.4.2.從定理11.7導(dǎo)出Konig定理。11.4.3.設(shè)S和T是圖G中二不相交頂點(diǎn)子集。證明：起點(diǎn)在S、終點(diǎn)在T的頂點(diǎn)不相交的路的最大數(shù)目=把S和T分離開來所需去掉的最少頂點(diǎn)數(shù)。（即，去掉后沒有一個(gè)分支同時(shí)包含S和T中的頂點(diǎn)）11.4.4.*證明：若G為k（32）-連通圖，則G的任何k個(gè)頂點(diǎn)共圈?？尚辛髟诰W(wǎng)絡(luò)N的每個(gè)發(fā)點(diǎn)xi上指定一非負(fù)整數(shù)s(xi)，稱為供給（supply）；在每個(gè)收點(diǎn)yj上指定一非負(fù)整數(shù)(yj)，稱為需求（demand）。稱N中的流f為可行流（feasibleflow）?f+(xi)-f-(xi)￡s(xi)"xi?X；f-(yj)-f+(yj)3(yj)"yj?Y。問題存在可行流的充要條件是什麼？記s(S)=；。定理11.8(Gale,1957)N中存在可行流?c(S,`S)3(Y?`S)-s(X?`S)"SíV。證明：由N作N’如下：①往N里添加二新頂點(diǎn)x及y；②從x到每個(gè)xi?X連以容量為s(xi)的?。虎蹚拿總€(gè)yj?Y到y(tǒng)連以容量為(yj)的弧；④將x和y分別當(dāng)作N’的發(fā)點(diǎn)和收點(diǎn)。易見，N中有可行流?N’有一個(gè)流使割(Y,{y})中每一弧都飽和。（習(xí)題11.5.1.)但N’中對應(yīng)流的值=(Y)=cap(Y,{y})。由推論11.1知，它是N’中的最大流，故58 N中有可行流?對N’中每一割(Sè{x}，`Sè{y})都有cap(Sè{x}，`Sè{y}）3(Y)。但cap(Sè{x}，`Sè{y}）=c’(S,`S)+c’(S,{y})+c’({x},`S)(c’(.)表示N’中的容量函數(shù)）=c(S,`S)+(Y?S)+s(X?`S)，而(Y)=(Y?`S)+(Y?S)，得證。#58