離散數(shù)學(xué)——圖論PPT課件

1、 圖論是一個古老而又年輕的數(shù)學(xué)分支，它誕生于18世紀，它是用圖的方法研究客觀世界的一門科學(xué)，為任何一個包含二元關(guān)系的系統(tǒng)提供了一個直觀而嚴謹?shù)臄?shù)學(xué)模型，因此物理系、化學(xué)、生物學(xué)、工程科學(xué)、管理科學(xué)、計算機科學(xué)等各個領(lǐng)域都有圖論的足跡。第1頁/共93頁圖論的發(fā)展 圖論的產(chǎn)生和發(fā)展經(jīng)歷了二百多年的歷史，從1736年到19世紀中葉是圖論發(fā)展的第一階段。 第二階段大體是從19世紀中葉到1936年，主要研究一些游戲問題：迷宮問題、博弈問題、棋盤上馬的行走線路問題。第2頁/共93頁 一些圖論中的著名問題如四色問題(1852年)和哈密爾頓環(huán)游世界問題(1856年)也大量出現(xiàn)。同時出現(xiàn)了以圖為工具去解決其它領(lǐng)

2、域中一些問題的成果。 1847年德國的克希霍夫(G.R.Kirchoff)將樹的概念和理論應(yīng)用于工程技術(shù)的電網(wǎng)絡(luò)方程組的研究。 1857年英國的凱萊(A.Cayley)也獨立地提出了樹的概念，并應(yīng)用于有機化合物的分子結(jié)構(gòu)的研究中。第3頁/共93頁 1936年匈牙利的數(shù)學(xué)家哥尼格(D.Konig) 發(fā)表了第一部集圖論二百年研究成果于一書的圖論專著有限圖與無限圖理論，這是現(xiàn)代圖論發(fā)展的里程碑，標志著圖論作為一門獨立學(xué)科。 現(xiàn)在圖論的主要分支有圖論、超圖理論、極值圖論、算法圖論、網(wǎng)絡(luò)圖論和隨機圖論等。第4頁/共93頁 第三階段是1936年以后。由于生產(chǎn)管理、軍事、交通運輸、計算機和通訊網(wǎng)絡(luò)等方面的大

3、量問題的出現(xiàn)，大大促進了圖論的發(fā)展?，F(xiàn)代電子計算機的出現(xiàn)與廣泛應(yīng)用極大地促進了圖論的發(fā)展和應(yīng)用。 目前圖論在物理、化學(xué)、運籌學(xué)、計算機科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、社會科學(xué)及經(jīng)濟管理等幾乎所有學(xué)科領(lǐng)域都有應(yīng)用。 第5頁/共93頁 在計算機科學(xué)中計算機科學(xué)的核心之一就是算法的設(shè)計與理論分析，而算法是以圖論與組合數(shù)學(xué)為基礎(chǔ)；圖論與組合數(shù)學(xué)關(guān)系也非常密切，已正式成為計算機諸多分支中一種有力的基礎(chǔ)工具。 因而，作為計算機專業(yè)人員，了解和掌握圖論的基本原理和方法是必要的。第6頁/共93頁 圖論交叉地運用了拓撲學(xué)、群論和數(shù)論知識，其定理證明難度高低不等，有的簡單易懂，有的難于理解，但其每一步證明

4、都需要技巧，每一個定理都像藝術(shù)平一樣值得品味與推敲。 因此，盡管本教材介紹的是較為基礎(chǔ)的圖論內(nèi)容，但閱讀理解與完成習(xí)題是學(xué)習(xí)圖論必不可少的步驟。 第7頁/共93頁 圖是人們?nèi)粘Ｉ钪谐Ｒ姷囊环N信息載體，其突出的特點是直觀、形象。圖論，顧名思義是運用數(shù)學(xué)手段研究圖的性質(zhì)的理論，但這里的圖不是平面坐標系中的函數(shù)，而是由一些點和連接這些點的線組成的結(jié)構(gòu) 。第8頁/共93頁 在圖形中，只關(guān)心點與點之間是否有連線，而不關(guān)心點具體代表哪些對象，也不關(guān)心連線的長短曲直，這就是圖的概念。 當研究的對象能被抽象為離散的元素集合和集合上的二元關(guān)系時，用關(guān)系圖表示和處理十分方便。第9頁/共93頁8.1圖的基本概念

