離散數(shù)學——圖論PPT通用課件

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

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

3、大地促進了圖論的發(fā)展和應用。目前圖論在物理、化學、運籌學、計算機科學、電子學、信息論、控制論、網(wǎng)絡理論、社會科學及經(jīng)濟管理等幾乎所有學科領域都有應用。 在計算機科學中計算機科學的核心之一就是算法的設計與理論分析，而算法是以圖論與組合數(shù)學為基礎；圖論與組合數(shù)學關系也非常密切，已正式成為計算機諸多分支中一種有力的基礎工具。因而，作為計算機專業(yè)人員，了解和掌握圖論的基本原理和方法是必要的。圖論交叉地運用了拓撲學、群論和數(shù)論知識，其定理證明難度高低不等，有的簡單易懂，有的難于理解，但其每一步證明都需要技巧，每一個定理都像藝術平一樣值得品味與推敲。因此，盡管本教材介紹的是較為基礎的圖論內(nèi)容，但閱讀理解與

4、完成習題是學習圖論必不可少的步驟。 圖是人們?nèi)粘Ｉ钪谐Ｒ姷囊环N信息載體，其突出的特點是直觀、形象。圖論，顧名思義是運用數(shù)學手段研究圖的性質的理論，但這里的圖不是平面坐標系中的函數(shù)，而是由一些點和連接這些點的線組成的結構 。在圖形中，只關心點與點之間是否有連線，而不關心點具體代表哪些對象，也不關心連線的長短曲直，這就是圖的概念。當研究的對象能被抽象為離散的元素集合和集合上的二元關系時，用關系圖表示和處理十分方便。8.1圖的基本概念圖論的起源可以追溯到1736年由瑞士數(shù)學家歐拉(Leonhard Euler，1707-1783)撰寫的一篇解決“哥尼斯堡七橋問題”的論文。 哥尼斯堡七橋問題把四塊陸

5、地用點來表示，橋用點與點連線表示。歐拉將問題轉化為：任何一點出發(fā)，是否存在通過每條邊一次且僅一次又回到出發(fā)點的路？歐拉的結論是不存在這樣的路。顯然，問題的結果并不重要，最為重要的是歐拉解決這個問題的中間步驟，即抽象為圖的形式來分析這個問題 。這是一種全新的思考方式，由此歐拉在他的論文中提出了一個新的數(shù)學分支，即圖論，因此，歐拉也常常被圖論學家稱為圖論之父。歐拉歐拉是著作較多的著名數(shù)學家之一，曾發(fā)表了886篇論文，出版了近90本書。在數(shù)學界的許多分支如數(shù)論、幾何、組合數(shù)學等領域的很多定理和公式都以歐拉命名的。 歐拉簡介圖的基本概念定義8.1圖（Graph）G包括一個非空的對象的集合 V=v1,v

6、2,vn與有限的V中兩個對象構成的無序對構成的集合 E=e1,e2,em，前者稱為結點集(Vertex set)，后者稱為邊集（Edge set）。一般用G=表示圖。例子：教材116頁例8.1，例8.2根據(jù)圖中邊的方向，分為有向圖、無向圖。邊關聯(lián)：有向邊lk=(vi,vj)，其中vi稱為起點，vj稱為終點。無論邊是否有向，稱lk與vi,vj相關聯(lián)。鄰接：邊lk=(vi,vj)，稱vi,vj是鄰接的點，若干條邊關聯(lián)同一個結點，則稱邊是鄰接的。環(huán)：邊lk=(vi,vj)， vi與vj是同一個點。孤立點：不與任何點相鄰接的點。定義圖的子圖子圖：設G=， G=，若V是V的子集，E是E的子集，則G是G的

7、子圖。真子圖：若V是V的子集，E是E的真子集。生成子圖：V=V，E是E的子集。舉例說明一個圖的子圖。定義（n,m）圖(n,m)圖：由n個結點，m條邊組成的圖。零圖：m=0。即（n,0）圖，有n個孤立點。平凡圖：n=1,m=0。即只有一個孤立點。完全圖：一個（n,m）圖G，其n個結點中每個結點均與其它n-1個結點相鄰接，記為Kn。無向完全圖：m=n(n-1)/2有向完全圖：m=n(n-1) 舉例說明以上幾種圖。定義補圖設圖G=， G=，若G=是完全圖，且EE=空集，則稱G是G的補圖。事實上，G與G互為補圖。圖的同構看一下教材120頁一個圖的幾個不同圖形。我們常將一個圖和它的圖形等同起來，但這是兩

