圖論重要結論

本文格式為Word版，下載可任意編輯——圖論重要結論v??d(v)?2mV(G)定理1：圖G=(V,E)中所有頂點的度的和等于邊數m的2倍，即：推論1在任何圖中，奇點個數為偶數。推論2正則圖的階數和度數不同時為奇數。

定理2若n階簡單圖G不包含Kl+1，則G度弱于某個完全l部圖H，且若G具有與H一致的度序列，則:G?H定理3設T是(n,m)樹，則：m?n?1偶圖判定定理:定理4圖G是偶圖當且僅當G中沒有奇回路。敏格爾定理:定理5(1)設x與y是圖G中的兩個不相鄰點，則G中分開點x與y的最小點數等于獨立的(x,y)路的最大數目；(2)設x與y是圖G中的兩個不相鄰點，則G中分開點x與y的最小邊數等于G中邊不重的(x,y)路的最大數目。

歐拉圖、歐拉跡的判定:定理6以下陳述對于非平凡連通圖G是等價的：(1)G是歐拉圖；(2)G的頂點度數為偶數；(3)G的邊集合能劃分為圈。

推論：連通非歐拉圖G存在歐拉跡當且僅當G中只有兩個頂點度數為奇數。

H圖的判定:定理7(必要條件)若G為H圖，則對V(G)的任一非空頂點子集S，有：?(G?S)?S定理8(充分條件)對于n≧3的單圖G，假使G中有：?(G)?n定理9(充分條件)對于n≧3的單圖G，假使G中的任意兩個不相2鄰頂點u與v，有：d(u)?d(v)?n定理10(幫迪——閉包定理)圖G是H圖當且僅當它的閉包是H圖。

定理11(Chvátal——度序列判定法)設簡單圖G的度序列是(d1,d2,…,dn),這里，d1≦d2≦…≦dn,并且n≧3.若對任意的mm,或者dn-m≧n-m,則G是H圖。定理12設G是n階單圖。若n≧3且E(G)???n?1??2???1則G是H圖；并且，具有n個頂點?n?1?條邊的非H圖只有C1,n以及C2,5.

??2??1?定理13(Hall定理）設G=(X,Y)是偶圖，則G存在飽和X每個頂點的匹配的充要條件是：對?S?X,有N(S)?S(*)推論：若G是k(k>0)正則偶圖，則G存在完美匹配。定理14(哥尼，1931)在偶圖中，最大匹配的邊數等于最小覆蓋的頂點數。定理15K2n可一因子分解。定理16具有H圈的三正則圖可一因子分解。定理17K2n+1可2因子分解。

定理18K2n可分解為一個1因子和n-1個2因子之和。

定理19每個沒有割邊的3正則圖是一個1因子和1個2因子問題可模型為一個偶圖。

之和。若n為偶數，且δ(G)≥n/2+1,則n階圖G有3因子一節(jié)課對應邊正常著色的一個色組。由于G是偶圖，所以邊色數定理20設G=(n,m)是平面圖，則：?deg(f)?2m為G的最大度35。這樣，最少總課時為35節(jié)課。平均每天要安排

f??n?m???27節(jié)課。假使每天安排8節(jié)課，由于G的總邊數為240，所定理21(歐拉公式)設G=(n,m)是連通平面圖，ф是G的面數，則：以需要的教室數為240/40=6。

推論1設G是具有n個點m條邊ф?zhèn)€面的連通平面圖，假使對G定理5一個n階圖G相和它的補圖有一致的頻序列。

的每個面f,有：deg(f)≥l≥3,則：m?ll?2(n?2)邊不重復的途徑稱為跡；點不重復的途徑稱為路。顯然路

推論2設G是具有n個點m條邊ф?zhèn)€面的簡單平面圖，則：m?3n?必為跡。6推論3設G是具有n個點m條邊的簡單平面圖，則：??5圖G的直徑定義為d(G)=max{d(u,v)|u,v∈V}

定理22平面圖G的對偶圖必然連通.

證明：若δ≥2，則G中必然含有圈。證明：只就連通圖證明定理23設G是至少有3個頂點的平面圖，則G是極大平面圖，即可！設W=v1v2…..vk-1vk是G中的一條最長路。由于δ≥2，所當且僅當G的每個面的次數是3且為單圖。以vk必然有相異于vk-1的鄰接頂點。又W是G中最長路。

??(Km,n)??所以，這樣的鄰接點必然是v1,v2,….,vk-2中之一。設該點為定理25(哥尼，1916)若G是偶圖，則??(G)??vm，則vmvm+1….vkvm為G中圈。

定理26(維津定理，1964)若G是單圖，則：??(G)??或??(G)??+1設G是具有m條邊的n階單圖，證明：若G的直徑為2且Δ定理27設G是單圖且Δ(G)>0。若G中只有一個最大度點或恰有(G)=n-2,則m≥2n-4.證明：設d(v)=Δ=n-2,且設v的鄰接點為兩個相鄰的最大度點，則：??(G)??(G)v1,v2,…,vn-2.u是剩下的一個頂點。由于d(G)=2且u不能和v鄰

定理28設G是單圖。若點數n=2k+1且邊數m>kΔ,則：??(G)??(G接，所以)?1u必需和v1,v2…,vn-2中每個頂點鄰接。

定理29設G是奇數階Δ正則單圖,若Δ>0,則：??(G)??(G)?1否則有d(G)>2.于是得：m≥2n-4.

定理31(布魯克斯，1941)若G是連通的單圖，并且它既不是奇圈，定理8一個圖是偶圖當且當它不包含奇圈。