5、圖論的起源可以追溯到1736年由瑞士數(shù)學(xué)家歐拉(Leonhard Euler，1707-1783)撰寫的一篇解決“哥尼斯堡七橋問題”的論文。 第10頁/共93頁哥尼斯堡七橋問題 把四塊陸地用點來表示，橋用點與點連線表示。第11頁/共93頁 歐拉將問題轉(zhuǎn)化為：任何一點出發(fā)，是否存在通過每條邊一次且僅一次又回到出發(fā)點的路？歐拉的結(jié)論是不存在這樣的路。顯然，問題的結(jié)果并不重要，最為重要的是歐拉解決這個問題的中間步驟，即抽象為圖的形式來分析這個問題 。 這是一種全新的思考方式，由此歐拉在他的論文中提出了一個新的數(shù)學(xué)分支，即圖論，因此，歐拉也常常被圖論學(xué)家稱為圖論之父。第12頁/共93頁歐拉 歐拉是著作

6、較多的著名數(shù)學(xué)家之一，曾發(fā)表了886篇論文，出版了近90本書。在數(shù)學(xué)界的許多分支如數(shù)論、幾何、組合數(shù)學(xué)等領(lǐng)域的很多定理和公式都以歐拉命名的。 第13頁/共93頁歐拉簡介第14頁/共93頁圖的基本概念 定義8.1圖（Graph）G包括一個非空的對象的集合 V=v1,v2,vn與有限的V中兩個對象構(gòu)成的無序?qū)?gòu)成的集合 E=e1,e2,em，前者稱為結(jié)點集(Vertex set)，后者稱為邊集（Edge set）。一般用G=表示圖。第15頁/共93頁 例子：教材116頁例8.1，例8.2第16頁/共93頁 根據(jù)圖中邊的方向，分為有向圖、無向圖。 邊關(guān)聯(lián)：有向邊lk=(vi,vj)，其中vi稱為起點

7、，vj稱為終點。無論邊是否有向，稱lk與vi,vj相關(guān)聯(lián)。 鄰接：邊lk=(vi,vj)，稱vi,vj是鄰接的點，若干條邊關(guān)聯(lián)同一個結(jié)點，則稱邊是鄰接的。 環(huán)：邊lk=(vi,vj)， vi與vj是同一個點。 孤立點：不與任何點相鄰接的點。第17頁/共93頁定義圖的子圖 子圖：設(shè)G=， G=，若V是V的子集，E是E的子集，則G是G的子圖。 真子圖：若V是V的子集，E是E的真子集。 生成子圖：V=V，E是E的子集。 舉例說明一個圖的子圖。第18頁/共93頁定義（n,m）圖 (n,m)圖：由n個結(jié)點，m條邊組成的圖。 零圖：m=0。即（n,0）圖，有n個孤立點。 平凡圖：n=1,m=0。即只有一個

8、孤立點。第19頁/共93頁 完全圖：一個（n,m）圖G，其n個結(jié)點中每個結(jié)點均與其它n-1個結(jié)點相鄰接，記為Kn。 無向完全圖：m=n(n-1)/2 有向完全圖：m=n(n-1) 舉例說明以上幾種圖。第20頁/共93頁定義補圖 設(shè)圖G=， G=，若G=是完全圖，且EE=空集，則稱G是G的補圖。 事實上，G與G互為補圖。第21頁/共93頁圖的同構(gòu) 看一下教材120頁一個圖的幾個不同圖形。 我們常將一個圖和它的圖形等同起來，但這是兩個不同的概念，給出圖形就確定了一個圖，然而一個圖的圖形是不唯一的。 考慮圖和圖形的不同。第22頁/共93頁 定義同構(gòu)：圖G=， G=，如果它們的結(jié)點間存在一一對應(yīng)關(guān)系，