8、個不同的概念，給出圖形就確定了一個圖，然而一個圖的圖形是不唯一的?？紤]圖和圖形的不同。定義同構：圖G=， G=，如果它們的結點間存在一一對應關系，且這種對應關系也反映在邊的結點對中，對于有向邊，對應的結點對還保持相同的順序，則稱兩圖是同構的。例1：教材121頁。結點次數(shù)引出次數(shù)：有向圖中以結點v為起點的邊的條數(shù)稱為v的引出次數(shù)，記 引入次數(shù)：有向圖中以結點v為終點的邊的條數(shù)稱為v的引出次數(shù)，記 結點次數(shù)：有向圖中引出次數(shù)和引入次數(shù)之和稱為結點次數(shù)；無向圖中與結點v相關聯(lián)的邊的條數(shù)稱為V的次數(shù)。統(tǒng)一為記deg(v)。握手定理定理：G=是(n,m)圖,V=v1,v2,vn 即所有結點次數(shù)之和等于邊

9、數(shù)的2倍。定理：有向圖中引入次數(shù)之和等于引出次數(shù)之和，都等于邊數(shù)。推論：任一圖中，次數(shù)為奇數(shù)的結點（即奇結點）的個數(shù)必為偶數(shù)。 正則圖所有結點均有相同次數(shù)d的圖稱為d次正則圖。如4階的完全圖是3次正則圖，是對角線相連的四邊形。試畫出兩個2次正則圖。兩圖同構需滿足的條件若兩個圖同構，必須滿足下列條件： （1）結點個數(shù)相同 （2）邊數(shù)相同 （3）次數(shù)相同的結點個數(shù)相同例子多重圖與帶權圖定義多重圖：包含多重邊的圖。定義簡單圖：不包含多重邊的圖。定義有權圖：具有有權邊的圖。定義無權圖：無有權邊的圖。練習題-關于圖中點的次數(shù)問題1.設圖G是3次正則圖，且2n-3=m，則n、m是多少？2.設G是（n,m）

10、圖，G中結點次數(shù)要么為k，要么為k+1，則次數(shù)為k的結點有幾個？3.設G有10條邊，4個3度結點，其余結點次數(shù)均小于等于2，則G中至少有幾個結點？解答1.2.設有x個k度結點，則3.設其余結點次數(shù)均為2，有 43+2x=102=20 得x=4，因此G中至少有8個結點。8.2通路、回路與連通性定義：通路與回路 設有向圖G=，考慮G中一條邊的序列（vi1,vi2, vik）,稱這種邊的序列為圖的通路。 Vi1、vik分別為起點、終點。通路中邊的條數(shù)稱為通路的長度。 若通路的起點和終點相同，則稱為回路。簡單通路、基本通路簡單通路：通路中沒有重復的邊。基本通路：通路中沒有重復的點。簡單回路和基本回路。

11、基本通路一定是簡單通路，但反之簡單通路不一定是基本通路?；净芈繁厥呛唵位芈?。定理：一個有向（n,m）圖中任何基本通路長度n-1。任何基本回路的長度n。任一通路中如果刪去所有回路，必得基本通路。任一回路中如刪去其中間的所有回路，必得基本回路?？蛇_性的定義定義可達性：從一個有向圖的結點vi到另一個結點vj間，如果存在一條通路，則稱vi到vj是可達的。同樣，可以將可達性的概念推廣到無向圖。利用通路、回路的概念，可研究計算機科學中的許多問題。連通性定義：無向圖，若它的任何兩結點間均是可達的，則稱圖G是連通圖；否則為非連通圖。定義：有向圖，如果忽略圖的方向后得到的無向圖是連通的，則稱此有向圖為連通圖。

