離散數(shù)學(xué)——圖論優(yōu)秀課件

1、1第四篇圖論 本篇包括第八章、第九章。主要內(nèi)容有圖的基本理論、歐拉圖、哈密爾圖、樹等。2v圖論是一個古老而又年輕的數(shù)學(xué)分支，它誕生于18世紀(jì)，它是用圖的方法研究客觀世界的一門科學(xué)，為任何一個包含二元關(guān)系的系統(tǒng)提供了一個直觀而嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型，因此物理系、化學(xué)、生物學(xué)、工程科學(xué)、管理科學(xué)、計(jì)算機(jī)科學(xué)等各個領(lǐng)域都有圖論的足跡。3圖論的發(fā)展 v圖論的產(chǎn)生和發(fā)展經(jīng)歷了二百多年的歷史，從1736年到19世紀(jì)中葉是圖論發(fā)展的第一階段。v第二階段大體是從19世紀(jì)中葉到1936年，主要研究一些游戲問題：迷宮問題、博弈問題、棋盤上馬的行走線路問題。4v一些圖論中的著名問題如四色問題(1852年)和哈密爾頓環(huán)游世界

2、問題(1856年)也大量出現(xiàn)。同時出現(xiàn)了以圖為工具去解決其它領(lǐng)域中一些問題的成果。v1847年德國的克?；舴?G.R.Kirchoff)將樹的概念和理論應(yīng)用于工程技術(shù)的電網(wǎng)絡(luò)方程組的研究。v1857年英國的凱萊(A.Cayley)也獨(dú)立地提出了樹的概念，并應(yīng)用于有機(jī)化合物的分子結(jié)構(gòu)的研究中。5v1936年匈牙利的數(shù)學(xué)家哥尼格(D.Konig) 發(fā)表了第一部集圖論二百年研究成果于一書的圖論專著有限圖與無限圖理論，這是現(xiàn)代圖論發(fā)展的里程碑，標(biāo)志著圖論作為一門獨(dú)立學(xué)科。v現(xiàn)在圖論的主要分支有圖論、超圖理論、極值圖論、算法圖論、網(wǎng)絡(luò)圖論和隨機(jī)圖論等。6v第三階段是1936年以后。由于生產(chǎn)管理、軍事、交

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

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

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

6、多分支如數(shù)論、幾何、組合數(shù)學(xué)等領(lǐng)域的很多定理和公式都以歐拉命名的。 15歐拉簡介16圖的基本概念v定義8.1圖（Graph）G包括一個非空的對象的集合 V=v1,v2,vn與有限的V中兩個對象構(gòu)成的無序?qū)?gòu)成的集合 E=e1,e2,em，前者稱為結(jié)點(diǎn)集(Vertex set)，后者稱為邊集（Edge set）。一般用G=表示圖。17v例子：教材116頁例8.1，例8.218v根據(jù)圖中邊的方向，分為有向圖、無向圖。v邊關(guān)聯(lián)：有向邊lk=(vi,vj)，其中vi稱為起點(diǎn)，vj稱為終點(diǎn)。無論邊是否有向，稱lk與vi,vj相關(guān)聯(lián)。v鄰接：邊lk=(vi,vj)，稱vi,vj是鄰接的點(diǎn)，若干條邊關(guān)聯(lián)同一

7、個結(jié)點(diǎn)，則稱邊是鄰接的。v環(huán)：邊lk=(vi,vj)， vi與vj是同一個點(diǎn)。v孤立點(diǎn)：不與任何點(diǎn)相鄰接的點(diǎn)。19定義圖的子圖v子圖：設(shè)G=， G=，若V是V的子集，E是E的子集，則G是G的子圖。v真子圖：若V是V的子集，E是E的真子集。v生成子圖：V=V，E是E的子集。v舉例說明一個圖的子圖。20定義（n,m）圖v(n,m)圖：由n個結(jié)點(diǎn)，m條邊組成的圖。v零圖：m=0。即（n,0）圖，有n個孤立點(diǎn)。v平凡圖：n=1,m=0。即只有一個孤立點(diǎn)。21v完全圖：一個（n,m）圖G，其n個結(jié)點(diǎn)中每個結(jié)點(diǎn)均與其它n-1個結(jié)點(diǎn)相鄰接，記為Kn。v無向完全圖：m=n(n-1)/2v有向完全圖：m=n(n

8、-1)v 舉例說明以上幾種圖。22定義補(bǔ)圖v設(shè)圖G=， G=，若G=是完全圖，且EE=空集，則稱G是G的補(bǔ)圖。v事實(shí)上，G與G互為補(bǔ)圖。23圖的同構(gòu)v看一下教材120頁一個圖的幾個不同圖形。v我們常將一個圖和它的圖形等同起來，但這是兩個不同的概念，給出圖形就確定了一個圖，然而一個圖的圖形是不唯一的。v考慮圖和圖形的不同。24v定義同構(gòu)：圖G=， G=，如果它們的結(jié)點(diǎn)間存在一一對應(yīng)關(guān)系，且這種對應(yīng)關(guān)系也反映在邊的結(jié)點(diǎn)對中，對于有向邊，對應(yīng)的結(jié)點(diǎn)對還保持相同的順序，則稱兩圖是同構(gòu)的。25v例1：教材121頁。26結(jié)點(diǎn)次數(shù)v引出次數(shù)：有向圖中以結(jié)點(diǎn)v為起點(diǎn)的邊的條數(shù)稱為v的引出次數(shù)，記 v引入次數(shù)：