9、且這種對應(yīng)關(guān)系也反映在邊的結(jié)點對中，對于有向邊，對應(yīng)的結(jié)點對還保持相同的順序，則稱兩圖是同構(gòu)的。第23頁/共93頁 例1：教材121頁。第24頁/共93頁結(jié)點次數(shù) 引出次數(shù)：有向圖中以結(jié)點v為起點的邊的條數(shù)稱為v的引出次數(shù)，記 引入次數(shù)：有向圖中以結(jié)點v為終點的邊的條數(shù)稱為v的引出次數(shù)，記 結(jié)點次數(shù)：有向圖中引出次數(shù)和引入次數(shù)之和稱為結(jié)點次數(shù)；無向圖中與結(jié)點v相關(guān)聯(lián)的邊的條數(shù)稱為V的次數(shù)。統(tǒng)一為記deg(v)。deg( )vdeg( )v第25頁/共93頁握手定理 定理：G=是(n,m)圖,V=v1,v2,vn 即所有結(jié)點次數(shù)之和等于邊數(shù)的2倍。 定理：有向圖中引入次數(shù)之和等于引出次數(shù)之和，都

10、等于邊數(shù)。 推論：任一圖中，次數(shù)為奇數(shù)的結(jié)點（即奇結(jié)點）的個數(shù)必為偶數(shù)。 i 1deg()2nvim第26頁/共93頁正則圖 所有結(jié)點均有相同次數(shù)d的圖稱為d次正則圖。 如4階的完全圖是3次正則圖，是對角線相連的四邊形。 試畫出兩個2次正則圖。第27頁/共93頁兩圖同構(gòu)需滿足的條件 若兩個圖同構(gòu)，必須滿足下列條件： （1）結(jié)點個數(shù)相同 （2）邊數(shù)相同 （3）次數(shù)相同的結(jié)點個數(shù)相同 例子第28頁/共93頁多重圖與帶權(quán)圖 定義多重圖：包含多重邊的圖。 定義簡單圖：不包含多重邊的圖。 定義有權(quán)圖：具有有權(quán)邊的圖。 定義無權(quán)圖：無有權(quán)邊的圖。第29頁/共93頁練習(xí)題-關(guān)于圖中點的次數(shù)問題 1.設(shè)圖G是

11、3次正則圖，且2n-3=m，則n、m是多少？ 2.設(shè)G是（n,m）圖，G中結(jié)點次數(shù)要么為k，要么為k+1，則次數(shù)為k的結(jié)點有幾個？ 3.設(shè)G有10條邊，4個3度結(jié)點，其余結(jié)點次數(shù)均小于等于2，則G中至少有幾個結(jié)點？第30頁/共93頁解答 1. 2.設(shè)有x個k度結(jié)點，則i1236d eg ()29nnmnvimm()(1)2(1)2kxnxkmxn km第31頁/共93頁 3.設(shè)其余結(jié)點次數(shù)均為2，有 43+2x=102=20 得x=4，因此G中至少有8個結(jié)點。第32頁/共93頁8.2通路、回路與連通性 定義：通路與回路 設(shè)有向圖G=，考慮G中一條邊的序列（vi1,vi2, vik）,稱這種邊的

12、序列為圖的通路。 Vi1、vik分別為起點、終點。通路中邊的條數(shù)稱為通路的長度。 若通路的起點和終點相同，則稱為回路。第33頁/共93頁簡單通路、基本通路 簡單通路：通路中沒有重復(fù)的邊。 基本通路：通路中沒有重復(fù)的點。 簡單回路和基本回路。 基本通路一定是簡單通路，但反之簡單通路不一定是基本通路?；净芈繁厥呛唵位芈贰５?4頁/共93頁 定理：一個有向（n,m）圖中任何基本通路長度n-1。任何基本回路的長度n。 任一通路中如果刪去所有回路，必得基本通路。 任一回路中如刪去其中間的所有回路，必得基本回路。第35頁/共93頁可達性的定義 定義可達性：從一個有向圖的結(jié)點vi到另一個結(jié)點vj間，如果存

13、在一條通路，則稱vi到vj是可達的。 同樣，可以將可達性的概念推廣到無向圖。 利用通路、回路的概念，可研究計算機科學(xué)中的許多問題。第36頁/共93頁連通性 定義：無向圖，若它的任何兩結(jié)點間均是可達的，則稱圖G是連通圖；否則為非連通圖。 定義：有向圖，如果忽略圖的方向后得到的無向圖是連通的，則稱此有向圖為連通圖。否則為非連通圖。第37頁/共93頁有向連通圖 定義：設(shè)G為有向連通圖， 強連通：G中任何兩點都是可達的。 單向連通：G中任何兩結(jié)點間，至少存在一個方向是可達的。 弱連通：忽略邊的方向后得到的無向圖是連通的。第38頁/共93頁連通分支 無向圖中的連通性是等價關(guān)系。 按照等價關(guān)系，可將圖G中

