二編圖論課件

1、第二編 圖論 圖論Graph Theory是數(shù)學(xué)的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個事物間具有這種關(guān)系。 圖論本身是應(yīng)用數(shù)學(xué)的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨(dú)立地建立過。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中，他所考慮的原始問題有很強(qiáng)的實(shí)際背景。 1 Peking University圖論簡介圖論起源于著名的七橋問題。A、B、C，D表示陸地。問題是要從這四塊陸地中任何一塊開始，通過每一座橋正好一次，再回到起點(diǎn)。然而無數(shù)次的嘗試都沒有

2、成功。歐拉在1736年解決了這個問題，他用抽象分析法將這個問題化為第一個圖論問題：即把每一塊陸地用一個點(diǎn)來代替，每一座橋用相應(yīng)兩點(diǎn)的一條線來代替，從而相當(dāng)于得到一個圖。歐拉證明了這個問題沒有解，并且推廣了這個問題，給出了對于一個給定的圖可以某種方式走遍的判定法則。這項工作使歐拉成為圖論及拓?fù)鋵W(xué)的創(chuàng)始人。 2 Peking University第7章 圖7.1 圖的基本概念7.2 通路與回路7.3 無向圖的連通性7.4 無向圖的連通度7.5 有向圖的連通性3 Peking University無序積無序積: A,B為兩個集合，稱 (a,b) |aAbB為A與B的無序積，記作A&B允許 a = b

3、 無序?qū)? (a,b)=(b,a)4 Peking University有向圖(directed graph)有向圖(digraph): 是一個有序二元組,記作D (1)頂點(diǎn)集V, 結(jié)點(diǎn)/頂點(diǎn)(vertex / node) (2)邊集, E是卡氏積VV的多重子集, 邊(edge / link / arc)6 Peking University例: G=,V=a,b,c,d,e, E=(a,a),(a,b),(a,b),(b,c),(c,d),(b,d).abcde例：無向圖7 Peking University表示方法圖G：V(G), E(G)分別表示圖G的頂點(diǎn)集和邊集圖D：V(D)，E(D)

4、|V(G)|, |E(G)|, |V(D)|, |E(D)|分別表示G和D的頂點(diǎn)數(shù)和邊數(shù)9 Peking Universityn階圖(有向圖): 若|V(G)|=n 或|V(D)|=n有限圖：若|V(G)|和|E(G)|均為有限數(shù)零圖(null graph): E=, n階零圖: |V(G)|=n, Nn 平凡圖(trival graph): 1階零圖, N1空圖(empty graph): V=E=, 圖定義中規(guī)定頂點(diǎn)集非空，由于圖的運(yùn)算中，可能產(chǎn)生點(diǎn)集為空集的運(yùn)算結(jié)果10 Peking University標(biāo)定圖,非標(biāo)定圖,基圖標(biāo)定圖(labeled graph): 頂點(diǎn)或邊標(biāo)定字母非標(biāo)定

5、圖(unlabeled graph): 頂點(diǎn)或邊不標(biāo)定字母基圖(底圖ground graph): 有向圖各邊的箭頭都去掉，所得圖為無向圖abcd11 Peking University關(guān)聯(lián)(incident)關(guān)聯(lián)(incident):圖G中, 邊ek=(vivj), ek與vi(ek與vi)彼此關(guān)聯(lián) （點(diǎn)與邊）關(guān)聯(lián)次數(shù): 若vivj ,稱ek與vi(ek與vi)關(guān)聯(lián)次數(shù)為1; 若vi=vj ,關(guān)聯(lián)次數(shù)為2環(huán)(loop):只與一個頂點(diǎn)關(guān)聯(lián)的邊孤立點(diǎn)(isolated vertex):無邊關(guān)聯(lián)的點(diǎn)viekvjviek12 Peking University相鄰(adjacent)相鄰(鄰接) :G