又不是完全圖，則：?(G)??(G)證明設G是具有二分類（X,Y）的偶圖，并且C=v0v1…vkv0定理32在完全m元樹T中，若樹葉數為t,分支點數為(i,m則：?1)

i?t?是1G的一個圈。不失一般性，可假定v0∈X。這樣，v2i∈X，)根樹:一棵非平凡的有向樹T，假使恰有一個頂點的入度為0，而且v2i+1∈Y。又由于v0∈X，所以vk∈Y。由此即得C是其余所有頂點的入度為1，這樣的的有向樹稱為根樹。其中入度為偶圈。顯然僅對連通圖證明其逆命題就夠了。設G是不包含奇圈0的點稱為樹根，出度為0的點稱為樹葉，入度為1，出度大于1的連通圖。任選一個頂點u且定義V的一個分類（X,Y）如下：

的點稱為內點。又將內點和樹根統(tǒng)稱為分支點。

X={x|d(u,x)是偶數，x∈V(G)}

敏格爾定理:定理5(1)設x與y是圖G中的兩個不相鄰點，則Y={y|d(u,y)是奇數，y∈V(G)}現在證明（X,Y）是G的一G中分開點x與y的最小點數等于獨立的(x,y)路的最大數目；2)設個二分類。假設v和w是X的兩個頂點，P是最短的（u,v）x與y是圖G中的兩個不相鄰點，則G中分開點x與y的最小邊數路，Q是最短的（u,w）路，以u1記P和Q的最終一個公共頂點。等于G中邊不重的(x,y)路的最大數目。

因P和Q是最短路，P和Q二者的（u1,u）節(jié)也是最短的路，故例2(排課表問題)在一個學校中，有7個教師12個班級。在長一致?，F因P和Q的長都是偶數，所以P的（u1,v）節(jié)P1和Q每周5天教學日條件下，教課的要求由如下矩陣給出：

的（u1,w）節(jié)Q1必有一致的奇偶性。由此推出路（v,w）長為偶??323333333333?數。若v和w相連，則就是一個奇圈，與假設矛?136042513304???05500505055?P??5盾，故X中任意兩個頂點均不相鄰。

?242424242423????352203144325??550055050550?設A為4圈C4的鄰接矩陣，求A的譜。所以A的特征值為-2,

???034343434330??基本回路是點不重復，簡單回來，邊不重

0,2;其重數依次記為1,2,1。故SpecA=???202??121??1設G是具有n個點m條邊的圖，則以下關于樹的命題等價。（1）G是樹。（2）G中任意兩個不同點之間存在唯一的路。（3）G連通，刪去任一邊便不連通（4）G連通，且m=n-1。5）G無圈，且m=n-1。（6）G無圈，添加任一條邊可得唯一的圈。

?(G)??(G?e)??(G?e)

定義2設T是圖G=(V,E)的一棵生成樹，m和n分別是G的邊數與頂點數，e1,e2,…,em-n+1為T的弦，設Cr是T加er產生的圈，r=1,2,…,m-n+1,稱Cr為對應于弦er的基本回路，稱｛C1,C2,…,Cm-n+1｝為對應于生成樹T的基本回路系統(tǒng)。

定理8連通圖G的任一回路均可表示成若干個基本回路的對稱差。

(1)若ω(G-v)＞ω(G),則v必為G的割點；(2)若G無環(huán)且非平凡

，

則

v

是

G

的

割

點

當

且

僅

當ω(G-v)＞ω(G)定理3設v是無環(huán)連通圖G的一個頂點，則v是G的割點當且僅當V(G-v)可劃分為兩個非空頂點子集V1與V2，使x∈V1，y∈V2，點v都在每一條(x,y)路上。若e是圖G的割邊或e是一個環(huán)，則G[{e}]是G的塊；G的僅含一個點的塊或是孤立點,或是環(huán)導出的子圖；至少兩個點的塊無環(huán)，至少三個點的塊無割邊。

定理4設圖G的階至少為3，則G是塊當且僅當G無環(huán)并且任意兩點都位于同一個圈上。

推論設G的階至少為3，則G是塊當且僅當G無孤立點且任意兩

條邊都在同一個圈上。定理5點v是圖G的割點當且僅當v至少屬于G的兩個不同的塊。

圖G是2邊連通的當且僅當G連通、無割邊且至少含有兩個點。引理1設G是n階簡單圖，若δ(G)≥n/2則G必連通。定理8設G是n階簡單圖，對正整數km,或有dn-m≧n-m,則G是H圖。

證明：若n為偶數，且δ(G)≥n/2+1,則n階圖G有3因子。證明：因δ(G)≥n/2+1,由狄拉克定理：n階圖G有H圈C.又因n為偶數，所以C為偶圈。于是由C可得到G的兩個1因子。設其中一個為F1?？紤]G1=G-F1。則δ(G1)≥n/2。于是G1中有H圈C1.作H=C1∪F1。顯然H是G的一個3因子證明K5和K3,3是不可平面圖。

引理設G是極大平面圖，則G必連通；若G的點數n≥3，則G無割邊。（1）若G不連通，則G至少存在兩個連通分支G1與G2。顯然G1與G2也是平面圖。將G2畫在G1的外部面內，并分別在G1與G2的外部面上各取一個點u和v。很明顯，u與v不相鄰。連接u和v，記所得的圖為G*。易知G*也是平面圖，這與G是極大平面圖矛盾，所以G連通。推論設G是一個有n個點m條邊ф?zhèn)€面的極大平面圖，n≥3，則（1）m=3n-6；（2）ф=2n-4。

定理12設G*是平面圖G的對偶圖，則G*必連通。)同構的平

面圖可以有不同構的對偶圖.對于3階以上的具有m條邊的單圖G來說，假使G滿足如下條件之一：