第1章-圖和子圖.ppt

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

2、稱邊ad與頂點(diǎn)a(及d)相關(guān)聯(lián)(incident)。也稱頂點(diǎn)b(及f)與邊bf相關(guān)聯(lián)。稱頂點(diǎn)a與e相鄰(adjacent)。也稱有公共端點(diǎn)的一些邊，例如p與af彼此相鄰。稱一條邊的兩個(gè)頂點(diǎn)為它的兩個(gè)端點(diǎn)環(huán)（loop，selfloop）：如邊k，它的兩個(gè)端點(diǎn)相同。棱（link）：如邊ae，它的兩個(gè)端點(diǎn)不相同。重邊：如邊p及邊q。簡(jiǎn)單圖：（simplegraph）無(wú)環(huán)，無(wú)重邊平凡圖：僅有一個(gè)頂點(diǎn)的圖。注意：任何一圖都有V。記號(hào)：（,）,例題1.1若G為簡(jiǎn)單圖，則。1.2若一群人中，凡相識(shí)的兩人都無(wú)公共朋友，凡不相識(shí)的兩人都恰有兩個(gè)公共朋友，則每人的朋友數(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è)圖同構(gòu)是指”它們有相同的結(jié)構(gòu)”，僅在頂點(diǎn)及邊的標(biāo)號(hào)上或兩個(gè)圖的畫(huà)法上有所不同而已。往往將同構(gòu)慨念引伸到非標(biāo)號(hào)圖中，以表達(dá)兩個(gè)圖在結(jié)構(gòu)上是否相同。注判定兩個(gè)圖是否同構(gòu)是個(gè)未解決的困難問(wèn)題（openproblem）。,完全圖(completegraph)Kn空?qǐng)D（emptyg.）E=。V(V)為獨(dú)立集V中任二頂點(diǎn)都互不相鄰。二部圖（偶圖，bipartiteg.）G=(X,Y;E)存在V(G)的一個(gè)2-劃分(X,Y)（即

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

5、(H)。并證明其逆命題不成立。1.2.2證明下面兩個(gè)圖不同構(gòu)：,1.2.3證明下面圖1與圖2是同構(gòu)的；而圖1與圖3是不同構(gòu)的：1.2.4證明兩個(gè)簡(jiǎn)單圖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).對(duì)簡(jiǎn)單二部圖有2/4.1.2.6記Tm,n為這樣的一個(gè)完全m-部圖：其頂點(diǎn)數(shù)為n，每個(gè)部分的頂點(diǎn)數(shù)為n/m或n/m個(gè)。證明：(a).(Tm,n)=其中k=n/m.(b)*.對(duì)任意的n頂點(diǎn)完全m-部圖G，一定有(G)(Tm,n)，且僅當(dāng)GTm,n時(shí)等式才成立。1.2.7所謂k-方體是這樣的圖：其頂點(diǎn)是由

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

7、連接頂點(diǎn)vi與vj的邊數(shù)。（鄰接矩陣）,頂點(diǎn)v的度dG(v)=G中與頂點(diǎn)v相關(guān)聯(lián)邊數(shù)。（每一環(huán)記為2）記號(hào)：最大、最小度，。（(G),(G)）奇點(diǎn)：度為奇數(shù)的頂點(diǎn)；偶點(diǎn)：度為偶數(shù)的頂點(diǎn)；孤立點(diǎn)：度為0的頂點(diǎn)；懸掛點(diǎn)：度為1的頂點(diǎn)；懸掛邊：懸掛點(diǎn)的關(guān)聯(lián)邊。,定理1.3.1(handshakinglemma)任一圖中，推論1.1任一圖中，度為奇數(shù)頂點(diǎn)的個(gè)數(shù)為偶數(shù)。,例：任一多面體中，邊數(shù)為奇數(shù)的外表面的數(shù)目為偶數(shù)。（提示：作一圖，其頂點(diǎn)對(duì)應(yīng)于多面體的面，且二頂點(diǎn)相鄰當(dāng)且僅當(dāng)對(duì)應(yīng)的兩個(gè)面相鄰（即有公共邊界）。）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的度序列。證明：非負(fù)整數(shù)序列(d1,d2,dn)為某一圖的度序列是偶數(shù)。1.3.5證明：任一無(wú)環(huán)圖G都包含一偶生成子圖H，使得dH(v)dG(v)/2對(duì)所有vV成立。（提示：考慮G的邊數(shù)最多的偶生成子圖）1.3.6*設(shè)平面上有n個(gè)點(diǎn)，其中任二點(diǎn)間的距離1，證明：最多有3n對(duì)點(diǎn)的距離=1。,1.4子圖,子圖(subgraph)HGV(H)V(G),E(H)E(G)。真子圖HGHG且HG。母圖（supergraph）。生成子圖（s