6、, 任意兩頂點(diǎn)vivj,存在邊ek, ek=(vi,vj) ,稱vi,vj彼此相鄰 (點(diǎn)與點(diǎn))任意兩邊ek,el,至少存在一個公共端點(diǎn),稱ek,el彼此相鄰（邊與邊）鄰接到,鄰接于: 有向圖D, ek=, vi鄰接到vj, vj鄰接于vi平行邊(parallel edge):端點(diǎn)相同的兩條無向邊是平行邊起點(diǎn)與終點(diǎn)相同的兩條有向邊是平行邊vivj13 Peking University鄰域(neighborhood)鄰域: NG(v)=u|uV(G)(u,v)E(G)uv為v的鄰域（v在圖G中的相鄰頂點(diǎn)）閉(closed)鄰域: 關(guān)聯(lián)集: IG(v) = e | e與v關(guān)聯(lián) 后繼:D+(v)=u

7、|uV(D)E(D)uv前驅(qū):D-(v)=u|uV(D)E(D)uv鄰域: ND(v)=D+(v)D-(v)閉鄰域: 14 Peking University最大(出/入)度,最小(出/入)度最大度: (G) = max dG(v) | vV(G) 最小度: (G) = min dG(v) | vV(G) 最大出度: +(D) = max dD+(v) | vV(D) 最小出度: +(D) = min dD+(v) | vV(D) 最大入度: -(D) = max dD-(v) | vV(D) 最小入度: -(D) = min dD-(v) | vV(D) 簡記為 , , +, +, -, -

8、16 Peking University03340,02,12,2=0=4+ = 2, +=0- =2, - = 017 Peking University定理2:設(shè)D=是有向圖, V=v1,v2,vn, |E|=m, 則d+(v1)+d+(v2)+d+(vn) = d-(v1)+d-(v2) +d-(vn) = m. #d+, d-19 Peking University推論:任何圖中,奇數(shù)度頂點(diǎn)的個數(shù)是偶數(shù). #證明：分為奇數(shù)度頂點(diǎn)集合V1和偶數(shù)度頂點(diǎn)集合V220 Peking University簡單圖(simple graph)簡單圖(simple graph): 無環(huán),無平行邊若G是

9、簡單圖, 則 0 (G) n-121 Peking University度數(shù)列度數(shù)列: 設(shè)G=,V=v1,v2,vn, 稱 d = ( d(v1),d(v2), d(vn) )為G的度數(shù)列例: d = ( 5, 1, 2, 3, 3 )v2v3v4v5v122 Peking University可圖化可圖化:設(shè)非負(fù)整數(shù)列d=( d1,d2, , dn ), 若存在圖G, 使得G的度數(shù)列是d, 則稱d為可圖化的例: d = ( 5, 3, 3, 2, 1 )23 Peking University定理3(可圖化充要條件)定理3:非負(fù)整數(shù)列d=(d1,d2,dn)是可圖化的, 當(dāng)且僅當(dāng)d1+d2+

10、dn=0(mod 2).證明: () 握手定理 () 奇數(shù)度點(diǎn)兩兩之間連一邊, 剩余度用環(huán)來實(shí)現(xiàn). #24 Peking University可簡單圖化可簡單圖化:設(shè)非負(fù)整數(shù)列d=( d1, d2, , dn ), 若存在簡單圖G, 使得G的度數(shù)列是d, 則稱d為可簡單圖化的26 Peking University可簡單圖化充要條件定理5(V. Havel, 1955):設(shè)非負(fù)整數(shù)列d=(d1,d2,dn)滿足:d1+d2+dn=0(mod 2), n-1d1d2dn0,則d可簡單圖化當(dāng)且僅當(dāng) d=(d2-1,d3-1,dd1+1-1,dd1+2,dn)可簡單圖化.27 Peking Univ

