圖論概念定理知識點梳理

1、圖論基本知識點梳理第一部分(基本概念)1.G連通的充分必要條件是0(G)=1?；蛉魘V(G)|=2k,且對VvV(G),有d(v)之k,則G是連通圖。4.圖G為二分圖當(dāng)且僅當(dāng)G中無奇圈。5.在僅兩個奇次頂點的圖中，此二奇次頂點連通。6.設(shè)G為簡單圖，若6(G)22,則G中有圈。7 .設(shè)G為簡單圖，若5(G)之3,則G中有偶圈。具體地，(1)單星妖怪中有偶圈。(2)在k正則圖G中，若k至3,則G中有偶圈。8.簡單圖G與其補圖Gc不能都不連通。29.在的三角剖分中，正常三角形為奇數(shù)個。10.以下等價(1)G是樹(無圈連通圖)。(2)G中任兩頂點間恰有一條軌。(3)G無圈，w=v1。(4)G是連通圖

2、，1。(5)G是連通圖，且對G的任意邊e,G-e不連通。(樹每邊皆割邊)(6)G無圈，且對任一不在E(G)的邊e,G+e恰含一個圈。11 .若G連通，則(G)v(G)-1oG的生成樹是G最小的連通生成子圖。12 .G是連通圖的充分必要條件是G有生成樹。13 .v2的樹 T T 至少有兩個葉。14.完全圖Kn的生成樹個數(shù)T(Kn)=nn。15 .圖G可平面嵌入的充分必要條件是G可以球面嵌入。(染地球上各國等價于染地圖上各國)16 .(Euler公式)G是連通平面圖，則Y-w+=2.17.證明：若G是v23的連通平面圖，則0O23單星妖怪的邊色數(shù)是4。24二分圖的邊色數(shù)等于圖的最大度。25 .簡單

3、圖G的邊色數(shù)(G)WS(G)d(G)+“。26 .M M 與N是圖G的無公共邊的匹配，且|M|N|,則存在無公共邊的匹配 M M與 N N , ,使得|M日M|-1,|N|=|N|+1,MN=MUN。27G是有邊二分圖的充要條件是7(G)=2。28 .G是無邊圖的充要條件是7(G)=1。29 .G是完全圖的充要條件是7(G)=|V(G)|。30.設(shè)Wn為輪圖，則有當(dāng)n為偶數(shù)時，X(Wn)=3,當(dāng)n為奇數(shù)時，(Wn)=4o31 .平面圖的色數(shù)不大于5。32.圖G的顏色多項式P(G,k)=k(k1)(kv+1)的充要條件是G=Kv。33圖G的顏色多項式P(G,k)=k的充要條件是|E(G)|=0。

4、34.圖G的顏色多項式P(G,k)是k的Y次多項式，n=|V(G)|,且降哥排列時，首項為kv,第二項為-水,，無常數(shù)項，系數(shù)是正負交替出現(xiàn)的整數(shù)，其中E=|E(G)|。35.圖G的顏色多項式P(G,k)滿足：P(Ge,K)=P(Ge,k)+P(G,k)。36 .圖G的顏色多項式P(G,k)=k(k1)W當(dāng)且僅當(dāng)G是v頂?shù)臉洹Ｈ魣DG的顏色多項式P(G,k)=k(k1)v;則G是連通圖，且w=v1。37 .I I 為G的獨立集的充要條件是V(G)-I是G的覆蓋集。38 .若I為G的極大獨立集，則V(G)-I是G的極小覆蓋集。39 .圖G的獨立數(shù)久(G)與覆蓋數(shù)P(G)滿足a(G)+P(G)=|V