9、有向圖中以結(jié)點(diǎn)v為終點(diǎn)的邊的條數(shù)稱為v的引出次數(shù)，記 v結(jié)點(diǎn)次數(shù)：有向圖中引出次數(shù)和引入次數(shù)之和稱為結(jié)點(diǎn)次數(shù)；無向圖中與結(jié)點(diǎn)v相關(guān)聯(lián)的邊的條數(shù)稱為V的次數(shù)。統(tǒng)一為記deg(v)。deg( )vdeg( )v27握手定理v定理：G=是(n,m)圖,V=v1,v2,vn 即所有結(jié)點(diǎn)次數(shù)之和等于邊數(shù)的2倍。v定理：有向圖中引入次數(shù)之和等于引出次數(shù)之和，都等于邊數(shù)。v推論：任一圖中，次數(shù)為奇數(shù)的結(jié)點(diǎn)（即奇結(jié)點(diǎn)）的個數(shù)必為偶數(shù)。 i 1deg()2nvim28正則圖v所有結(jié)點(diǎn)均有相同次數(shù)d的圖稱為d次正則圖。v如4階的完全圖是3次正則圖，是對角線相連的四邊形。v試畫出兩個2次正則圖。29兩圖同構(gòu)需滿足的

10、條件v若兩個圖同構(gòu)，必須滿足下列條件： （1）結(jié)點(diǎn)個數(shù)相同 （2）邊數(shù)相同 （3）次數(shù)相同的結(jié)點(diǎn)個數(shù)相同v例子30多重圖與帶權(quán)圖v定義多重圖：包含多重邊的圖。v定義簡單圖：不包含多重邊的圖。v定義有權(quán)圖：具有有權(quán)邊的圖。v定義無權(quán)圖：無有權(quán)邊的圖。31練習(xí)題-關(guān)于圖中點(diǎn)的次數(shù)問題v1.設(shè)圖G是3次正則圖，且2n-3=m，則n、m是多少？v2.設(shè)G是（n,m）圖，G中結(jié)點(diǎn)次數(shù)要么為k，要么為k+1，則次數(shù)為k的結(jié)點(diǎn)有幾個？v3.設(shè)G有10條邊，4個3度結(jié)點(diǎn)，其余結(jié)點(diǎn)次數(shù)均小于等于2，則G中至少有幾個結(jié)點(diǎn)？32解答v1.v2.設(shè)有x個k度結(jié)點(diǎn)，則i1236d eg ()29nnmnvimm()(1

11、)2(1)2k xnxkmxnkm33v3.設(shè)其余結(jié)點(diǎn)次數(shù)均為2，有 43+2x=102=20 得x=4，因此G中至少有8個結(jié)點(diǎn)。348.2通路、回路與連通性v定義：通路與回路 設(shè)有向圖G=，考慮G中一條邊的序列（vi1,vi2, vik）,稱這種邊的序列為圖的通路。 Vi1、vik分別為起點(diǎn)、終點(diǎn)。通路中邊的條數(shù)稱為通路的長度。 若通路的起點(diǎn)和終點(diǎn)相同，則稱為回路。35簡單通路、基本通路v簡單通路：通路中沒有重復(fù)的邊。v基本通路：通路中沒有重復(fù)的點(diǎn)。v簡單回路和基本回路。v基本通路一定是簡單通路，但反之簡單通路不一定是基本通路?；净芈繁厥呛唵位芈?。36v定理：一個有向（n,m）圖中任何基本