11、ersity定理5(圖示)v1v2v3vd1+1vnvd1+2v2v3vd1+1vnvd1+2GGd = (d1,d2,d3,dd1+1,dd1+2,dn)d = (d2-1,d3-1,dd1+1-1,dd1+2,dn)29 Peking University定理5(證明)證明: () 設(shè)d=(d2-1,d3-1,dd1+1-1, dd1+2, , dn)可簡單圖化為 G=, 其中V=v2,v3,vn, 則令G=, V=Vv1, E = E (v1,v2), (v1,v3), , (v1,vd1+1) ,于是d可簡單圖化為G. 30 Peking University定理5(證明,續(xù))證明:

12、() 設(shè)d可簡單圖化為G=, 其中V=v1,v2,vn, d(v1)d(v2)d(vn).(1) 若NG(v1)=v2,v3, ,vd1+1, 則令 G=, V=V-v1, E=E- (v1,v2), (v1,v3), , (v1,vd1+1) , 于是d可簡單圖化為G.(2) 若ij( ij viNG(v1) vjNG(v1) ),31 Peking University定理5(示意)v1v2vivd1+1vnvkGd = (d1,d2,d3,dd1+1,dd1+2,dn)vjv1v2vivd1+1vnvkG1d = (d1,d2,d3,dd1+1,dd1+2,dn)vjv1NG(vi)v1

