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

圖4.1.1一個(gè)有限圖

圖4.1.1一個(gè)有限圖

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

4.1.2路徑與連通

圖4.1.2一個(gè)不連通圖

圖4.1.2一個(gè)不連通圖

子圖生成子圖導(dǎo)出子圖

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

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

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

4.2.2Cayley公式

圖4

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

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

樹及其Prüfer編碼

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

圖4.2.1學(xué)號樹圖4.3.1樹及其根樹表示

樹高為2

3元樹，但不是完全3元樹例：假設(shè)傳輸一組數(shù)據(jù)：45533322211110000000.因?yàn)锳SCII編碼規(guī)定每個(gè)字符（包括數(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)中給出了一棵完全二叉搜索樹.各頂點(diǎn)的賦值為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ù)學(xué)講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學(xué)，電子工業(yè)出版社，2025內(nèi)容提要4.4節(jié)最小生成樹和最短路徑最小生成樹Kruskal算法Prim算法最短路徑Dijkstra算法4.4.1最小生成樹

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

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

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

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

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

4.5.2哈密頓圖

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

圖5一些哈密頓圖

上述定