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

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

1、圖和子圖圖和簡單圖圖G=(V,E)，其中V={}V---頂點集，---頂點數(shù)E={}E---邊集，---邊數(shù)例。左圖中，V={a,b,......,f},E={p,q,ae,af,......,ce,cf}注意，左圖僅僅是圖G的幾何實現(xiàn)（代表），它們有無窮多個。真正的圖G是上面所給出式子，它與頂點的位置、邊的形狀等無關(guān)。不過今后對兩者將經(jīng)常不加以區(qū)別。稱邊ad與頂點a(及d)相關(guān)聯(lián)。也稱頂點b(及f)與邊bf相關(guān)聯(lián)。稱頂點a與e相鄰。稱有公共端點的一些邊彼此相鄰，例如p與af。環(huán)（loop，selfloop）：如邊l。棱（link）：如邊ae。重邊：如邊p及邊q。簡單

2、圖：（simplegraph）無環(huán)，無重邊平凡圖：僅有一個頂點的圖（可有多條環(huán)）。一條邊的端點：它的兩個頂點。記號：。習(xí)題1.1.1若G為簡單圖，則。1.1.2n(34)個人中，若每4人中一定有一人認(rèn)識其他3人，則一定有一人認(rèn)識其他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)之間各存在一一對應(yīng)關(guān)系，且這二對應(yīng)關(guān)系保持關(guān)聯(lián)關(guān)系。記為GF。注往往將同構(gòu)慨念引伸到非標(biāo)號圖中，以表達兩個圖在結(jié)構(gòu)上是否相同。58注判定兩個圖是否同構(gòu)是NP-hard問題。完全圖(complete

3、graph)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之間的每對頂點都相鄰，且

4、X

5、=m,

6、Y

7、=n。類似地可定義，完全三部圖（例如Km,n,p），完全n-部圖等。例。用標(biāo)號法判定二部圖。習(xí)題1.2.1G@HTn(G)=n(H),e(G)=e(H)。并證明其逆命題不成立。1..2.2證明下面兩個圖不同構(gòu)：1.2.3證明下面兩個圖是同構(gòu)的：1.2.4證明兩個簡單圖

8、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為這樣的一個完全m-部圖：其頂點數(shù)為n，每個部分的頂點數(shù)為[n/m]或{n/m}個。證明：(a).e(Tm,n)=其中k=[n/m].(b)*.對任意的n頂點完全m-部圖G，一定有e(G)￡e(Tm,n)，且僅當(dāng)G@Tm,n時等式才成立。1.2.7所謂k-方體是這樣的圖：其頂點是由0與1組成的有序k-元組，其二頂點相鄰當(dāng)且僅當(dāng)它們恰有一個坐標(biāo)不同。證明k-方體有個頂點

9、，k*2k-1條邊，且是一偶圖。581.2.8簡單圖G的補圖Gc是指和G有相同頂點集V的一個簡單圖，在Gc中兩個頂點相鄰當(dāng)且僅當(dāng)它們在G不相鄰。(a).畫出Kcn和Kcm,n。(b).如果G@Gc則稱簡單圖G為自補的。證明：若G是自補的，則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=頂點vi與邊ej的關(guān)聯(lián)次數(shù)=0,1,2.ai,j=連接頂點vi與vj的邊數(shù)。例。子圖子圖(subgraph)HíG?V(H)íV(G),E(H)íE(G)。真子圖HìG。母圖（supergraph）。生成

10、子圖（spanningsubg.）?HíG且V(H)=V(G)。生成母圖?；A(chǔ)簡單圖（underlyingsimpleg.）。導(dǎo)出子圖（inducedsubg.）G[V’],(非空V’íV)?以V’為頂點集，以G中兩端都在V’上的邊全體為邊集構(gòu)成的G的子圖。邊導(dǎo)出子圖G[E’]非空E’íE?以E’為邊集，以E’中所有邊的端點為頂點集的的子圖。例。58以上兩種子圖，其實，對應(yīng)于取子圖的兩種基本運算。下面是取子圖的另兩種基本運算：G-V’?去掉V’及與V’相關(guān)聯(lián)的一切邊所得的剩余子圖。?即G[VV’]G-E’?從中去掉E’后所得的生成子圖例。G-{b,d,g},(=G[

11、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’雖有相同的邊集，但兩者不一定相等：后者一定是生成子圖，而前者則不然。上述四種運算是最基本取子圖運算，今后老要遇到，一定要認(rèn)真掌握好。關(guān)于子圖的一些定義還有：G+E’?往G上加新邊集E’所得的（G的母）圖。為簡單計，今后將G±{e}簡計為G±e；G-{v}簡計為G-v。設(shè)G1,G2íG，稱G1與G2為不相交的（disjiont）?V(G1)?V(G2)=?(E(G1)?E(G2)=?)邊