12、通路長度n-1。任何基本回路的長度n。v任一通路中如果刪去所有回路，必得基本通路。v任一回路中如刪去其中間的所有回路，必得基本回路。37可達(dá)性的定義v定義可達(dá)性：從一個有向圖的結(jié)點(diǎn)vi到另一個結(jié)點(diǎn)vj間，如果存在一條通路，則稱vi到vj是可達(dá)的。v同樣，可以將可達(dá)性的概念推廣到無向圖。v利用通路、回路的概念，可研究計(jì)算機(jī)科學(xué)中的許多問題。38連通性v定義：無向圖，若它的任何兩結(jié)點(diǎn)間均是可達(dá)的，則稱圖G是連通圖；否則為非連通圖。v定義：有向圖，如果忽略圖的方向后得到的無向圖是連通的，則稱此有向圖為連通圖。否則為非連通圖。39有向連通圖v定義：設(shè)G為有向連通圖，v強(qiáng)連通：G中任何兩點(diǎn)都是可達(dá)的。v

13、單向連通：G中任何兩結(jié)點(diǎn)間，至少存在一個方向是可達(dá)的。v弱連通：忽略邊的方向后得到的無向圖是連通的。40連通分支v無向圖中的連通性是等價(jià)關(guān)系。v按照等價(jià)關(guān)系，可將圖G中的結(jié)點(diǎn)進(jìn)行分類，一個連通的子圖即是一個等價(jià)類，稱為G的一個連通分支。vP（G）表示連通分支的個數(shù)。連通圖的連通分支只有一個。41練習(xí)題-圖的連通性問題v1.若圖G是不連通的，則補(bǔ)圖是連通的。v提示：直接證法。 根據(jù)圖的不連通，假設(shè)至少有兩個連通分支；任取G中兩點(diǎn)，證明這兩點(diǎn)是可達(dá)的。42v2.設(shè)G是有n個結(jié)點(diǎn)的簡單圖，且 |E|(n-1)(n-2)/2，則G是連通圖。v提示：反證法。 設(shè)有兩個連通分支，這兩個分支至多是完全圖。由

14、此得到圖中點(diǎn)與邊之間的數(shù)量關(guān)系。438.3歐拉圖v歐拉圖產(chǎn)生的背景就是前面的七橋問題。v定義：圖G的回路，若它通過G中的每條邊一次，這樣的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。v定義歐拉通路：通過圖G中每條邊一次的通路（非回路）稱為歐拉通路。44判斷歐拉通路的定理v定理：無向連通圖G是歐拉圖的充要條件是G的每個結(jié)點(diǎn)均具有偶次數(shù)。v定理：無向連通圖G中結(jié)點(diǎn)vi與vj存在歐拉通路的充要條件是vi與vj的次數(shù)均為奇數(shù)，而其他結(jié)點(diǎn)次數(shù)均為偶數(shù)。45例子v郵遞員信件問題v城市街道問題v一筆畫問題v公交線路問題46有向歐拉圖的判定v一個有向圖G有歐拉通路當(dāng)且僅當(dāng)G是連通的，且除了兩個結(jié)點(diǎn)外，其余結(jié)

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

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

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

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

19、圖G=的鄰接矩陣，則A=AT。有11deg( )()nniikkiikkvaav的次數(shù)59An =AAA的元素的意義vn=1時，aij=1表示存在一條邊（vi,vj）或者從vi到vj存在一條長度為1的通路。若vi與vj是同一個點(diǎn)，則表示回路。v當(dāng)n=2時，記B= A2 =(bij)，bij表示從vi到vj存在的長度為2的通路的條數(shù)。v當(dāng)n=k時，記C= Ak =(cij) ，cij表示從vi到vj存在的長度為k的通路的條數(shù)。60v例子61可達(dá)性矩陣v記Rn=A+A2+An=(rij)nn，由上一部分Ak的意義知，rij表示給出了從vi到vj的所有長度從1到n的通路的數(shù)目之和。v一般我們并不關(guān)心

20、兩點(diǎn)之間有幾條通路，通路的長度是多少等等。v若rij=0，則表示從vi到vj是不可達(dá)的；若rij0，則vi到vj是可達(dá)的。v考慮：為什么計(jì)算到An即可判斷vi到vj是否可達(dá)？62v記 稱P為G的可達(dá)性矩陣或通路矩陣。 一個圖的可達(dá)矩陣給出了圖中各結(jié)點(diǎn)間是否可達(dá)及圖中是否有回路。n0,r0Pp1,0jijirijn若（）若63v例：求G=的可達(dá)矩陣， V、E如下 ： V=v1,v2,v3,v4， E=(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v3,v1), (v4,v1)。64v解：23423440 1 0 00 0 1 12 1 0 11 2 1 10

21、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é)點(diǎn)是可達(dá)的。65v由于根據(jù)Rn計(jì)算可達(dá)矩陣較復(fù)雜，在以后的計(jì)算中引入布爾運(yùn)算。v例子：教材136頁例8.11是否存在遞歸調(diào)用？66多重圖及有權(quán)圖的矩陣表示v舉例說明。67矩陣與無向圖的連通性v設(shè)G為無向圖，由連通性定義知，任兩個結(jié)點(diǎn)都是可達(dá)的。vG連通當(dāng)且僅當(dāng)G的可達(dá)矩陣P除對角線外，所有元素均為1。68矩陣與有向圖的連通性v設(shè)