12、否則為非連通圖。有向連通圖定義：設G為有向連通圖，強連通：G中任何兩點都是可達的。單向連通：G中任何兩結點間，至少存在一個方向是可達的。弱連通：忽略邊的方向后得到的無向圖是連通的。連通分支無向圖中的連通性是等價關系。按照等價關系，可將圖G中的結點進行分類，一個連通的子圖即是一個等價類，稱為G的一個連通分支。P（G）表示連通分支的個數(shù)。連通圖的連通分支只有一個。練習題-圖的連通性問題1.若圖G是不連通的，則補圖是連通的。提示：直接證法。 根據(jù)圖的不連通，假設至少有兩個連通分支；任取G中兩點，證明這兩點是可達的。2.設G是有n個結點的簡單圖，且 |E|(n-1)(n-2)/2，則G是連通圖。提示：

13、反證法。 設有兩個連通分支，這兩個分支至多是完全圖。由此得到圖中點與邊之間的數(shù)量關系。8.3歐拉圖歐拉圖產(chǎn)生的背景就是前面的七橋問題。定義：圖G的回路，若它通過G中的每條邊一次，這樣的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。定義歐拉通路：通過圖G中每條邊一次的通路（非回路）稱為歐拉通路。判斷歐拉通路的定理定理：無向連通圖G是歐拉圖的充要條件是G的每個結點均具有偶次數(shù)。定理：無向連通圖G中結點vi與vj存在歐拉通路的充要條件是vi與vj的次數(shù)均為奇數(shù)，而其他結點次數(shù)均為偶數(shù)。例子郵遞員信件問題城市街道問題一筆畫問題公交線路問題有向歐拉圖的判定一個有向圖G有歐拉通路當且僅當G是連通的，且除了

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

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

16、圖中，H-回路不一定是唯一的。8.5圖的矩陣表示用矩陣的理論和分析方法來研究圖論，將圖的一些問題轉換為矩陣運算問題，更適合于計算機處理。圖在計算機中就是以矩陣形式存貯和讀取的。也可借助圖的理論和方法研究矩陣中的問題。有向圖的鄰接矩陣定義鄰接矩陣：設有向圖G=，設各點按一定次序排列，構造矩陣 則稱A為圖G的鄰接矩陣。零圖的鄰接矩陣：A為零矩陣。完全圖的鄰接矩陣：A除對角線元素為0外，其余元素全為1。無向圖的鄰接矩陣：將無向邊用兩條方向相反的有向邊代替，將無向圖轉成有向圖。無向圖的鄰接矩陣是對稱陣。鄰接矩陣的概念還可推廣到多重圖和帶權圖，考慮如何表示。一個圖的鄰接矩陣完整的刻畫了圖中結點間的鄰接關

17、系，但當結點次序發(fā)生變化時，對應的鄰接矩陣也隨之變化。一般將V強行排序，圖與鄰接矩陣就一一對應了。同構的兩個圖，對應結點間的鄰接關系相同，則它們的鄰接矩陣或者相同或者其中一個通過行、列交換可得到另一個。例子有向圖的鄰接矩陣和次數(shù)設A為有向圖G=的鄰接矩陣，|V|=n，有無向圖的鄰接矩陣和次數(shù)設A為無向圖G=的鄰接矩陣，則A=AT。有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

18、=(cij) ，cij表示從vi到vj存在的長度為k的通路的條數(shù)。例子可達性矩陣記Rn=A+A2+An=(rij)nn，由上一部分Ak的意義知，rij表示給出了從vi到vj的所有長度從1到n的通路的數(shù)目之和。一般我們并不關心兩點之間有幾條通路，通路的長度是多少等等。若rij=0，則表示從vi到vj是不可達的；若rij0，則vi到vj是可達的?？紤]：為什么計算到An即可判斷vi到vj是否可達？記 稱P為G的可達性矩陣或通路矩陣。 一個圖的可達矩陣給出了圖中各結點間是否可達及圖中是否有回路。例：求G=的可達矩陣， V、E如下 ： V=v1,v2,v3,v4， E=(v1,v2),(v2,v3),(

19、v2,v4),(v3,v2),(v3,v4),(v3,v1), (v4,v1)。解：由于根據(jù)Rn計算可達矩陣較復雜，在以后的計算中引入布爾運算。例子：教材136頁例8.11是否存在遞歸調(diào)用？多重圖及有權圖的矩陣表示舉例說明。矩陣與無向圖的連通性設G為無向圖，由連通性定義知，任兩個結點都是可達的。G連通當且僅當G的可達矩陣P除對角線外，所有元素均為1。矩陣與有向圖的連通性設G為有向圖，設P為G的可達矩陣。 （1）G強連通當且僅當P除對角線外均為1。 （2）G單向連通當且僅當P=P+PT， P除對角線外其余元素均為1。 （3）G弱連通當且僅當A=A+AT， P 是A的可達矩陣， P除對角線外其余元

