第1章-圖和子圖.ppt

1、第一章圖的基本概念,1.1圖的概念1.2同構(gòu)1.3圖的矩陣和頂點的度1.4子圖1.5路和連通性1.6圈1.7最短路問題,1.1圖的概念,Knigsberg七橋問題電網(wǎng)絡(luò)四色猜想,圖G=(V(G),E(G)，其中V(G)=V-頂點集，-頂點數(shù)E(G)=E-邊集，-邊數(shù)例如，下圖中，V=a,b,f,E=k,p,q,ae,af,ce,cf,注意，右圖僅僅是圖G的一個幾何實現(xiàn)（geometricrealization,代表representation），它們有無窮多個，隨頂點位置及邊的形狀而不同。真正的圖G是上面所給出式子，它與頂點的位置、邊的形狀等無關(guān)。不過今后對圖G及其幾何實現(xiàn)將經(jīng)常不加以區(qū)別。,

2、稱邊ad與頂點a(及d)相關(guān)聯(lián)(incident)。也稱頂點b(及f)與邊bf相關(guān)聯(lián)。稱頂點a與e相鄰(adjacent)。也稱有公共端點的一些邊，例如p與af彼此相鄰。稱一條邊的兩個頂點為它的兩個端點環(huán)（loop，selfloop）：如邊k，它的兩個端點相同。棱（link）：如邊ae，它的兩個端點不相同。重邊：如邊p及邊q。簡單圖：（simplegraph）無環(huán)，無重邊平凡圖：僅有一個頂點的圖。注意：任何一圖都有V。記號：（,）,例題1.1若G為簡單圖，則。1.2若一群人中，凡相識的兩人都無公共朋友，凡不相識的兩人都恰有兩個公共朋友，則每人的朋友數(shù)相等。,1.2同構(gòu),例如在下圖中，稱圖G恒等

3、于圖H(記為G=H)VG)=V(H),E(G)=E(H)。,圖G同構(gòu)于圖F（記為GF）V(G)與V(F),E(G)與E(F)之間各存在一一映射，及且這二映射保持關(guān)聯(lián)關(guān)系，即：,注兩個圖同構(gòu)是指”它們有相同的結(jié)構(gòu)”，僅在頂點及邊的標(biāo)號上或兩個圖的畫法上有所不同而已。往往將同構(gòu)慨念引伸到非標(biāo)號圖中，以表達兩個圖在結(jié)構(gòu)上是否相同。注判定兩個圖是否同構(gòu)是個未解決的困難問題（openproblem）。,完全圖(completegraph)Kn空圖（emptyg.）E=。V(V)為獨立集V中任二頂點都互不相鄰。二部圖（偶圖，bipartiteg.）G=(X,Y;E)存在V(G)的一個2-劃分(X,Y)（即

4、V(G)=XY，且XY=），使X與Y都是獨立集。,完全二部圖Km,n二部圖G=(X,Y;E)，其中X和Y之間的每對頂點都相鄰，且X=m,Y=n。類似地可定義，完全三部圖（例如，Km,n,p），完全n-部圖等。,例。用標(biāo)號法判定二部圖。用紅藍兩種顏色進行頂點標(biāo)號如下：任取一頂點v標(biāo)以紅色。再將v的所有相鄰頂點都標(biāo)以蘭色。這時稱v為已掃描頂點。若尚存在一已標(biāo)號未掃描頂點u，將它的所有相鄰頂點，（若不出現(xiàn)矛盾）都標(biāo)以（其相異色）紅色，并稱u為已掃描頂點。如此繼續(xù)下去，直到或者所有頂點都已標(biāo)號，從而該圖為一二部圖；或者在標(biāo)號過程中出現(xiàn)矛盾，該圖為非二部圖。,習(xí)題,1.2.1GH(G)=(H),(G)=

5、(H)。并證明其逆命題不成立。1.2.2證明下面兩個圖不同構(gòu)：,1.2.3證明下面圖1與圖2是同構(gòu)的；而圖1與圖3是不同構(gòu)的：1.2.4證明兩個簡單圖G和H同構(gòu)存在一一映射f:V(G)V(H)，使得uvE(G)當(dāng)且僅當(dāng)f(u)f(v)E(H)。,1.2.5證明：(a).(Km,n)=mn;(b).對簡單二部圖有2/4.1.2.6記Tm,n為這樣的一個完全m-部圖：其頂點數(shù)為n，每個部分的頂點數(shù)為n/m或n/m個。證明：(a).(Tm,n)=其中k=n/m.(b)*.對任意的n頂點完全m-部圖G，一定有(G)(Tm,n)，且僅當(dāng)GTm,n時等式才成立。1.2.7所謂k-方體是這樣的圖：其頂點是由