14、的結(jié)點進行分類，一個連通的子圖即是一個等價類，稱為G的一個連通分支。 P（G）表示連通分支的個數(shù)。連通圖的連通分支只有一個。第39頁/共93頁練習(xí)題-圖的連通性問題 1.若圖G是不連通的，則補圖是連通的。 提示：直接證法。 根據(jù)圖的不連通，假設(shè)至少有兩個連通分支；任取G中兩點，證明這兩點是可達的。第40頁/共93頁 2.設(shè)G是有n個結(jié)點的簡單圖，且 |E|(n-1)(n-2)/2，則G是連通圖。 提示：反證法。 設(shè)有兩個連通分支，這兩個分支至多是完全圖。由此得到圖中點與邊之間的數(shù)量關(guān)系。第41頁/共93頁8.3歐拉圖 歐拉圖產(chǎn)生的背景就是前面的七橋問題。 定義：圖G的回路，若它通過G中的每條邊

15、一次，這樣的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。 定義歐拉通路：通過圖G中每條邊一次的通路（非回路）稱為歐拉通路。第42頁/共93頁判斷歐拉通路的定理 定理：無向連通圖G是歐拉圖的充要條件是G的每個結(jié)點均具有偶次數(shù)。 定理：無向連通圖G中結(jié)點vi與vj存在歐拉通路的充要條件是vi與vj的次數(shù)均為奇數(shù)，而其他結(jié)點次數(shù)均為偶數(shù)。第43頁/共93頁例子 郵遞員信件問題 城市街道問題 一筆畫問題 公交線路問題第44頁/共93頁有向歐拉圖的判定 一個有向圖G有歐拉通路當且僅當G是連通的，且除了兩個結(jié)點外，其余結(jié)點的引入次數(shù)等于引出次數(shù)，且這兩結(jié)點中，一個結(jié)點的入度比出度大1，另一個結(jié)點的入度比

16、出度多1. 一個有向圖G是歐拉圖當且僅當G是連通的，且所有結(jié)點的入度等于出度。第45頁/共93頁8.4哈密爾頓圖 與歐拉圖類似的是哈密爾頓圖，它起源于環(huán)游世界的問題。 定義：若圖G的一個回路通過G中每個點一次，這樣的回路稱為哈密爾頓回路，有這種回路的圖稱為哈密爾頓圖。 顯然歐拉回路是簡單回路，無重復(fù)邊；哈密爾頓圖是基本回路，無重復(fù)點。第46頁/共93頁 關(guān)于如何判斷哈密爾頓通路與回路，至今尚未找到它的充要條件，只有一些充分條件和必要條件。第47頁/共93頁H-圖性質(zhì)定理 定理：設(shè)無向圖G=是哈密爾頓圖，非空集V1是V的子集，則P（G-V1）|V1|。 P（G-V1）是從G中刪去V1（包括與V1

17、中結(jié)點相關(guān)聯(lián)的邊）后所得的圖的連通分支。 利用這個定理有時可證明一個圖不是哈密爾頓圖。P（G-V1） |V1|說明不是H-圖。第48頁/共93頁 定理：設(shè)G=是無向簡單圖，|V|3，如果G中每對結(jié)點次數(shù)之和大于等于|V|，則G必為哈密爾頓圖。 定理：設(shè)有向圖，|V| 2，若所有有向邊均用無向邊代替后，所得無向圖中含生成子圖Kn,則G存在哈密爾頓通路。 推論：n階有向完全圖(n2)為哈密爾頓圖。第49頁/共93頁判斷H-圖的一些充分或必要條件 H-圖一定是連通圖，且每個結(jié)點次數(shù)2。 若G是n階圖，則H-通路是長度為n-1的基本通路。 若存在次數(shù)為1的結(jié)點，則G沒有H-回路。 歐拉圖遍歷邊，哈密爾