22、G為有向圖，設(shè)P為G的可達(dá)矩陣。 （1）G強(qiáng)連通當(dāng)且僅當(dāng)P除對角線外均為1。 （2）G單向連通當(dāng)且僅當(dāng)P=P+PT， P除對角線外其余元素均為1。 （3）G弱連通當(dāng)且僅當(dāng)A=A+AT， P 是A的可達(dá)矩陣， P除對角線外其余元素均為1。69第九章常用圖v本章介紹圖論中幾種常用圖的基本原理和方法。v樹是圖論中重要概念之一，它在計(jì)算機(jī)科學(xué)中如算法分析、數(shù)據(jù)結(jié)構(gòu)等有廣泛應(yīng)用。v平面圖v兩步圖709.1樹v定義：樹是不包含回路的連通圖。v在樹中次數(shù)為1的結(jié)點(diǎn)稱為葉，次數(shù)大于1的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。v例71樹的定理v定理9.1：在（n,m）樹中，必有m=n-1。 證明：對n用歸納法。v定理9.2：具有兩個

23、結(jié)點(diǎn)以上的樹必至少有兩片葉。 證明：用反證法、直接法兩種方法。v定理9.3：圖G是樹的充要條件是G的每對結(jié)點(diǎn)間只有一條通路。72樹的等價(jià)定義v設(shè)圖T=是（n,m）圖，T是樹。vT連通無回路。vT連通且m=n-1。vT無回路，且m=n-1。vT是最小連通圖。vT是最大無回路圖。vT的每對結(jié)點(diǎn)間恰有唯一一條通路。73有向樹v定義：在有向圖中若不考慮邊的方向而構(gòu)成樹，則稱為有向樹。v一般常用的有向樹為外向樹和內(nèi)向樹。74外向樹v定義外向樹：滿足下列條件的有向樹T稱為外向樹。（1）T有且僅有一個根。（引入次數(shù)為0）（2）T的其它結(jié)點(diǎn)的引入次數(shù)均為1.（3）T有葉。（引出次數(shù)為0，當(dāng)然引入次數(shù)仍為1）v

24、定義：由外向樹的根到結(jié)點(diǎn)vi的通路長度稱為結(jié)點(diǎn)vi的級。75外向樹的相關(guān)概念v兩個結(jié)點(diǎn)如從根到結(jié)點(diǎn)的通路長度相等，則它們同級。否則不同級。v可用外向樹表示上面家屬關(guān)系。例子：紅樓夢人物簡表。雙親，兒子，祖先，子孫，兄弟。v從家屬樹中引入有序樹的概念。兄弟間有一定的次序。76定義內(nèi)向樹v定義內(nèi)向樹：滿足下列條件的有向樹T稱為內(nèi)向樹。（1）T有且僅有一個根。（引出次數(shù)為0）（2）T的其它結(jié)點(diǎn)的引出次數(shù)均為1.（3）T有葉。（引入次數(shù)為0，當(dāng)然引出次數(shù)仍為1）v內(nèi)向樹的概念和性質(zhì)與外向樹類似，故以后只考慮外向樹。 77m元樹v定義：設(shè)有n個結(jié)點(diǎn)的外向樹T=，若 vi的引出次數(shù)m，稱T為m元樹；若除了

25、葉外， vi的引出次數(shù)=m，則稱T為m元完全樹。v例：用二元樹表示算術(shù)表達(dá)式。v例：計(jì)算機(jī)中的程序流程圖也可用有序二元樹表示。78v二元樹的真正作用在于：任一外向樹均可用二元樹表示。v例子。79生成樹v定義：設(shè)G=是一連通圖，T=是G的一個子圖，T是樹，且V=V，E是E的子集，稱T是G的生成樹。v由一連通圖G尋找它的生成樹過程如下：在G中尋找基本回路，找到后在此回路中刪去一邊，并繼續(xù)尋找直至G中無基本回路為止。v一般而言，G的生成樹不是唯一的。80求生成樹v若G=（n,m）圖，得到的生成樹為（n,m-1）圖，故由G得到一個生成樹，必須刪去m-(n-1)=m-n+1條邊，稱之為G的基本回路的秩。v練習(xí)：求一圖的生成樹。81v尋找一個圖的生成樹是很有實(shí)際價(jià)值的。v一個連通圖可以有多個生成樹，尋找生成樹使它的總長度最短的問題即為最