5、(G)|。40.平凡的Ramsey數(shù)：r(1,l)=r(k,1)=1,r(2,l)=l,r(k,2)=k,r(k,l)=r(l,k)41 .關(guān)于二維Ramsey數(shù)，正確的是：r(3,3)=6,r(3,4)=9,r(3,5)=14,r(4,5)=25。42 .k與l是不小于2的自然數(shù)，則r(k,l)2,則Ramsey數(shù)r(k,l)EC：；/。kRamsey數(shù)r(k,k)不小于2244 .對于連通圖G,(1)G是Euler圖的充要條件是G無奇度點。(2)G是Euler圖的充要條彳是G可表示為無公共邊的圈之并。45 .連通圖G有Euler行跡當(dāng)且僅當(dāng)G中至多兩個奇度點。46 .若G的每頂皆偶度，則G

6、中無割邊。47 .G是Hamilton圖的必要條件是VS仁V(G),S#巾，有切(GS)E|S|,其中切(,)是連通分支數(shù)。48.設(shè)|V(G)戶3,G的任一對頂 u,vu,v 皆有d(u)+d(v)|V(G)|-1-1，則G有Hamilton軌；若d(u)+d(v)JV(G)|,則G是Hamilton圖。注：由“設(shè)|V(G)上3,G的任一對頂 u,vu,v 皆有d(u)+d(v)之|V(G)|11可得G為連通圖。49 .(1)階至少為3的完全圖是Hamilton圖。(2)完全偶圖Km,m(m至2)為Hamilton圖。50 .Kmm中有 1 1m ml l 個兩兩無公共邊的Hamilton圈。

7、251 .G是強連通有向圖當(dāng)且僅當(dāng)G存在有向生成回路。52 .當(dāng)且僅當(dāng)無向圖G是無橋連通圖時，G可定向成強連通有向圖。53 .G是單連通有向圖當(dāng)且僅當(dāng)G中有含G的一切頂?shù)挠邢虻缆贰?4 .競賽圖是定向的無向完全圖。55 .若有向圖的底圖為G,則此圖中有長為7(G)-1的有向軌。每個競賽圖皆有有向Hamilton軌。56 .G是無向圖，則可對G的邊定向，使得到的有向圖中的最長有向軌長(G)-1o57 .競賽圖中得分最多的頂為王。反之不成立。58 .n階競賽圖G有唯一王的充要條件是v得分n-1。59 .(泛圈定理)V至3的強連通競賽圖G的每個頂點都包含在有向k圈中，3k2,則G為Hamilton圖

8、。63 .Heawood定理平面圖的色數(shù)不超過5。64 .碳氫化合物中氫原子個數(shù)為偶數(shù)。65.大于7公斤的整公斤的重量都可以僅用一些3公斤和5公斤的兩種祛碼來稱量.67.各邊相異的道路稱為行跡.68.各頂相異的道路稱為軌道.69.圖G是二分圖當(dāng)且僅當(dāng)G中無奇圈.70.無零次與1次頂?shù)膯螆D中有圈.71 .設(shè)G是單圖，若6(G)3,則G中有偶圈.75 .、M2.：.v76.任取n個人組成的人群，n22,至少有兩位，他們在這個人群中的朋友一樣多.77 .G連通的必要條件是名(G)v(G)-1.82.設(shè)G為平面圖，59)=力/j,即是圖6的面集合，氏9)|=名，則d(fi)=2;.i183 .若G是v

9、23的平面圖，當(dāng)u,vWV(G),而uWE(G)時，G+uv不再是平面圖，則稱G是極大平面圖.84 .M M 是圖G的邊子集，且 M M 中任兩邊在G中不相鄰，則稱 M M 是G的一個匹配.85 .G中每個頂點皆被 M M 許配，則稱 M M 為G的完備匹配或完美匹配.86.設(shè) M M 是圖G中的匹配，G中的一條軌P(u,v),u,v未被 M M 許配，但P(u,v)上邊交替地不在 M M 中出現(xiàn)與在 M M 中出現(xiàn)，則稱P(u,v)為 M M 的可增廣軌.87 .無橋三次正則圖有完備匹配.88 .k次正則圖有完備匹配，kA0.89.匹配理論Berge定理 M M 是圖G中的最大匹配當(dāng)且僅當(dāng)G

