第四章圖論基礎(chǔ)離散數(shù)學配套教材：李小南目錄CONTENTS4.14.24.34.44.5圖與有向圖樹的性質(zhì)根樹及其應(yīng)用最小生成樹和最短路徑歐拉圖和哈密頓圖4.1圖與有向圖什么是圖？哥尼斯堡七橋問題：從家里出發(fā)，七座橋每橋恰通過一次，再回到家里，是否可能？Euler把兩座小島分別用v1，v2兩點來表示，兩岸的陸地用v2，v4來表示，兩地之間的橋用線段表示，于是得到了圖2.Euler將圖2這種圖形稱為圖.圖1：哥尼斯堡七橋問題圖2：哥尼斯堡七橋圖示內(nèi)容提要4.1節(jié)圖與有向圖圖的定義圖的類型平凡圖有環(huán)圖簡單圖頂點與邊的關(guān)系相鄰關(guān)聯(lián)頂點的度數(shù)圖的基本定理路徑相關(guān)概念通道跡路徑圈子圖、生成子圖、導出子圖、極大連通圖有向圖圖4.1.1一個有限圖4.1.1圖與度序列

圖4.1.1一個有限圖

圖4.1.1一個有限圖

注：每個圖都有一個度序列.反之，并非每個遞減序列都為某個圖的度序列.

4.1.2路徑與連通

圖4.1.2一個不連通圖

圖4.1.2一個不連通圖

子圖生成子圖導出子圖

定義4.1.4圖??的連通分支(connectedcomponent)是指其極大連通子圖.圖??的割點(cut-vertex)(割邊(cut-edge))是指一個頂點(一條邊)且刪除它會增加連通分支的數(shù)目.圖4.1.2一個不連通圖

圖4.1.3有向圖THANKS感謝觀看第4.2節(jié)樹的性質(zhì)離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025內(nèi)容提要4.2節(jié)樹的性質(zhì)樹的定義樹的性質(zhì)生成樹Cayley公式4.2.1樹的定義及刻畫定義4.2.1一個森林(forest)是指一個無圈圖.一棵樹(tree)是指一個連通的森林.度為1的頂點稱為葉子(leaf).若一個圖的生成子圖是一棵樹,則稱該樹是圖的生成樹(spanningtree).例4.2.1

給西安電子科技大學的所有學生編排學號時形成一棵樹.以01,02,03…表示學院；以10,11,12…表示入學年份為2010,2011,2012…,以1,2,3…表示學院的專業(yè)；以001,002,003,…表示各專業(yè)的學生，結(jié)果如圖4.2.1所示,樹中的每個葉子表示一個學生.例如頂點為010的葉子所表示的學生的學號可記為07132010,表示該學生是07學院13級2專業(yè)第10號.圖4.2.1學號樹

4.2.2Cayley公式

圖4

2、3、4個頂點構(gòu)成樹的圖示

123452314611555度數(shù)為1的頂點不出現(xiàn)在編碼中;頂點在編碼中出現(xiàn)的次數(shù)為度數(shù)減1.圖4.2.2

樹及其Prüfer編碼

THANKS感謝觀看第4.3節(jié)根樹及其應(yīng)用離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025內(nèi)容提要4.3節(jié)根樹及其應(yīng)用根樹的定義及其表示樹高頂點的孩子頂點的后代m元樹(m-ary)完全m元樹二叉樹Huffman算法二叉搜索樹決策樹4.3.1Huffman算法

圖4.2.1學號樹圖4.3.1樹及其根樹表示

樹高為2

3元樹，但不是完全3元樹例：假設(shè)傳輸一組數(shù)據(jù)：45533322211110000000.因為ASCII編碼規(guī)定每個字符（包括數(shù)字字符）都占用8位，所以直接傳輸共需

20×8=160位.

