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

《離散數(shù)學(xué)-圖論.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)-圖論.ppt（93頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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