湖南大學(xué)離散數(shù)學(xué)圖論PPT課件

1、5.1圖的概念與描述圖的概念與描述 由結(jié)點和連結(jié)兩個結(jié)點的連線所組成的對象稱為由結(jié)點和連結(jié)兩個結(jié)點的連線所組成的對象稱為“圖圖”。 至于結(jié)點的位置及連線的長度無緊要至于結(jié)點的位置及連線的長度無緊要 ADBCe1e2e3e4e5第1頁/共72頁 形式定義形式定義：三元組：三元組(V(G),E(G),M(E,V)稱為圖。其中稱為圖。其中V(G)為點的集合為點的集合(非空集非空集)，E(G)是邊集，是邊集，M(E,V)=邊與點連接關(guān)系。邊與點連接關(guān)系。 常簡化為二元組常簡化為二元組 (V(G),E(G)稱為圖。簡記為稱為圖。簡記為G=(V,E)。第2頁/共72頁5.1圖的概念與描述圖的概念與描述-鄰

2、接矩陣鄰接矩陣 對于對于有向圖有向圖，如果從結(jié)點，如果從結(jié)點vi到結(jié)點到結(jié)點vj之間之間有一條邊有一條邊，則，則a(i,j)=1，否則為，否則為0。 由于結(jié)點由于結(jié)點vi到到vj有一條邊，有一條邊，反過來反過來vj到到vi之間不一定有一條，故之間不一定有一條，故不一定不一定對稱。對稱。 對于對于無向圖無向圖，如果結(jié)點，如果結(jié)點vi到到Vj有一條邊有一條邊，則，則a(i,j)=1，否則為，否則為0。 由于由于Vi到到Vj有一條邊時，有一條邊時，反過來反過來Vj到到Vi肯定也有一條邊。故它是肯定也有一條邊。故它是對稱對稱的。的。第3頁/共72頁ADBCe1e2e3e4e5 110000010100

3、1110可表示自環(huán)，不能表示重邊第4頁/共72頁 0111101111011110第5頁/共72頁5.1圖的概念與描述圖的概念與描述關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣表示關(guān)聯(lián)矩陣表示結(jié)點結(jié)點與與邊邊之間的關(guān)聯(lián)關(guān)系。之間的關(guān)聯(lián)關(guān)系。對于對于有向圖有向圖： 如果如果Vi是是ej的起點，則的起點，則b(i,j)=1。 如果如果Vi是是ej的終點，則的終點，則b(i,j)=-1。 如果以上兩種情況不存在，則如果以上兩種情況不存在，則b(i,j)=0。對于對于無向圖無向圖： 如果如果Vi到到ej某個端點，則某個端點，則b(i,j)=1。 否則否則 b(i,j)=0。該矩陣的行對應(yīng)為該矩陣的行對應(yīng)為“點點”，列對應(yīng)

4、，列對應(yīng)“邊邊”， nm.ejViejViejViejVi第6頁/共72頁ADBCe1e2e3e4e5e6e7 1000011001011001110000101101重邊可表示，重邊可表示，自環(huán)不可能自環(huán)不可能表示表示ABCDe1 e2 e3 e4e5 e6 e7第7頁/共72頁 110100011010001101100011abcde1e2e3e4e5e6第8頁/共72頁有限圖有限圖無限圖無限圖第9頁/共72頁有向圖有向圖無向圖無向圖第10頁/共72頁鄰接鄰接ADBCe1e2e3e4e5第11頁/共72頁度度ADBCe1e2e3e4e5某結(jié)點某結(jié)點關(guān)聯(lián)邊關(guān)聯(lián)邊的的條數(shù)條數(shù)，稱為該，稱為該

5、點的度數(shù)點的度數(shù)：D(A)=5,d入入(A) =1,d出出(A) =4, 有向圖有向圖d入入(A) +d出出(A) =d(A)=5“入入”進進入入某結(jié)點的邊，也稱為某結(jié)點的邊，也稱為“負負邊邊”，負度，負度“出出”離離開開某結(jié)點的邊，也稱為某結(jié)點的邊，也稱為“正正邊邊”，正度，正度第12頁/共72頁各點度數(shù)各點度數(shù)和和= =邊數(shù)的邊數(shù)的2 2倍倍第13頁/共72頁ADBCe1e2e3e4e5第14頁/共72頁圖中度數(shù)圖中度數(shù)為奇的為奇的結(jié)點有結(jié)點有偶數(shù)個偶數(shù)個第15頁/共72頁ADBCe1e2e3e4e5第16頁/共72頁有向圖中有向圖中出度出度( (正度正度) )和和= =入度入度( (負度

6、負度) )和和在有向圖中，每條邊都有起點、與終點。在有向圖中，每條邊都有起點、與終點。每加一條邊使每加一條邊使起點起點的的出度增加出度增加1 1，整圖整圖的出度增加的出度增加1 1每加一條邊使每加一條邊使終點終點的的入度入度增增加加1 1，整圖整圖的入度增加的入度增加1 1每邊使每邊使整圖整圖的的出度出度、入度入度各各增加增加1 1 所有的邊加起來，增加的所有的邊加起來，增加的出度和出度和= =入度和入度和。第17頁/共72頁ADBCe1e2e3e4e5正度正度(出度出度)=4+1+1+2=8負度負度(入度入度)=1+2+3+2=8正度和正度和=負度和負度和第18頁/共72頁n n個結(jié)點完全圖

7、個結(jié)點完全圖KnKn的邊數(shù)的邊數(shù)=n(n-1)/2=n(n-1)/2n(n-1)/2第19頁/共72頁邊數(shù)=n(n-1)/2第20頁/共72頁非空簡單圖非空簡單圖一定存在度相同的結(jié)一定存在度相同的結(jié)點點. . 第21頁/共72頁ADBCe1e2e3e4e53、2、2、33、3、3、3第22頁/共72頁 例題例題某班有某班有23人，班長說每個人恰好只與其他人，班長說每個人恰好只與其他7個人關(guān)系密切，請問班長的話可信嗎？個人關(guān)系密切，請問班長的話可信嗎？ 解解：將以上問題用圖表示，：將以上問題用圖表示，23個人則個人則23個點表示，個點表示，i號同學(xué)對應(yīng)結(jié)點號同學(xué)對應(yīng)結(jié)點i，如果某兩位，如果某兩位

8、同學(xué)關(guān)系密切，則對應(yīng)的結(jié)點間用一條邊相連。同學(xué)關(guān)系密切，則對應(yīng)的結(jié)點間用一條邊相連。 “說每個人恰好只與其他說每個人恰好只與其他7個人個人”，說明與每位同學(xué)相連的邊數(shù)為，說明與每位同學(xué)相連的邊數(shù)為7，即其度數(shù)為，即其度數(shù)為7，23位同學(xué)的度數(shù)和位同學(xué)的度數(shù)和=23*7=161，由握手定理有，由握手定理有161=2m， 一個奇數(shù)不可能等于一個偶數(shù)，顯然矛盾，故班長的話不可信。一個奇數(shù)不可能等于一個偶數(shù)，顯然矛盾，故班長的話不可信。 用圖論來解決問題，關(guān)鍵是將問題中的對象表示為結(jié)點或邊。用圖論來解決問題，關(guān)鍵是將問題中的對象表示為結(jié)點或邊。. . 第23頁/共72頁5.2 圖的連通性圖的連通性 第

9、24頁/共72頁5.2 圖的連通性圖的連通性 第25頁/共72頁5.2 圖的連通性圖的連通性因此求傳遞閉包的方法可用來判斷圖的連通性，因此求傳遞閉包的方法可用來判斷圖的連通性，即即WarShall算法、鄰接矩陣的邏輯冪次方運算。算法、鄰接矩陣的邏輯冪次方運算。第26頁/共72頁 例題例題 判斷下圖是是否連通判斷下圖是是否連通a(1,3)=0從結(jié)點1不能走到結(jié)點3，看圖可知,其他0類似a(1,5)=1從結(jié)點1出發(fā)可達結(jié)點5，看圖可知,其他1類似第27頁/共72頁 例題例題 若求跨越若求跨越1條邊、條邊、2條邊、條邊、n-1條邊的路，究竟有多少條，則直接計算鄰接矩條邊的路，究竟有多少條，則直接計算

10、鄰接矩陣的冪次方陣的冪次方A、A2、A3、An-1。 第28頁/共72頁5.3Euler問題問題 七橋問題七橋問題第29頁/共72頁 第30頁/共72頁第31頁/共72頁第32頁/共72頁5.4 哈密爾頓圖哈密爾頓圖 第33頁/共72頁5.4 哈密爾頓圖哈密爾頓圖 this 一對一對結(jié)點度數(shù)和結(jié)點度數(shù)和n，則，則G中存在一條哈密爾頓回路。中存在一條哈密爾頓回路。即存在一條經(jīng)過所有點一次的回路。即存在一條經(jīng)過所有點一次的回路。充分而不必要充分而不必要！第34頁/共72頁5.4 哈密爾頓圖哈密爾頓圖 第35頁/共72頁5.4 哈密爾頓圖哈密爾頓圖，。第36頁/共72頁5.4 哈密爾頓圖哈密爾頓圖第

11、37頁/共72頁5.4 哈密爾頓圖哈密爾頓圖 第38頁/共72頁5.5 平面圖與染色問題平面圖與染色問題第39頁/共72頁5.5 平面圖與染色問題平面圖與染色問題第40頁/共72頁5.5 平面圖與染色問題平面圖與染色問題第41頁/共72頁5.5 平面圖與染色問題平面圖與染色問題 將將m=3d/2代入代入d=m-n+2中，中，d=3d/2-n+2，故，故d=2n-4第42頁/共72頁5.5 平面圖與染色問題平面圖與染色問題 第43頁/共72頁5.5 平面圖與染色問題平面圖與染色問題 第44頁/共72頁5.5 平面圖與染色問題平面圖與染色問題第45頁/共72頁5.5 平面圖與染色問題平面圖與染色問

12、題第46頁/共72頁5.6 樹樹 。第47頁/共72頁5.6 樹樹 第48頁/共72頁5.6 樹樹 。 第49頁/共72頁5.6 樹樹-Kruskal最小生成樹最小生成樹第50頁/共72頁5.6 樹樹-Prim最小生成樹最小生成樹第51頁/共72頁5.6 樹樹-根樹根樹 A到到F離為離為4，距離中最大值稱為，距離中最大值稱為樹高或?qū)訑?shù)樹高或?qū)訑?shù)第52頁/共72頁5.6 樹樹-根樹根樹 如果結(jié)點至多有如果結(jié)點至多有2個后代，稱為個后代，稱為2叉樹，如果正好叉樹，如果正好都只有都只有2個后代，則稱為個后代，則稱為完全二叉樹完全二叉樹。 畫根樹時，如圖畫根樹時，如圖5.21(b)，習(xí)慣將根結(jié)點畫在最