10、無 M M 的可增廣軌.Hall定理設(shè)G是具有二分類(X,Y)的二分圖，存在將 X X 中頂皆許配的匹配的充分必要條件是VS=X,|N(S)mS|.其中N(S)是S中每個頂?shù)泥忢斀M成的S的鄰集.K?nig定理若G為二分圖，則其最大匹配的邊數(shù)為G的覆蓋數(shù)P(G).Tutte定理圖G由完備匹配當(dāng)且僅當(dāng)VSCV(G),O(G-S)R滿足(1)0f(e)c(e),eeE(G);f(e)=f(e),vwVs,t,其中覆(v)e：Xv)e：=|.：v)是以v為頭的邊的邊集，P(v)是以v為尾的邊的邊集。稱f為網(wǎng)絡(luò)N上的流函數(shù)。91 .設(shè)N(G,s,t,c(e)是定義在有向圖G上的網(wǎng)絡(luò)，f為網(wǎng)絡(luò)N上的流函數(shù)

11、，稱F一f(e)-f(e)e；(t)eq(t)為流函數(shù)f的流量。92.設(shè)N(G,s,t,c(e)是定義在有向圖G上的網(wǎng)絡(luò)，SuV(G),sS,tV(G)S,則稱C(S)=Zc(e)為截(S,S)的截量。e.(S,S)93.設(shè)N(G,s,t,c(e)是定義在有向圖G上的網(wǎng)絡(luò)，S=V(G),(S,S)為網(wǎng)絡(luò)的截，則網(wǎng)絡(luò)N上的流函數(shù)f的流量 F F 等于工f(e)-工f(e)。e.(S,S)e.(S,S)94.設(shè)N(G,s,t,c(e)是定義在有向圖G上的網(wǎng)絡(luò)，S=V(G),C(S)為(S,S)的截量，F(xiàn) F 為流函數(shù)的流量，則 F F 與C(S)滿足不等式FC(S)。95.設(shè)N(G,s,t,c(e

12、)是定義在有向圖G上的網(wǎng)絡(luò)，S=V(G),C(S)為(S,S)的截量，F(xiàn) F 為流函數(shù)的流量。若F=C(S)。則 F F 是網(wǎng)絡(luò)的最大流，C(S)是網(wǎng)絡(luò)的最小截量。96.設(shè)N(G,s,t,c(e)是定義在有向圖G上的網(wǎng)絡(luò)，(S,S)為網(wǎng)絡(luò)的截，f為網(wǎng)絡(luò)的流函數(shù)。則f是最大流，(S,S)是最小截的充分必要條件為F=C(S)。第二部分(算法及應(yīng)用)1、Kruskal算法的基本步驟及應(yīng)用。設(shè)G是連通加權(quán)圖，求G的最優(yōu)樹.(1)從E(G)中選一條權(quán)最小的邊e1.(2)若e,e2,，e已選出，則從E(G)e,e2,，e中選e書,使得(a)Ge,q,，e,e書中無圈，(b)w(e+)=min.(3)反復(fù)執(zhí)

13、行上述過程直至選出e止.2. huffman算法的基本步驟為：a(1)初始：令S=WI,W2,，wt;(2)從S中取出兩個權(quán)值最小者w與w,畫結(jié)點Vi,帶權(quán)w，畫結(jié)點Vj,帶權(quán)Wj,畫Vi與Vj的父親V,連接Vi與V,連接Vj與V,令V帶權(quán)W1十w2;令S=(S-w1,w2)=w+也;(4)判斷S只含一個元素，若是，停止，否則轉(zhuǎn)2).3. dijkstra算法(見課本)4、設(shè)G=Kn,n為加權(quán)完全二分圖，且具有二分類(X,Y)。求G的最佳匹配的KM算法的步驟如下：(1)選定初始定標(biāo)l,構(gòu)造相等子圖Gl,在Gl取定初始匹配M。(2)若X中頂皆被 M M 許配，止。M M 即為所求的最佳匹配；否則取Gl中未被 M M 許配的頂U,令S=u,T=弧若NGl(S)nT,轉(zhuǎn)(4),若NGl(S)=T,取%=xm%a(