解：按照Huffman算法得到的二叉樹如圖4.3.2所示，所以0,1,2,3,4,5的最優(yōu)前綴編碼分別為：0:1;1:011;2:010;3:001;4:0000;5:0001數(shù)字5所需位數(shù)：2×4=8；數(shù)字4所需位數(shù)：1×4=4；數(shù)字3所需位數(shù)：3×3=9；數(shù)字2所需位數(shù)：3×3=9；數(shù)字1所需位數(shù)：4×3=12；數(shù)字0所需位數(shù)：7×1=7.共需要：4+8+9+9+12+7=40位.圖4.3.2編碼樹4.3.2二叉搜索樹和決策樹

圖4.3.3二叉搜索樹圖4.3.3二叉搜索樹

圖4.3.3(a)中給出了一棵完全二叉搜索樹.各頂點的賦值為1,2,...,7.例如，搜索7,先是和4比較,7大于4故而和4的右孩子比較,7又大于6,故再和6的右孩子比較,這樣用了3步就找到了7.如果按照列表1,2,3,...,7則需要7步.

圖4.3.4決策樹

THANKS感謝觀看第4.4節(jié)最小生成樹和最短路徑離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025內(nèi)容提要4.4節(jié)最小生成樹和最短路徑最小生成樹Kruskal算法Prim算法最短路徑Dijkstra算法4.4.1最小生成樹

加權(quán)圖或網(wǎng)絡(luò)(weightedgraph,ornetwork)是各邊都標有數(shù)值(稱為邊的權(quán)值,我們只考慮非負實數(shù)情形)的圖.一個圖的權(quán)是圖中各邊的權(quán)之和.最小生成樹問題就是給定一個加權(quán)連通圖,尋找一個權(quán)值最小的生成樹.圖4.4.1一個加權(quán)連通圖

圖4.4.1Kruskal算法產(chǎn)生的生成樹

注：一個加權(quán)連通圖的最小生成樹不是唯一的.

Prim算法：從某一頂點出發(fā),將訪問過的頂點和未訪問過的頂點之間的權(quán)值最小的邊添加進來,直到所有頂點已被訪問.圖4.4.1一棵連通圖從中間頂點開始.4.4.2最短路徑問題

例4.4.1加權(quán)連通圖如圖4.4.2(a)所示，求頂點a到各個頂點的最短路徑長度.圖4.4.2一個加權(quán)連通圖(a)(b)12322326433646464655565表4.4.1Dijkstra算法迭代情況THANKS感謝觀看第4.5節(jié)歐拉圖和哈密頓圖離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025內(nèi)容提要4.5節(jié)歐拉圖和哈密頓圖歐拉圖歐拉跡歐拉回路歐拉跡存在的充要條件哈密頓圖哈密頓圈哈密頓圖的充分和必要條件4.5.1歐拉圖哥尼斯堡七橋問題：從家里出發(fā)，七座橋每橋恰通過一次，再回到家里，是否可能？(一筆畫問題)圖4.5.1哥尼斯堡七橋圖示人們經(jīng)過多次實驗,都給出了否定的答案,但都未能嚴格證明.1736年,歐拉徹底的解決了這個問題,這一年也被認為是圖論的元年.歐拉用頂點來表示陸地,兩個頂點之間邊的數(shù)目等于兩個陸地之間橋的數(shù)目，于是得到了圖4.5.1(右).這樣問題就轉(zhuǎn)化為此圖中是否存在一條包含所有邊的閉跡1?

4.5.2哈密頓圖

19世紀,哈密頓爵士發(fā)明了一種游戲:給定正十二面體的一個頂點,找出從此頂點出發(fā)經(jīng)其它頂點僅一次又回到出發(fā)頂點的路徑.如圖4.5.3所示，正十二面體確定了一個有20個頂點,30條邊的圖.圖4.5.3正十二面體的圖示哈密頓圖與旅行商問題密切相關(guān).在旅行商問題中，旅行商需要在多個城市之間旅行，每個城市只訪問一次，最終回到出發(fā)城市.這個問題是經(jīng)典的優(yōu)化問題，哈密頓回路就是旅行商問題中的一種解.電路設(shè)計：在電路設(shè)計中，哈密頓回路可用于優(yōu)化電路的布局和布線，減少布線的長度和交叉.

圖5一些哈密頓圖

上述定