6、0與1組成的有序k-元組，其二頂點相鄰當(dāng)且僅當(dāng)它們恰有一個坐標(biāo)不同。證明k-方體有2k個頂點，k*2k-1條邊，且是一偶圖。,1.2.8簡單圖G的補圖Gc是指和G有相同頂點集V的一個簡單圖，在Gc中兩個頂點相鄰當(dāng)且僅當(dāng)它們在G中不相鄰。(a).畫出Kcn和Kcm,n。(b).如果GGc則稱簡單圖G為自補的。證明：若G是自補的，則0,1(mod4)。1.2.9設(shè)，且，則H一定是個完全二部圖。1.2.10若的簡單圖中如下性質(zhì)成立則G一定是個完全（某）m部圖。,1.3圖的矩陣和頂點的度,M(G)=mi,j,(關(guān)聯(lián)矩陣)mi,j=頂點vi與邊ej的關(guān)聯(lián)次數(shù)=0,1,2.,A(G)=ai,j,ai,j=

7、連接頂點vi與vj的邊數(shù)。（鄰接矩陣）,頂點v的度dG(v)=G中與頂點v相關(guān)聯(lián)邊數(shù)。（每一環(huán)記為2）記號：最大、最小度，。（(G),(G)）奇點：度為奇數(shù)的頂點；偶點：度為偶數(shù)的頂點；孤立點：度為0的頂點；懸掛點：度為1的頂點；懸掛邊：懸掛點的關(guān)聯(lián)邊。,定理1.3.1(handshakinglemma)任一圖中，推論1.1任一圖中，度為奇數(shù)頂點的個數(shù)為偶數(shù)。,例：任一多面體中，邊數(shù)為奇數(shù)的外表面的數(shù)目為偶數(shù)。（提示：作一圖，其頂點對應(yīng)于多面體的面，且二頂點相鄰當(dāng)且僅當(dāng)對應(yīng)的兩個面相鄰（即有公共邊界）。）k-正則圖（k-regularg.),習(xí)題,1.3.1證明：2/。1.3.2若k-正則偶圖