13、高，習(xí)慣將根結(jié)點畫在最高處處 所有邊都指向遠離根結(jié)點方向，即整體朝下，所有邊都指向遠離根結(jié)點方向，即整體朝下， 對根樹的畫法適當簡化，即去掉所有邊的箭頭，如對根樹的畫法適當簡化，即去掉所有邊的箭頭，如圖圖5.21(b)所示的根樹可簡化為圖所示的根樹可簡化為圖5.22所示所示 第53頁/共72頁5.6 樹樹-根樹根樹 定義定義5.6.4 設(shè)根樹設(shè)根樹T有有t片樹葉片樹葉v1,v2,vt，給每，給每片樹葉賦一個權(quán)值片樹葉賦一個權(quán)值w1,w2,wt，則稱為，則稱為T的賦權(quán)二的賦權(quán)二叉樹，其中叉樹，其中l(wèi)(vi)為葉子結(jié)點為葉子結(jié)點vi的長度。的長度。 如果存在一種賦權(quán)方式，使得值如果存在一種賦權(quán)方式

14、，使得值 w(i)l(vi)達到最達到最小，則稱為棵樹為最優(yōu)二叉樹，或稱小，則稱為棵樹為最優(yōu)二叉樹，或稱Huffman樹。樹。Huffman樹的構(gòu)造算法：樹的構(gòu)造算法：(1)對所有權(quán)值從低到高排隊；對所有權(quán)值從低到高排隊；(2)找出兩個最小的權(quán)值，記為找出兩個最小的權(quán)值，記為W1和和W2。(3)用用W1+W2代替代替W1與與W2，產(chǎn)生新的隊列。，產(chǎn)生新的隊列。(4)若隊列中的點數(shù)大于若隊列中的點數(shù)大于1，則回到，則回到(1)，否則轉(zhuǎn)，否則轉(zhuǎn)(5)。(5)逆序?qū)⒁陨辖M合過程畫出來便得到逆序?qū)⒁陨辖M合過程畫出來便得到Huffman樹。樹。 第54頁/共72頁5.6 樹樹-根樹根樹 第55頁/共72頁5.6 樹樹-根樹根樹第56頁/共72頁5.6 樹樹-根樹根樹 第57頁/共72頁5.7 最短路徑最短路徑第58頁/共72頁5.7 最短路徑最短路徑第59頁/共72頁5.7 最短路徑最短路徑第60頁/共72頁5.7