資源描述：
《圖論及其應(yīng)用.doc》由會員上傳分享，免費在線閱讀，更多相關(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，selfl
2、oop）：如邊l。棱（link）：如邊ae。重邊：如邊p及邊q。簡單圖：（simplegraph）無環(huán)，無重邊平凡圖：僅有一個頂點的圖（可有多條環(huán)）。一條邊的端點：它的兩個頂點。記號：。習(xí)題1.1.1若G為簡單圖，則。1.1.2n(34)個人中，若每4人中一定有一人認識其他3人，則一定有一人認識其他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
3、。注往往將同構(gòu)慨念引伸到非標號圖中，以表達兩個圖在結(jié)構(gòu)上是否相同。58注判定兩個圖是否同構(gòu)是NP-hard問題。完全圖(completegraph)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-部圖
8、等。例。用標號法判定二部圖。習(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證明兩個簡單圖G和H同構(gòu)?存在一一映射f:V(G)?V(H)，使得uv?E(G)當且僅當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).
9、e(Tm,n)=其中k=[n/m].(b)*.對任意的n頂點完全m-部圖G，一定有e(G)￡e(Tm,n)，且僅當G@Tm,n時等式才成立。1.2.7所謂k-方體是這樣的圖：其頂點是由0與1組成的有序k-元組，其二頂點相鄰當且僅當它們恰有一個坐標不同。證明k-方體有個頂點，k*2k-1條邊，且是一偶圖。581.2.8簡單圖G的補圖Gc是指和G有相同頂點集V的一個簡單圖，在Gc中兩個頂點相鄰當且僅當它們在G不相鄰。(a).畫出Kcn和Kcm,n。(b).如果G@Gc則稱簡單圖G為自補的。證明：若G是自補
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=頂點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）。生成子圖（spanningsubg.）?HíG且V(H)=V(G)。生成母圖?；A(chǔ)簡單圖（underlyingsimpleg.）。導(dǎo)出子圖（inducedsubg.）G[
11、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[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’雖有相同的邊集，但兩者不一定相等：后者一定是生成子圖，而前者則不然。上述四種運算是最基本取子圖運算，今后老要遇到，一定要認真掌握好。關(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)=?)邊