18、頓圖遍歷點。在H-圖中，H-回路不一定是唯一的。第50頁/共93頁8.5圖的矩陣表示 用矩陣的理論和分析方法來研究圖論，將圖的一些問題轉(zhuǎn)換為矩陣運算問題，更適合于計算機處理。 圖在計算機中就是以矩陣形式存貯和讀取的。 也可借助圖的理論和方法研究矩陣中的問題。第51頁/共93頁有向圖的鄰接矩陣 定義鄰接矩陣：設(shè)有向圖G=，設(shè)各點按一定次序排列，構(gòu)造矩陣 則稱A為圖G的鄰接矩陣。0( ,)EA1( ,)Eijijijijv vaav vn n（ ） ,其中第52頁/共93頁 零圖的鄰接矩陣：A為零矩陣。 完全圖的鄰接矩陣：A除對角線元素為0外，其余元素全為1。 無向圖的鄰接矩陣：將無向邊用兩條方向

19、相反的有向邊代替，將無向圖轉(zhuǎn)成有向圖。 無向圖的鄰接矩陣是對稱陣。 鄰接矩陣的概念還可推廣到多重圖和帶權(quán)圖，考慮如何表示。第53頁/共93頁 一個圖的鄰接矩陣完整的刻畫了圖中結(jié)點間的鄰接關(guān)系，但當結(jié)點次序發(fā)生變化時，對應(yīng)的鄰接矩陣也隨之變化。一般將V強行排序，圖與鄰接矩陣就一一對應(yīng)了。 同構(gòu)的兩個圖，對應(yīng)結(jié)點間的鄰接關(guān)系相同，則它們的鄰接矩陣或者相同或者其中一個通過行、列交換可得到另一個。第54頁/共93頁 例子第55頁/共93頁有向圖的鄰接矩陣和次數(shù) 設(shè)A為有向圖G=的鄰接矩陣，|V|=n，有111deg( )()deg( )()deg( )()()niikknikikniikkiikvav

20、avaav引出次數(shù)引入次數(shù)的次數(shù)第56頁/共93頁無向圖的鄰接矩陣和次數(shù) 設(shè)A為無向圖G=的鄰接矩陣，則A=AT。有11deg( )()nniikkiikkvaav的次數(shù)第57頁/共93頁An =AAA的元素的意義 n=1時，aij=1表示存在一條邊（vi,vj）或者從vi到vj存在一條長度為1的通路。若vi與vj是同一個點，則表示回路。 當n=2時，記B= A2 =(bij)，bij表示從vi到vj存在的長度為2的通路的條數(shù)。 當n=k時，記C= Ak =(cij) ，cij表示從vi到vj存在的長度為k的通路的條數(shù)。第58頁/共93頁 例子第59頁/共93頁可達性矩陣 記Rn=A+A2+A

21、n=(rij)nn，由上一部分Ak的意義知，rij表示給出了從vi到vj的所有長度從1到n的通路的數(shù)目之和。 一般我們并不關(guān)心兩點之間有幾條通路，通路的長度是多少等等。 若rij=0，則表示從vi到vj是不可達的；若rij0，則vi到vj是可達的。 考慮：為什么計算到An即可判斷vi到vj是否可達？第60頁/共93頁 記 稱P為G的可達性矩陣或通路矩陣。 一個圖的可達矩陣給出了圖中各結(jié)點間是否可達及圖中是否有回路。n0,r0Pp1,0jijirijn若（）若第61頁/共93頁 例：求G=的可達矩陣， V、E如下 ： V=v1,v2,v3,v4， E=(v1,v2),(v2,v3),(v2,v4

22、),(v3,v2),(v3,v4),(v3,v1), (v4,v1)。第62頁/共93頁 解：23423440 1 0 00 0 1 12 1 0 11 2 1 10 0 1 12 1 0 01 2 1 12 2 2 3AAAA1 1 0 11 1 1 12 2 1 23 3 2 31 0 0 00 1 0 00 0 1 12 1 0 11 1 1 11 1 1 1RA A,1 1 1 11 1 1 1GAA P，有，所以 中任兩個結(jié)點是可達的。第63頁/共93頁 由于根據(jù)Rn計算可達矩陣較復(fù)雜，在以后的計算中引入布爾運算。 例子：教材136頁例8.11是否存在遞歸調(diào)用？第64頁/共93頁多重