9、panningsubg.）HHG且V(H)=V(G)。生成母圖?；A(chǔ)簡(jiǎn)單圖（underlyingsimpleg.）：從一圖中去掉其所有重邊及環(huán)后所得的剩余（簡(jiǎn)單圖）圖稱之為其基礎(chǔ)簡(jiǎn)單圖。導(dǎo)出子圖（inducedsubgraph.）GV，(非空VV)以V為頂點(diǎn)集，以G中兩端都在V上的邊全體為邊集構(gòu)成的G的子圖邊導(dǎo)出子圖GE(非空EE)以E為邊集，以E中所有邊的端點(diǎn)為頂點(diǎn)集的的子圖。,GV,GE兩種子圖對(duì)應(yīng)于取子圖的兩種基本運(yùn)算。下面是取子圖的另兩種基本運(yùn)算：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雖有相同的邊集，但兩者不一定相等：后者一定是生成子圖，而前者則不然。,上述四種運(yùn)算是最基本的取子圖運(yùn)算，今后經(jīng)常會(huì)遇到，一定要認(rèn)真掌握好。關(guān)于子圖的另一些定義還有：G+E往G上加新邊集E所得的（G的）母圖。為簡(jiǎn)單計(jì)，今后將Ge簡(jiǎn)記為Ge；G-v簡(jiǎn)記為G-v。設(shè)G1,G2G，稱G1與G2為不相交的（disjiont）V(G1)V(G2)=(E(G1)E(G2)=)邊不相交（edge-distjiont，邊不重的）E(G1)E(G2)=。（但這時(shí)G1與G2仍可能為相交的）。并圖G1G2,當(dāng)不相交時(shí)可簡(jiǎn)記為G

11、1+G2.交圖G1G2.,習(xí)題,1.4.1證明：完全圖的每個(gè)導(dǎo)出子圖是完全圖；偶圖的每個(gè)導(dǎo)出子圖是偶圖。1.4.2*設(shè)G為一簡(jiǎn)單圖，1n-1。證明：若4，且G中每個(gè)n頂點(diǎn)的導(dǎo)出子圖均有相同的邊數(shù)，則GK或Kc。,1.5路和連通性,途徑（walk）例如圖G的(u,x)-途徑W=ueyfvgyhwbvgydxdydx(有限非空序列)=uyvywvyxyx(簡(jiǎn)寫法-當(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)。）長(zhǎng)邊數(shù)（重復(fù)計(jì)算）。節(jié)（段，section）。例如W的(y,w)-節(jié)=yvw

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

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

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

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

16、），2-圈(由兩條重邊組成)，3-圈（又稱三角形）。,定理1.2G為二部圖G不含奇圈。,證明：設(shè)G的2-劃分為（X,Y），由G的定義，G的任一圈中，X和Y的頂點(diǎn)一定交錯(cuò)出現(xiàn)，從而其長(zhǎng)必為偶數(shù)。：不妨設(shè)G為連通的。任取一頂點(diǎn)u,令X=xVd(u,x)=偶數(shù),Y=yVd(u,y)=奇數(shù)。易見(jiàn)，(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é)的長(zhǎng)相

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

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

19、路P的長(zhǎng)=w(P)頂點(diǎn)u與v的距離d(u,v)=最短(u,v)-路的長(zhǎng)。,問(wèn)題求最短(u0,v0)-路。轉(zhuǎn)求最短(u0,v)-路,vVu0.簡(jiǎn)化只考慮簡(jiǎn)單圖，且w(e)0eE.（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)=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