20、素均為1。第九章常用圖本章介紹圖論中幾種常用圖的基本原理和方法。樹是圖論中重要概念之一，它在計算機科學中如算法分析、數(shù)據(jù)結構等有廣泛應用。平面圖兩步圖9.1樹定義：樹是不包含回路的連通圖。在樹中次數(shù)為1的結點稱為葉，次數(shù)大于1的結點稱為分支結點。例樹的定理定理9.1：在（n,m）樹中，必有m=n-1。 證明：對n用歸納法。定理9.2：具有兩個結點以上的樹必至少有兩片葉。 證明：用反證法、直接法兩種方法。定理9.3：圖G是樹的充要條件是G的每對結點間只有一條通路。樹的等價定義設圖T=是（n,m）圖，T是樹。T連通無回路。T連通且m=n-1。T無回路，且m=n-1。T是最小連通圖。T是最大無回路圖

21、。T的每對結點間恰有唯一一條通路。有向樹定義：在有向圖中若不考慮邊的方向而構成樹，則稱為有向樹。一般常用的有向樹為外向樹和內(nèi)向樹。外向樹定義外向樹：滿足下列條件的有向樹T稱為外向樹。（1）T有且僅有一個根。（引入次數(shù)為0）（2）T的其它結點的引入次數(shù)均為1.（3）T有葉。（引出次數(shù)為0，當然引入次數(shù)仍為1）定義：由外向樹的根到結點vi的通路長度稱為結點vi的級。外向樹的相關概念兩個結點如從根到結點的通路長度相等，則它們同級。否則不同級?？捎猛庀驑浔硎旧厦婕覍訇P系。例子：紅樓夢人物簡表。雙親，兒子，祖先，子孫，兄弟。從家屬樹中引入有序樹的概念。兄弟間有一定的次序。定義內(nèi)向樹定義內(nèi)向樹：滿足下列條

22、件的有向樹T稱為內(nèi)向樹。（1）T有且僅有一個根。（引出次數(shù)為0）（2）T的其它結點的引出次數(shù)均為1.（3）T有葉。（引入次數(shù)為0，當然引出次數(shù)仍為1）內(nèi)向樹的概念和性質與外向樹類似，故以后只考慮外向樹。 m元樹定義：設有n個結點的外向樹T=，若 vi的引出次數(shù)m，稱T為m元樹；若除了葉外， vi的引出次數(shù)=m，則稱T為m元完全樹。例：用二元樹表示算術表達式。例：計算機中的程序流程圖也可用有序二元樹表示。二元樹的真正作用在于：任一外向樹均可用二元樹表示。例子。生成樹定義：設G=是一連通圖，T=是G的一個子圖，T是樹，且V=V，E是E的子集，稱T是G的生成樹。由一連通圖G尋找它的生成樹過程如下：在G中尋找基本回路，找到后在此回路中刪去一邊，并繼續(xù)尋找直至G中無基本回路為止。一般而言，G的生成樹不是唯一的。求生成樹若G=（n,m）圖，得到的生成樹為（n,m-1）圖，故由G得到一個生成樹，必須刪去m-(n-1)=m-n+1條邊，稱之為G的基本回路的秩。練習：求一圖的生成樹。尋找一個圖的生成樹是很有實際價值的。一個連通圖可以有多個生成樹，尋找生成樹使它的總長度最短的問題即為最短樹問題。即求最小生成樹問題。目前已有很多成熟的算法。9.2平面圖定義