8、(k0)的2-劃分為(X,Y),則X=Y。1.3.3在人數(shù)1的人群中，總有二人在該人群中有相同的朋友數(shù),1.3.4設(shè)V(G)=，則稱(d(v1),d(v2),d(v)為G的度序列。證明：非負整數(shù)序列(d1,d2,dn)為某一圖的度序列是偶數(shù)。1.3.5證明：任一無環(huán)圖G都包含一偶生成子圖H，使得dH(v)dG(v)/2對所有vV成立。（提示：考慮G的邊數(shù)最多的偶生成子圖）1.3.6*設(shè)平面上有n個點，其中任二點間的距離1，證明：最多有3n對點的距離=1。,1.4子圖,子圖(subgraph)HGV(H)V(G),E(H)E(G)。真子圖HGHG且HG。母圖（supergraph）。生成子圖（s

9、panningsubg.）HHG且V(H)=V(G)。生成母圖。基礎(chǔ)簡單圖（underlyingsimpleg.）：從一圖中去掉其所有重邊及環(huán)后所得的剩余（簡單圖）圖稱之為其基礎(chǔ)簡單圖。導(dǎo)出子圖（inducedsubgraph.）GV，(非空VV)以V為頂點集，以G中兩端都在V上的邊全體為邊集構(gòu)成的G的子圖邊導(dǎo)出子圖GE(非空EE)以E為邊集，以E中所有邊的端點為頂點集的的子圖。,GV,GE兩種子圖對應(yīng)于取子圖的兩種基本運算。下面是取子圖的另兩種基本運算：G-V去掉V及與V相關(guān)聯(lián)的一切邊所得的剩余子圖。即GVVG-E從中去掉E后所得的生成子圖,例。G-b,d,g,(=GEb,d,g)G-b,c

10、,d,g,(GEb,c,d,g)G-a,e,f,g.(GEa,e,f,g)注意GEE與G-E雖有相同的邊集，但兩者不一定相等：后者一定是生成子圖，而前者則不然。,上述四種運算是最基本的取子圖運算，今后經(jīng)常會遇到，一定要認真掌握好。關(guān)于子圖的另一些定義還有：G+E往G上加新邊集E所得的（G的）母圖。為簡單計，今后將Ge簡記為Ge；G-v簡記為G-v。設(shè)G1,G2G，稱G1與G2為不相交的（disjiont）V(G1)V(G2)=(E(G1)E(G2)=)邊不相交（edge-distjiont，邊不重的）E(G1)E(G2)=。（但這時G1與G2仍可能為相交的）。并圖G1G2,當(dāng)不相交時可簡記為G

11、1+G2.交圖G1G2.,習(xí)題,1.4.1證明：完全圖的每個導(dǎo)出子圖是完全圖；偶圖的每個導(dǎo)出子圖是偶圖。1.4.2*設(shè)G為一簡單圖，1n-1。證明：若4，且G中每個n頂點的導(dǎo)出子圖均有相同的邊數(shù)，則GK或Kc。,1.5路和連通性,途徑（walk）例如圖G的(u,x)-途徑W=ueyfvgyhwbvgydxdydx(有限非空序列)=uyvywvyxyx(簡寫法-當(dāng)不引起混淆時),起點（origin）u。終點（terminus）x。內(nèi)部頂點（internalvertex）y,v,w,x。（注意，中間出現(xiàn)的x也叫內(nèi)部頂點。）長邊數(shù)（重復(fù)計算）。節(jié)（段，section）。例如W的(y,w)-節(jié)=yvw

12、。W-1（逆途徑）,WW（兩條途徑W與W相銜接。要求：W的終點=W的起點）。跡(trail)邊各不相同的途徑（頂點可重復(fù)出現(xiàn)）。例如，yvwyx。路(path)頂點各不相同的途徑。（邊也一定不重復(fù)出現(xiàn)。路可當(dāng)作一個圖或子圖）。例如，yvwx。距離dG(u,v)=圖G中頂點u與v之間最短路的長。,uyvywvyxyx,定理1.5.1G中存在(u,v)-途徑G中存在(u,v)-路。證明：是顯然的；：設(shè)G中存在-途徑其中若W中的頂點互不相同，則W就是(u,v)-路；不然，設(shè)其中有（），則也是一條-途徑，長度比W短。若其中仍有重復(fù)頂點出現(xiàn)，則繼續(xù)上述過程。由于W長度的有限性，上述過程必停止于一(u,v

13、)-路。,圖的連通性：稱G中頂點u與v為連通的(connected)G中存在(u,v)-路(G中存在(u,v)-途徑。)容易驗證，V上的連通性是V上的等價關(guān)系，它將V劃分為一些等價類：V1，V使每個Vi中的任二頂點都連通（即存在(u,v)-路）；而不同Vi與Vj之間的任二頂點都不連通。,稱每個GVii=1,2,.為G的一個分支（component）;稱(G)為G的分支數(shù)。稱G為連通圖(G)=1G中任兩點間都有一條路相連。稱G為非連通圖(G)1。,記號：對任一非空SV，令=VS,記S,=G中兩端分別在S及中的一切邊的集合。（后文中將稱為邊割）,容易證明：定理1.5.2G連通對任SV都有S,例1.

14、5簡單圖G中，kG中有長k的路。（注意到，G中任一最長路P的起點（終點）的所有鄰接點全在P上。）,習(xí)題,1.5.1證明：G中長為k的途徑的數(shù)目,就是Ak中的(I,j)元素，其中A為G的鄰接矩陣。1.5.2證明：對簡單圖G有，G連通。對于1，試給出的不連通簡單圖。1.5.3證明簡單圖G中，/2-1G連通。當(dāng)是偶數(shù)時，試給出一個不連通的(/2-1)正則簡單圖。,1.5.4G不連通Gc連通。1.5.5對任意圖G的任一邊e，有(G)(G-e)(G)+1。1.5.6G連通，且d(v)=偶數(shù)，vV(G-v)d(v)/2,vV.1.5.7連通圖中，任二最長路必有公共頂點。1.5.8對任一圖的任三個頂點u,v

15、,w都有d(u,v)+d(v,w)d(u,w)。1.5.9任一的簡單、連通、非完全圖中，一定有三個頂點u,v,w，使得uv,vwE而uwE。1.5.10若圖G中恰有兩個奇點u與v，則G中一定有一(u,v)路。,1.6圈,閉途徑（closedwalk）起點=終點且長0的途徑。閉跡(closedtrail)邊各不相同的閉途徑。圈（cycle）頂點各不相同的閉跡。（可當(dāng)作一圖或子圖。）,例：閉途徑：uyvyu;uywxywvu；uyuyu。閉跡：uyxwyvu。圈：yfvgy;uywvu。k-圈（k-cycle）長為k的圈。奇圈(oddcycle)。偶圈(evencycle)。,例：1-圈（即一條環(huán)

16、），2-圈(由兩條重邊組成)，3-圈（又稱三角形）。,定理1.2G為二部圖G不含奇圈。,證明：設(shè)G的2-劃分為（X,Y），由G的定義，G的任一圈中，X和Y的頂點一定交錯出現(xiàn)，從而其長必為偶數(shù)。：不妨設(shè)G為連通的。任取一頂點u,令X=xVd(u,x)=偶數(shù),Y=yVd(u,y)=奇數(shù)。易見，(X,Y)為V的2-劃分，,所以只要再證X（和Y）都是G的獨立集（即X（或Y）中任二頂點v，w都不相鄰）即可。令P與Q分別為最短(u,v)-路與最短(u,w)-路。設(shè)u為P與Q的最后一個公共頂點；而P與Q分別為P的(u,v)-節(jié)與Q的(u,w)-節(jié)。則P與Q只有一公共頂點。又，由于P與Q的(u,u)-節(jié)的長相

17、等，P與Q的長有相同的奇偶性，因此v與w不能相鄰，不然，v(P)1Qwv將是一奇圈，矛盾。,容易證明：命題1圖G中2G中含圈。命題2簡單圖G，2G含長+1的圈。（提示：以上兩例中可考慮其最長路）命題3任一圖G中G含圈。證明：反證，假設(shè)結(jié)論不成立，而G為其最小反例。則首先G是連通的，且。再由以上第一例知，G中存在一頂點u，。于是，且顯然G-u中也不含圈，從而G-u也是個反例，但頂點數(shù)比G少，矛盾。,習(xí)題,1.6.1若邊e在G的一閉跡中，則e在G的一圈中。1.6.2證明：(a).G含圈。(b)*.+4G含兩個邊不重的圈。1.6.3證明：任一連通偶圖G=(X,Y)的2-劃分(X,Y)是唯一的。（提示

18、：不然，必有二頂點u,v，原屬同一部（例如，）X，而在另一種2-劃分則不然。）,1.6.4證明或反證：(1).G中有兩個不同的(u,v)路，則G中含一圈。(2).G中有一閉途徑，在則G中含一圈。(3).G中有一長為奇數(shù)的閉途徑，在則G中含一奇圈。1.6.5設(shè)圖G的頂點可用兩種顏色進行著色，使每個頂點都至少與兩個異色頂點鄰，則G中一定包含偶圈。1.6.6座位的教室中，不可能讓每個學(xué)生都作一上下左右移動，使每個人都換了座位。（提示：“座位圖”是一二部圖）,1.7最短路問題,賦權(quán)圖（weightedgraph）G(注：權(quán)1時即為上文中所提的圖。)權(quán)(weight)w(e)0.記號：w(H)=,HG.

19、路P的長=w(P)頂點u與v的距離d(u,v)=最短(u,v)-路的長。,問題求最短(u0,v0)-路。轉(zhuǎn)求最短(u0,v)-路,vVu0.簡化只考慮簡單圖，且w(e)0eE.（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)=minw(u0v)vu0者.得S1=S0u1,P1=u0u1.,(2).若已求得Sk-1;d(u0,u1)，d(u0,uk-1);及最短(u0,ui)路Pi，i=1.2,.,k-1。求uk：顯然，d(u0,uk)=mind(u0,v)v=d(u0,uj)+w(ujuk)某j1,2,，k-1=mind(u0,u)+w(uuk)uSk-1=mind(u0,u)+w(uv)uSk-1，v=minl(v)v其中，l(v)=mind(uo,u)+w(uv)uSk-1(l