離散數(shù)學-圖論.ppt

《離散數(shù)學-圖論.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學-圖論.ppt（93頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第四篇圖論,本篇包括第八章、第九章。主要內(nèi)容有圖的基本理論、歐拉圖、哈密爾圖、樹等。,圖論是一個古老而又年輕的數(shù)學分支，它誕生于18世紀，它是用圖的方法研究客觀世界的一門科學，為任何一個包含二元關(guān)系的系統(tǒng)提供了一個直觀而嚴謹?shù)臄?shù)學模型，因此物理系、化學、生物學、工程科學、管理科學、計算機科學等各個領(lǐng)域都有圖論的足跡。,圖論的發(fā)展,圖論的產(chǎn)生和發(fā)展經(jīng)歷了二百多年的歷史，從1736年到19世紀中葉是圖論發(fā)展的第一階段。 第二階段大體是從19世紀中葉到1936年，主要研究一些游戲問題：迷宮問題、博弈問題、棋盤上馬的行走線路問題。,一些圖論中的著名問題如四色問題(1852年)和哈密爾頓環(huán)游世界問題(1856年)也大量出現(xiàn)。同時出現(xiàn)了以圖為工具去解決其它領(lǐng)域中一些問題的成果。 1847年德國的克希霍夫(G.R.Kirchoff)將樹的概念和理論應用于工程技術(shù)的電網(wǎng)絡方程組的研究。 1857年英國的凱萊(A.Cayley)也獨立地提出了樹的概念，并應用于有機化合物的分子結(jié)構(gòu)的研究中。,1936年匈牙利的數(shù)學家哥尼格(D.Konig) 發(fā)表了第一部集圖論二百年研究成果于一書的圖論專著《有限圖與無限圖理論》，這是現(xiàn)代圖論發(fā)展的里程碑，標志著圖論作為一門獨立學科。 現(xiàn)在圖論的主要分支有圖論、超圖理論、極值圖論、算法圖論、網(wǎng)絡圖論和隨機圖論等。,第三階段是1936年以后。由于生產(chǎn)管理、軍事、交通運輸、計算機和通訊網(wǎng)絡等方面的大量問題的出現(xiàn)，大大促進了圖論的發(fā)展。現(xiàn)代電子計算機的出現(xiàn)與廣泛應用極大地促進了圖論的發(fā)展和應用。 目前圖論在物理、化學、運籌學、計算機科學、電子學、信息論、控制論、網(wǎng)絡理論、社會科學及經(jīng)濟管理等幾乎所有學科領(lǐng)域都有應用。。,在計算機科學中計算機科學的核心之一就是算法的設計與理論分析，而算法是以圖論與組合數(shù)學為基礎(chǔ)；圖論與組合數(shù)學關(guān)系也非常密切，已正式成為計算機諸多分支中一種有力的基礎(chǔ)工具。 因而，作為計算機專業(yè)人員，了解和掌握圖論的基本原理和方法是必要的。,圖論交叉地運用了拓撲學、群論和數(shù)論知識，其定理證明難度高低不等，有的簡單易懂，有的難于理解，但其每一步證明都需要技巧，每一個定理都像藝術(shù)平一樣值得品味與推敲。 因此，盡管本教材介紹的是較為基礎(chǔ)的圖論內(nèi)容，但閱讀理解與完成習題是學習圖論必不可少的步驟。,圖是人們?nèi)粘Ｉ钪谐Ｒ姷囊环N信息載體，其突出的特點是直觀、形象。圖論，顧名思義是運用數(shù)學手段研究圖的性質(zhì)的理論，但這里的圖不是平面坐標系中的函數(shù)，而是由一些點和連接這些點的線組成的結(jié)構(gòu) 。,在圖形中，只關(guān)心點與點之間是否有連線，而不關(guān)心點具體代表哪些對象，也不關(guān)心連線的長短曲直，這就是圖的概念。 當研究的對象能被抽象為離散的元素集合和集合上的二元關(guān)系時，用關(guān)系圖表示和處理十分方便。,8.1圖的基本概念,圖論的起源可以追溯到1736年由瑞士數(shù)學家歐拉(Leonhard Euler，1707-1783)撰寫的一篇解決“哥尼斯堡七橋問題”的論文。,哥尼斯堡七橋問題,把四塊陸地用點來表示，橋用點與點連線表示。,歐拉將問題轉(zhuǎn)化為：任何一點出發(fā)，是否存在通過每條邊一次且僅一次又回到出發(fā)點的路？歐拉的結(jié)論是不存在這樣的路。顯然，問題的結(jié)果并不重要，最為重要的是歐拉解決這個問題的中間步驟，即抽象為圖的形式來分析這個問題 。 這是一種全新的思考方式，由此歐拉在他的論文中提出了一個新的數(shù)學分支，即圖論，因此，歐拉也常常被圖論學家稱為圖論之父。,歐拉,歐拉是著作較多的著名數(shù)學家之一，曾發(fā)表了886篇論文，出版了近90本書。在數(shù)學界的許多分支如數(shù)論、幾何、組合數(shù)學等領(lǐng)域的很多定理和公式都以歐拉命名的。,歐拉簡介,,圖的基本概念,定義8.1圖（Graph）G包括一個非空的對象的集合 V={v1,v2,…,vn} 與有限的V中兩個對象構(gòu)成的無序?qū)?gòu)成的集合 E={e1,e2,…,em}， 前者稱為結(jié)點集(Vertex set)，后者稱為邊集（Edge set）。 一般用G=表示圖。,,例子：教材116頁例8.1，例8.2,根據(jù)圖中邊的方向，分為有向圖、無向圖。 邊關(guān)聯(lián)：有向邊lk=(vi,vj)，其中vi稱為起點，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是同一個點。 孤立點：不與任何點相鄰接的點。,定義圖的子圖,子圖：設G=， G’=，若V’是V的子集，E’是E的子集，則G’是G的子圖。 真子圖：若V’是V的子集，E’是E的真子集。 生成子圖：V’=V，E’是E的子集。 舉例說明一個圖的子圖。,定義（n,m）圖,(n,m)圖：由n個結(jié)點，m條邊組成的圖。 零圖：m=0。即（n,0）圖，有n個孤立點。 平凡圖：n=1,m=0。即只有一個孤立點。,完全圖：一個（n,m）圖G，其n個結(jié)點中每個結(jié)點均與其它n-1個結(jié)點相鄰接，記為Kn。 無向完全圖：m=n(n-1)/2 有向完全圖：m=n(n-1) 舉例說明以上幾種圖。,定義補圖,設圖G=， G’=，若G’’=是完全圖，且E∩E’=空集，則稱G’是G的補圖。 事實上，G與G’互為補圖。,圖的同構(gòu),看一下教材120頁一個圖的幾個不同圖形。 我們常將一個圖和它的圖形等同起來，但這是兩個不同的概念，給出圖形就確定了一個圖，然而一個圖的圖形是不唯一的。 考慮圖和圖形的不同。,,定義同構(gòu)：圖G=， G’=，如果它們的結(jié)點間存在一一對應關(guān)系，且這種對應關(guān)系也反映在邊的結(jié)點對中，對于有向邊，對應的結(jié)點對還保持相同的順序，則稱兩圖是同構(gòu)的。,,例1：教材121頁。,結(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)。,握手定理,定理：G=是(n,m)圖,V={v1,v2,…,vn} 即所有結(jié)點次數(shù)之和等于邊數(shù)的2倍。 定理：有向圖中引入次數(shù)之和等于引出次數(shù)之和，都等于邊數(shù)。 推論：任一圖中，次數(shù)為奇數(shù)的結(jié)點（即奇結(jié)點）的個數(shù)必為偶數(shù)。,正則圖,所有結(jié)點均有相同次數(shù)d的圖稱為d次正則圖。 如4階的完全圖是3次正則圖，是對角線相連的四邊形。 試畫出兩個2次正則圖。,兩圖同構(gòu)需滿足的條件,若兩個圖同構(gòu)，必須滿足下列條件： （1）結(jié)點個數(shù)相同 （2）邊數(shù)相同 （3）次數(shù)相同的結(jié)點個數(shù)相同 例子,多重圖與帶權(quán)圖,定義多重圖：包含多重邊的圖。 定義簡單圖：不包含多重邊的圖。 定義有權(quán)圖：具有有權(quán)邊的圖。 定義無權(quán)圖：無有權(quán)邊的圖。,練習題----關(guān)于圖中點的次數(shù)問題,1.設圖G是3次正則圖，且2n-3=m，則n、m是多少？ 2.設G是（n,m）圖，G中結(jié)點次數(shù)要么為k，要么為k+1，則次數(shù)為k的結(jié)點有幾個？ 3.設G有10條邊，4個3度結(jié)點，其余結(jié)點次數(shù)均小于等于2，則G中至少有幾個結(jié)點？,解答,1. 2.設有x個k度結(jié)點，則,,3.設其余結(jié)點次數(shù)均為2，有 43+2x=102=20 得x=4，因此G中至少有8個結(jié)點。,8.2通路、回路與連通性,定義：通路與回路 設有向圖G=，考慮G中一條邊的序列（vi1,vi2,…, vik）,稱這種邊的序列為圖的通路。 Vi1、vik分別為起點、終點。通路中邊的條數(shù)稱為通路的長度。 若通路的起點和終點相同，則稱為回路。,簡單通路、基本通路,簡單通路：通路中沒有重復的邊。 基本通路：通路中沒有重復的點。 簡單回路和基本回路。 基本通路一定是簡單通路，但反之簡單通路不一定是基本通路。基本回路必是簡單回路。,定理：一個有向（n,m）圖中任何基本通路長度≤n-1。任何基本回路的長度≤n。 任一通路中如果刪去所有回路，必得基本通路。 任一回路中如刪去其中間的所有回路，必得基本回路。,可達性的定義,定義可達性：從一個有向圖的結(jié)點vi到另一個結(jié)點vj間，如果存在一條通路，則稱vi到vj是可達的。 同樣，可以將可達性的概念推廣到無向圖。 利用通路、回路的概念，可研究計算機科學中的許多問題。,連通性,定義：無向圖，若它的任何兩結(jié)點間均是可達的，則稱圖G是連通圖；否則為非連通圖。 定義：有向圖，如果忽略圖的方向后得到的無向圖是連通的，則稱此有向圖為連通圖。否則為非連通圖。,有向連通圖,定義：設G為有向連通圖， 強連通：G中任何兩點都是可達的。 單向連通：G中任何兩結(jié)點間，至少存在一個方向是可達的。 弱連通：忽略邊的方向后得到的無向圖是連通的。,連通分支,無向圖中的連通性是等價關(guān)系。 按照等價關(guān)系，可將圖G中的結(jié)點進行分類，一個連通的子圖即是一個等價類，稱為G的一個連通分支。 P（G）表示連通分支的個數(shù)。連通圖的連通分支只有一個。,練習題---圖的連通性問題,1.若圖G是不連通的，則補圖是連通的。 提示：直接證法。 根據(jù)圖的不連通，假設至少有兩個連通分支；任取G中兩點，證明這兩點是可達的。,,2.設G是有n個結(jié)點的簡單圖，且 |E|(n-1)(n-2)/2，則G是連通圖。 提示：反證法。 設有兩個連通分支，這兩個分支至多是完全圖。由此得到圖中點與邊之間的數(shù)量關(guān)系。,8.3歐拉圖,歐拉圖產(chǎn)生的背景就是前面的七橋問題。 定義：圖G的回路，若它通過G中的每條邊一次，這樣的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。 定義歐拉通路：通過圖G中每條邊一次的通路（非回路）稱為歐拉通路。,判斷歐拉通路的定理,定理：無向連通圖G是歐拉圖的充要條件是G的每個結(jié)點均具有偶次數(shù)。 定理：無向連通圖G中結(jié)點vi與vj存在歐拉通路的充要條件是vi與vj的次數(shù)均為奇數(shù)，而其他結(jié)點次數(shù)均為偶數(shù)。,例子,郵遞員信件問題 城市街道問題 一筆畫問題 公交線路問題,有向歐拉圖的判定,一個有向圖G有歐拉通路當且僅當G是連通的，且除了兩個結(jié)點外，其余結(jié)點的引入次數(shù)等于引出次數(shù)，且這兩結(jié)點中，一個結(jié)點的入度比出度大1，另一個結(jié)點的入度比出度多1. 一個有向圖G是歐拉圖當且僅當G是連通的，且所有結(jié)點的入度等于出度。,8.4哈密爾頓圖,與歐拉圖類似的是哈密爾頓圖，它起源于環(huán)游世界的問題。 定義：若圖G的一個回路通過G中每個點一次，這樣的回路稱為哈密爾頓回路，有這種回路的圖稱為哈密爾頓圖。 顯然歐拉回路是簡單回路，無重復邊；哈密爾頓圖是基本回路，無重復點。,,關(guān)于如何判斷哈密爾頓通路與回路，至今尚未找到它的充要條件，只有一些充分條件和必要條件。,H-圖性質(zhì)定理,定理：設無向圖G=是哈密爾頓圖，非空集V1是V的子集，則P（G-V1）≤|V1|。 P（G-V1）是從G中刪去V1（包括與V1中結(jié)點相關(guān)聯(lián)的邊）后所得的圖的連通分支。 利用這個定理有時可證明一個圖不是哈密爾頓圖。P（G-V1） |V1|說明不是H-圖。,,定理：設G=是無向簡單圖，|V|≥3，如果G中每對結(jié)點次數(shù)之和大于等于|V|，則G必為哈密爾頓圖。 定理：設有向圖，|V| ≥2，若所有有向邊均用無向邊代替后，所得無向圖中含生成子圖Kn,則G存在哈密爾頓通路。 推論：n階有向完全圖(n2)為哈密爾頓圖。,判斷H-圖的一些充分或必要條件,H-圖一定是連通圖，且每個結(jié)點次數(shù)≥2。 若G是n階圖，則H-通路是長度為n-1的基本通路。 若存在次數(shù)為1的結(jié)點，則G沒有H-回路。 歐拉圖遍歷邊，哈密爾頓圖遍歷點。在H-圖中，H-回路不一定是唯一的。,8.5圖的矩陣表示,用矩陣的理論和分析方法來研究圖論，將圖的一些問題轉(zhuǎn)換為矩陣運算問題，更適合于計算機處理。 圖在計算機中就是以矩陣形式存貯和讀取的。 也可借助圖的理論和方法研究矩陣中的問題。,有向圖的鄰接矩陣,定義鄰接矩陣：設有向圖G=，設各點按一定次序排列，構(gòu)造矩陣 則稱A為圖G的鄰接矩陣。,零圖的鄰接矩陣：A為零矩陣。 完全圖的鄰接矩陣：A除對角線元素為0外，其余元素全為1。 無向圖的鄰接矩陣：將無向邊用兩條方向相反的有向邊代替，將無向圖轉(zhuǎn)成有向圖。 無向圖的鄰接矩陣是對稱陣。 鄰接矩陣的概念還可推廣到多重圖和帶權(quán)圖，考慮如何表示。,一個圖的鄰接矩陣完整的刻畫了圖中結(jié)點間的鄰接關(guān)系，但當結(jié)點次序發(fā)生變化時，對應的鄰接矩陣也隨之變化。一般將V強行排序，圖與鄰接矩陣就一一對應了。 同構(gòu)的兩個圖，對應結(jié)點間的鄰接關(guān)系相同，則它們的鄰接矩陣或者相同或者其中一個通過行、列交換可得到另一個。,,例子,有向圖的鄰接矩陣和次數(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 =(cij) ，cij表示從vi到vj存在的長度為k的通路的條數(shù)。,,例子,可達性矩陣,記Rn=A+A2++An=(rij)nn，由上一部分Ak的意義知，rij表示給出了從vi到vj的所有長度從1到n的通路的數(shù)目之和。 一般我們并不關(guān)心兩點之間有幾條通路，通路的長度是多少等等。 若rij=0，則表示從vi到vj是不可達的；若rij≠0，則vi到vj是可達的。 考慮：為什么計算到An即可判斷vi到vj是否可達？,,記 稱P為G的可達性矩陣或通路矩陣。 一個圖的可達矩陣給出了圖中各結(jié)點間是否可達及圖中是否有回路。,,例：求G=的可達矩陣， V、E如下 ： V={v1,v2,v3,v4}， E={(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v3,v1), (v4,v1)}。,解：,,由于根據(jù)Rn計算可達矩陣較復雜，在以后的計算中引入布爾運算。 例子：教材136頁例8.11是否存在遞歸調(diào)用？,多重圖及有權(quán)圖的矩陣表示,舉例說明。,矩陣與無向圖的連通性,設G為無向圖，由連通性定義知，任兩個結(jié)點都是可達的。 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’除對角線外其余元素均為1。,第九章常用圖,本章介紹圖論中幾種常用圖的基本原理和方法。 樹是圖論中重要概念之一，它在計算機科學中如算法分析、數(shù)據(jù)結(jié)構(gòu)等有廣泛應用。 平面圖 兩步圖,9.1樹,定義：樹是不包含回路的連通圖。 在樹中次數(shù)為1的結(jié)點稱為葉，次數(shù)大于1的結(jié)點稱為分支結(jié)點。 例,樹的定理,定理9.1：在（n,m）樹中，必有m=n-1。 證明：對n用歸納法。 定理9.2：具有兩個結(jié)點以上的樹必至少有兩片葉。 證明：用反證法、直接法兩種方法。 定理9.3：圖G是樹的充要條件是G的每對結(jié)點間只有一條通路。,樹的等價定義,設圖T=是（n,m）圖，T是樹。 T連通無回路。 T連通且m=n-1。 T無回路，且m=n-1。 T是最小連通圖。 T是最大無回路圖。 T的每對結(jié)點間恰有唯一一條通路。,有向樹,定義：在有向圖中若不考慮邊的方向而構(gòu)成樹，則稱為有向樹。 一般常用的有向樹為外向樹和內(nèi)向樹。,外向樹,定義外向樹：滿足下列條件的有向樹T稱為外向樹。 （1）T有且僅有一個根。（引入次數(shù)為0） （2）T的其它結(jié)點的引入次數(shù)均為1. （3）T有葉。（引出次數(shù)為0，當然引入次數(shù)仍為1） 定義：由外向樹的根到結(jié)點vi的通路長度稱為結(jié)點vi的級。,外向樹的相關(guān)概念,兩個結(jié)點如從根到結(jié)點的通路長度相等，則它們同級。否則不同級。 可用外向樹表示上面家屬關(guān)系。例子：紅樓夢人物簡表。雙親，兒子，祖先，子孫，兄弟。 從家屬樹中引入有序樹的概念。兄弟間有一定的次序。,定義內(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ì)與外向樹類似，故以后只考慮外向樹。,m元樹,定義：設有n個結(jié)點的外向樹T=，若 vi的引出次數(shù)≤m，稱T為m元樹；若除了葉外， vi的引出次數(shù)=m，則稱T為m元完全樹。 例：用二元樹表示算術(shù)表達式。 例：計算機中的程序流程圖也可用有序二元樹表示。,,二元樹的真正作用在于：任一外向樹均可用二元樹表示。 例子。,生成樹,定義：設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平面圖,定義平面圖：一個圖不管它的圖形的幾何形狀如何改變，它們的邊之間總有交叉現(xiàn)象出現(xiàn)，則稱此圖為非平面圖；否則稱為平面圖。 或定義：設G=是無向圖，若存在G的一種圖示，使得任意兩條邊不相交，則稱為平面圖。,,無回路的圖是平面圖。 有回路，無相交交叉邊，G是平面圖。 有回路有交叉邊，則將邊分別置于某基本回路的內(nèi)或外，然后判定是否是平面圖。,平面圖的區(qū)域,定義：設G是連通平面圖，由圖中的邊所包圍的最小平面塊稱為平面圖的區(qū)域。 包圍該區(qū)域的邊所構(gòu)成的回路稱為這個區(qū)域的邊界。 區(qū)域面積有限稱為有限區(qū)域；面積無限稱為無限區(qū)域。,,每個平面圖只有唯一一個無限區(qū)域。 一個平面圖將整個平面完全劃分。 例子,定理： （Euler定理） 設G是(n,m)連通平面圖，區(qū)域數(shù)為r,則有 n-m+r=2 證明：對m 進行歸納法證明。 m=1時，由G連通，n=2或n=1。 設m=k-1時，有n-m+r=2，證m=k時，G有n個結(jié)點，r個區(qū)域。有兩種情況：G有次數(shù)為1的結(jié)點；G沒有次數(shù)為1的結(jié)點。,定理：設G是一個(n,m)平面連通圖，且G中無環(huán)，m1，則必有 m≤3n-6。 證明：已知圖G的每個區(qū)域邊界的邊數(shù)至少為3。G中每條邊至多同時作為兩個不同區(qū)域邊界的邊。故有 3r ≤2m。 一個連通平面圖一般應滿足m≤3n-6，否則是非平面圖。,判斷定理,定義：基本縮減。 定理：一個圖是平面圖的充要條件是它的任何子圖都不可能縮減成下面的兩個圖：K5和K3,3 例子,9.3兩步圖,定義：設無向圖G=有兩個V的子集V1、V2，兩個相互分離，且滿足V1∪V2=V，圖G的每一邊e均有e=(vi,vj),其中vi∈V1,vj∈V2，稱G為兩步圖。 在G中，V被劃分為V1、V2，且在V1、V2內(nèi)各結(jié)點間無邊相連，故稱V1、V2為G的互補結(jié)點子集。,,定理：圖G是兩步圖的充要條件是G的所有回路長度均為偶數(shù)。,,例子,,,,,