圖論及其應(yīng)用.doc

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

1、圖和子圖圖和簡(jiǎn)單圖圖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)（代表），它們有無(wú)窮多個(gè)。真正的圖G是上面所給出式子，它與頂點(diǎn)的位置、邊的形狀等無(wú)關(guān)。不過(guò)今后對(duì)兩者將經(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，selfl

2、oop）：如邊l。棱（link）：如邊ae。重邊：如邊p及邊q。簡(jiǎn)單圖：（simplegraph）無(wú)環(huán)，無(wú)重邊平凡圖：僅有一個(gè)頂點(diǎn)的圖（可有多條環(huán)）。一條邊的端點(diǎn)：它的兩個(gè)頂點(diǎn)。記號(hào)：。習(xí)題1.1.1若G為簡(jiǎn)單圖，則。1.1.2n(34)個(gè)人中，若每4人中一定有一人認(rèn)識(shí)其他3人，則一定有一人認(rèn)識(shí)其他n-1人。同構(gòu)在下圖中，圖G恒等于圖H,記為G=H?V（G)=V(H),E(G)=E(H)。圖G同構(gòu)于圖F?V(G)與V(F),E(G)與E(F)之間各存在一一對(duì)應(yīng)關(guān)系，且這二對(duì)應(yīng)關(guān)系保持關(guān)聯(lián)關(guān)系。記為GF

3、。注往往將同構(gòu)慨念引伸到非標(biāo)號(hào)圖中，以表達(dá)兩個(gè)圖在結(jié)構(gòu)上是否相同。58注判定兩個(gè)圖是否同構(gòu)是NP-hard問(wèn)題。完全圖(completegraph)Kn空?qǐng)D（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之間的每對(duì)頂點(diǎn)都相鄰，且

4、X

5、=m,

6、Y

7、=n。類似地可定義，完全三部圖（例如Km,n,p），完全n-部圖

8、等。例。用標(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è)簡(jiǎn)單圖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).對(duì)簡(jiǎn)單二部圖有e￡n2/4.1.2.6記Tm,n為這樣的一個(gè)完全m-部圖：其頂點(diǎn)數(shù)為n，每個(gè)部分的頂點(diǎn)數(shù)為[n/m]或{n/m}個(gè)。證明：(a).

9、e(Tm,n)=其中k=[n/m].(b)*.對(duì)任意的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條邊，且是一偶圖。581.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).如果G@Gc則稱簡(jiǎn)單圖G為自補(bǔ)的。證明：若G是自補(bǔ)

10、的，則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ǔ)簡(jiǎn)單圖（underlyingsimpleg.）。導(dǎo)出子圖（inducedsubg.）G[

11、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í)，對(duì)應(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,

12、g}.(1G[E{a,e,f,g}])注意G[EE’]與G-E’雖有相同的邊集，但兩者不一定相等：后者一定是生成子圖，而前者則不然。上述四種運(yùn)算是最基本取子圖運(yùn)算，今后老要遇到，一定要認(rèn)真掌握好。關(guān)于子圖的一些定義還有：G+E’?往G上加新邊集E’所得的（G的母）圖。為簡(jiǎn)單計(jì)，今后將G±{e}簡(jiǎn)計(jì)為G±e；G-{v}簡(jiǎn)計(jì)為G-v。設(shè)G1,G2íG，稱G1與G2為不相交的（disjiont）?V(G1)?V(G2)=?(E(G1)?E(G2)=?)邊