13、NG(vj)didj vk(vkNG(vi)vkNG(vj)32 Peking University定理5(示意)v1v2vivd1+1vnvkGd = (d1,d2,d3,dd1+1,dd1+2,dn)vjv1v2vivd1+1vnvkG1d = (d1,d2,d3,dd1+1,dd1+2,dn)vj33 Peking University定理5(證明,續(xù))證明: ()(2)若ij(1ijnviNG(v1)vjNG(v1),則由didj可得 k(1knvkNG(vj)vkNG(vi),令G1=,則G1與G的度數(shù)列都還是d,重復(fù)這個步驟,直到化為(1)中情形為止. #34 Peking Uni

14、versity定理4 (可簡單圖化充要條件)定理4(P.Erds,T.Gallai,1960):設(shè)非負(fù)整數(shù)列d=(d1,d2,dn)滿足:n-1d1d2dn0,則d可簡單圖化當(dāng)且僅當(dāng)d1+d2+dn=0(mod 2)并且對r=1,2,n-1有d1+d2+dr r(r-1)+minr,dr+1+minr,dr+2+minr,dn. #35 Peking UniversityPaul Erds(1913-1996) 一生中同485位合作者發(fā)表過1475篇數(shù)學(xué)論文,每天工作19個小時以上。 Another roof, Another proofErdos數(shù)是數(shù)學(xué)界流傳的一個典故。即給每一個數(shù)學(xué)家賦予

15、一個Erdos數(shù)：Erdos本人的Erdos數(shù)是0；曾與Erdos合作發(fā)表過文章的人的Erdos數(shù)是1；沒有與Erdos合作發(fā)表過文章，但與Erdos數(shù)為1的人合作過的是2；不屬于以上任何一類的就是.36 Peking University幾乎每一個當(dāng)代數(shù)學(xué)家都有一個有限的Erdos數(shù)，而且這個數(shù)往往非常小Fields獎得主的Erdos數(shù)都不超過5Nevanlinna獎得主的Erdos數(shù)不超過3Wolf數(shù)學(xué)獎得主的Erdos數(shù)不超過6Steele獎的終身成就獎得主的Erdos數(shù)不超過4. 一些其他領(lǐng)域的專家，Bill Gates，他的Erdos數(shù)是4，通過如下途徑實(shí)現(xiàn)：Erdos-Pavol

16、Hell-Xiao Tie Deng-Chris tos H. Papadimitriou-William H. (Bill) Gates 37 Peking University定理4(舉例)例3: 判斷下列非負(fù)整數(shù)列是否可簡單圖化. (1) (5,4,3,2,2,1) (2)(5,4,4,3,2) (3) (3,3,3,1) (4)(6,6,5,4,3,3,1) (5) (5,5,3,3,2,2,2) (6) (d1,d2,dn), d1d2dn1,解: (1) 5+4+3+2+2+1=170(mod 2).不可(簡單)圖化.38 Peking University定理4(舉例)例3: 判

17、斷下列非負(fù)整數(shù)列是否可簡單圖化. (2)(5,4,4,3,2) 解: (2) 5+4+4+3+2=18=0(mod 2). 但是d1=5n-1=4,不滿足n-1d1, 不可簡單圖化. ( 或者: 但是r=1時, d1=51(1-1)+min1,4 +min1,4+min1,3 +min1,2=4, 不可簡單圖化.)39 Peking University定理4(舉例)例3: 判斷下列非負(fù)整數(shù)列是否可簡單圖化. (3) (3,3,3,1) 解: (3) 3+3+3+1=10=0(mod 2). d1=3=n-1,滿足n-1d1, 但是r=2時,d1+d2=62(2-1)+min2,3+min2,

18、1=5, 不可簡單圖化.40 Peking University定理4(舉例)例3: 判斷下列非負(fù)整數(shù)列是否可簡單圖化. (4)(6,6,5,4,3,3,1) 解: (4) 6+6+5+4+3+3+1=28=0(mod 2).d1=6=n-1,滿足n-1d1. r=1,2時,d1=61(1-1)+min1,6+min1,5+ =6, d1+d2=122(2-1)+min2,5+=11, 不可簡單圖化.或:6,6,*,*,*,*,1不可簡單圖化41 Peking University定理4(舉例)例3: (5) (5,5,3,3,2,2,2)解: (5) 5+5+3+3+2+2+2=22=0(m

19、od 2).d1=5n-1,滿足n-1d1. r=1,2,7時,d1=51(1-1)+min1,5+min1,5+ =6, d1+d2=102(2-1)+min2,3+=12, d1+d2+d3 =133(3-1)+min3,3+=15,d1+d2+d3+d4 =164(4-1)+min4,2+=18,42 Peking University定理4(舉例)例3: (5) (5,5,3,3,2,2,2)解: (5) d1+d2+d5 =185(5-1)+min5,2+=24,d1+d2+d6 =206(6-1)+min6,2=32,d1+d2+d7 =22d2dn1,解: (6) d1d2dn1

20、, dn-12, dn-23, d1n,不滿足n-1d1, 不可簡單圖化. #45 Peking University圖同構(gòu)(graph isomorphism)圖同構(gòu): 設(shè)(有向)圖G1=, G2=, 若存在雙射 f:V1V2, 滿足uV1,vV1, (u,v)E1 (f(u),f(v)E2且與重數(shù)相同， 則稱G1與G2同構(gòu), 記作G1G2算法：NAUTY46 Peking University圖同構(gòu)(舉例)G1G2G3G1G3, G1G247 Peking University圖同構(gòu)(舉例)G1G2G3G1G3, G1G248 Peking University圖同構(gòu)(舉例)G1G2G3G

21、1G2G3彼得森(Peterson)圖49 Peking University圖同構(gòu)(舉例)D1D2D3D1D2, D2D350 Peking University同構(gòu)關(guān)系同構(gòu)關(guān)系是全體圖集合上的二元關(guān)系自反的對稱的傳遞的同構(gòu)關(guān)系是等價關(guān)系51 Peking University圖族(graph class)完全圖,有向完全圖,競賽圖正則圖：柏拉圖圖,彼德森圖,庫拉圖斯基圖r部圖,二部圖(偶圖),完全r部圖路徑,圈,輪52 Peking University完全圖(complete graphs)K1K2K3K4K5每個頂點(diǎn)均與其余的n-1個頂點(diǎn)相鄰,記作Kn53 Peking Univers

22、ity有向完全圖54 Peking University競賽圖(tournament)55 Peking University正則圖(regular graph)k正則圖: vV(G), d(v)=k, r=0,1,2,完全圖Kn是n-1正則圖(n=1,2,3,)56 Peking University柏拉圖圖(Platonic graphs)正四面體圖正六面體圖正八面體圖正十二面體圖正二十面體圖57 Peking University彼德森圖(Pertersen graph)58 Peking University庫拉圖斯基圖(Kuratowski graph)K3,3K559 Peking

23、 Universityr部圖(r-partite graphs)r部圖: G=,若V分成r個互不相交的子集,使得G中任何一條邊的兩個端點(diǎn)都不在同一個Vi中, 即V=V1V2Vr, ViVj= (ij),EU(Vi&Vj)也記作 G=.60 Peking University二部圖(偶圖)(bipartite graphs)二部圖: G=, 也稱為偶圖61 Peking University完全r部圖(complete r-partite graphs)K3,3K2,3Kr,sK1,1,1K1,1,2K1,2,2K1,2,3r個s個Kn1,n2,nr:Vi中任一個頂點(diǎn)均與Vj(ij)所有頂點(diǎn)相鄰

24、62 Peking University圈(cycles)C1C2C3C4C563 Peking University輪(wheels)W1W2W3W4W564 Peking University樹(trees)樹: 連通無回圖65 Peking University子圖,生成子圖子圖(subgraph): G=, G=,GG VV EE真子圖(proper subgraph): GG GG (VV EE)生成子圖(spanning subgraph):G是G的生成子圖 GG V=V66 Peking University導(dǎo)出子圖(induced subgraph)導(dǎo)出子圖: G=, 若V1V

25、, 以G中兩個端點(diǎn)都在V1中的邊組成邊集E1的圖,即E1 = E V1&V1,GV1 = 為由V1導(dǎo)出的子圖若E1E, 以E1中的邊關(guān)聯(lián)的點(diǎn)為頂點(diǎn)集V1, 則稱GE1 = 為由E1導(dǎo)出的子圖67 Peking University導(dǎo)出子圖(舉例)Ge1GV1GE1v1v2v3v4v5v6v7v1v4v5v6v7e2e368 Peking University補(bǔ)圖(complement graph)補(bǔ)圖: 以V為頂點(diǎn)集,以使G稱為n階完全圖的所有添加邊組成的集合為邊集的圖,為G的補(bǔ)圖, 即G=, G=自補(bǔ)圖(self-complement graph):GG69 Peking Universit

26、y例5例5: (1) 畫出5階4條邊的所有非同構(gòu)的無向簡單圖; (2)畫出4階2條邊的所有非同構(gòu)的有向簡單圖.解: (1) d(v)=2m=8, n-1=4,(4,1,1,1,1),(3,2,1,1,1),(2,2,2,1,1),(3,2,2,1,0),(2,2,2,2,0)(2) d+(v)=d-(v)=m=2, d(v)=2m=4,(2,1,1,0),(1,1,1,1),(2,2,0,0)70 Peking University例5(1)例5: (1) 畫出5階4條邊的所有非同構(gòu)的無向簡單圖;解: (1)4,1,1,1,13,2,1,1,12,2,2,1,12,2,2,1,13,2,2,1

27、,02,2,2,2,071 Peking University例5(2)例5: (2)畫出4階2條邊的所有非同構(gòu)的有向簡單圖.解: (2) 2,1,1,02,1,1,02,1,1,01,1,1,12,2,0,072 Peking University圖的運(yùn)算刪除,收縮,加新邊,不交并圖,交圖,差圖,環(huán)和聯(lián)圖,積圖73 Peking University刪除(delete)刪除邊e: G-e = 刪除邊集E: G-E = , 刪除頂點(diǎn)v以及v所關(guān)聯(lián)的所有邊:G-v = ,刪除頂點(diǎn)集V以及V所關(guān)聯(lián)的所有邊:G-V = ,74 Peking University收縮(contract)Ge: e=(u,v)E, 刪除e,將e的兩個端點(diǎn)u與v用一個新的頂點(diǎn)w代替,使w關(guān)聯(lián)除e之外的u,v關(guān)聯(lián)的所有邊euvw75 Peking University加新邊(add new edge)G(u,v) = , 在u與v之間加新邊也寫成G+(u,v)76 Pe