23、圖及有權(quán)圖的矩陣表示 舉例說明。第65頁/共93頁矩陣與無向圖的連通性 設(shè)G為無向圖，由連通性定義知，任兩個結(jié)點都是可達的。 G連通當且僅當G的可達矩陣P除對角線外，所有元素均為1。第66頁/共93頁矩陣與有向圖的連通性 設(shè)G為有向圖，設(shè)P為G的可達矩陣。 （1）G強連通當且僅當P除對角線外均為1。 （2）G單向連通當且僅當P=P+PT， P除對角線外其余元素均為1。 （3）G弱連通當且僅當A=A+AT， P 是A的可達矩陣， P除對角線外其余元素均為1。第67頁/共93頁第九章常用圖 本章介紹圖論中幾種常用圖的基本原理和方法。 樹是圖論中重要概念之一，它在計算機科學(xué)中如算法分析、數(shù)據(jù)結(jié)構(gòu)等有

24、廣泛應(yīng)用。 平面圖 兩步圖第68頁/共93頁9.1樹 定義：樹是不包含回路的連通圖。 在樹中次數(shù)為1的結(jié)點稱為葉，次數(shù)大于1的結(jié)點稱為分支結(jié)點。 例第69頁/共93頁樹的定理 定理9.1：在（n,m）樹中，必有m=n-1。 證明：對n用歸納法。 定理9.2：具有兩個結(jié)點以上的樹必至少有兩片葉。 證明：用反證法、直接法兩種方法。 定理9.3：圖G是樹的充要條件是G的每對結(jié)點間只有一條通路。第70頁/共93頁樹的等價定義 設(shè)圖T=是（n,m）圖，T是樹。 T連通無回路。 T連通且m=n-1。 T無回路，且m=n-1。 T是最小連通圖。 T是最大無回路圖。 T的每對結(jié)點間恰有唯一一條通路。第71頁/

25、共93頁有向樹 定義：在有向圖中若不考慮邊的方向而構(gòu)成樹，則稱為有向樹。 一般常用的有向樹為外向樹和內(nèi)向樹。第72頁/共93頁外向樹 定義外向樹：滿足下列條件的有向樹T稱為外向樹。（1）T有且僅有一個根。（引入次數(shù)為0）（2）T的其它結(jié)點的引入次數(shù)均為1.（3）T有葉。（引出次數(shù)為0，當然引入次數(shù)仍為1） 定義：由外向樹的根到結(jié)點vi的通路長度稱為結(jié)點vi的級。第73頁/共93頁外向樹的相關(guān)概念 兩個結(jié)點如從根到結(jié)點的通路長度相等，則它們同級。否則不同級。 可用外向樹表示上面家屬關(guān)系。例子：紅樓夢人物簡表。雙親，兒子，祖先，子孫，兄弟。 從家屬樹中引入有序樹的概念。兄弟間有一定的次序。第74頁

26、/共93頁定義內(nèi)向樹 定義內(nèi)向樹：滿足下列條件的有向樹T稱為內(nèi)向樹。（1）T有且僅有一個根。（引出次數(shù)為0）（2）T的其它結(jié)點的引出次數(shù)均為1.（3）T有葉。（引入次數(shù)為0，當然引出次數(shù)仍為1） 內(nèi)向樹的概念和性質(zhì)與外向樹類似，故以后只考慮外向樹。 第75頁/共93頁m元樹 定義：設(shè)有n個結(jié)點的外向樹T=，若 vi的引出次數(shù)m，稱T為m元樹；若除了葉外， vi的引出次數(shù)=m，則稱T為m元完全樹。 例：用二元樹表示算術(shù)表達式。 例：計算機中的程序流程圖也可用有序二元樹表示。第76頁/共93頁 二元樹的真正作用在于：任一外向樹均可用二元樹表示。 例子。第77頁/共93頁生成樹 定義：設(shè)G=是一連通

27、圖，T=是G的一個子圖，T是樹，且V=V，E是E的子集，稱T是G的生成樹。 由一連通圖G尋找它的生成樹過程如下：在G中尋找基本回路，找到后在此回路中刪去一邊，并繼續(xù)尋找直至G中無基本回路為止。 一般而言，G的生成樹不是唯一的。第78頁/共93頁求生成樹 若G=（n,m）圖，得到的生成樹為（n,m-1）圖，故由G得到一個生成樹，必須刪去m-(n-1)=m-n+1條邊，稱之為G的基本回路的秩。 練習(xí)：求一圖的生成樹。第79頁/共93頁 尋找一個圖的生成樹是很有實際價值的。 一個連通圖可以有多個生成樹，尋找生成樹使它的總長度最短的問題即為最短樹問題。即求最小生成樹問題。 目前已有很多成熟的算法。第80頁/共93頁9.2平面圖 定義平