第九章 常見圖(縮)

第九章常用圖本章主要介紹圖論中的幾種常用圖的基本原理與方法樹平面圖兩步圖9.1樹9.1.1樹及其基本性質(zhì)定義9.1(定義一)

樹是不包含回路的連通圖.次數(shù)為1的結(jié)點(diǎn)稱為葉,次數(shù)大于1的結(jié)點(diǎn)稱為分支結(jié)點(diǎn).有回路不連通是樹9.1.1樹及其基本性質(zhì)定理9.1

在(n,m)樹中必有m=n-1證明： 設(shè)有一(n,m)樹,由于其不包含任何回路,故從樹中刪去一邊后變成兩個(gè)互不相通的子圖,而其每個(gè)子圖則是連通的,故每個(gè)子圖均為樹,

設(shè)它們分別是(n1,m1)樹及(n2,m2)樹,如果m1=n1-1,m2=n2-1,

又由于n1+n2=n,m=m1+m2-1=n-1 n=1時(shí)定理成立.

由數(shù)學(xué)歸納法可得該定理成立.9.1.1樹及其基本性質(zhì)定理9.2

具有兩個(gè)結(jié)點(diǎn)以上的樹必至少有兩片葉.證明： 任何(n,m)圖的所有結(jié)點(diǎn)次數(shù)之和為2m,

對(duì)于樹而言則必為2n-2,

若存在某樹其葉少于2,

則此時(shí)其分支結(jié)點(diǎn)至少為n-1,

則此時(shí)樹的次數(shù)的和必大于2n-2.9.1.1樹及其基本性質(zhì)定理9.3

圖G是樹的充分必要條件是圖G的每對(duì)結(jié)點(diǎn)間只有一條通路.定義二： 圖G的每對(duì)結(jié)點(diǎn)間只有一條通路,則此類圖稱為樹.9.1.1樹及其基本性質(zhì)例：設(shè)圖G是一棵樹,它有n2個(gè)2次分支點(diǎn),n3個(gè)3次分支點(diǎn),…,nk個(gè)k次分支點(diǎn),求G中葉結(jié)點(diǎn)數(shù).解:

設(shè)G中葉結(jié)點(diǎn)數(shù)為x,

則G中結(jié)點(diǎn)數(shù)n=x+n2+n3+…+nk

邊數(shù)m=n-1=x+n2+n3+…+nk-1

所有結(jié)點(diǎn)之和 因此有x+2n2+3n3+…+knk=2m=2(x+n2+n3+…+nk-1) x=n3+2n4…+(k-2)nk+29.1.2有向樹定義9.2在有向圖中如果不考慮邊的方向而構(gòu)成樹,則稱此有向圖為有向樹.9.1.2有向樹定義9.3

滿足下列條件的有向圖T稱為外向樹: 1)T有一個(gè)結(jié)點(diǎn)(也僅有一個(gè))它的引入次數(shù)為0,這個(gè)結(jié)點(diǎn)稱為T的根; 2)T的其他結(jié)點(diǎn)的引入次數(shù)均為1; 3)T有一些結(jié)點(diǎn),它的引出次數(shù)為0----這些結(jié)點(diǎn)稱為T的葉.外向樹中,非根非葉的結(jié)點(diǎn)稱為分支結(jié)點(diǎn).9.1.2有向樹定義9.4

由外向樹的根到結(jié)點(diǎn)vi的通路長(zhǎng)度稱為結(jié)點(diǎn)vi的級(jí). v1的級(jí)為0,v2,v3的級(jí)為1,v4,v5,v6,v7的級(jí)為2,v8,v9的級(jí)為3.9.1.2有向樹例9.2：形式語言中可用外向樹表示對(duì)應(yīng)的文法G和句子的推理過程.例如,文法G的生成規(guī)則為：

<因子>::=i/(<表達(dá)式>) <項(xiàng)>::<因子>|<項(xiàng)>＊<因子> <表達(dá)式>::=<項(xiàng)>|<表達(dá)式>+<項(xiàng)>

則<表達(dá)式>+<項(xiàng)>＊<因子>可由上述的規(guī)則推出,其推導(dǎo)過程可用外向樹表示,此外向樹稱為語法樹.9.1.2有向樹例9.3：可用外向樹表示家屬關(guān)系設(shè)某人a生兩個(gè)兒子：b及c,b與c又分別生了3個(gè)兒子,他們分別為d,e,f及g,h,I,而d與g又分別生了一個(gè)兒子,它們是j和k,這樣的家屬關(guān)系可用外向樹表示,稱為家屬樹.9.1.2有向樹家屬樹中兄弟間是有一定次序的,在有些外向樹中需要對(duì)每個(gè)分支結(jié)點(diǎn)(及根)的順序編號(hào).9.1.2有向樹內(nèi)向樹：

1)T有一個(gè)結(jié)點(diǎn)(也僅有一個(gè))它的引出次數(shù)為0,這個(gè)結(jié)點(diǎn)稱為T的根; 2)T的其他結(jié)點(diǎn)的引出次數(shù)均為1; 3)T有一些結(jié)點(diǎn),它的引入次數(shù)為0----這些結(jié)點(diǎn)稱為T的葉.9.1.3二元樹定義9.5

一n個(gè)結(jié)點(diǎn)的外向樹如滿足:

則稱此外向樹為m元樹.

如滿足(除葉外)

則稱此外向樹為m元完全樹.當(dāng)m=2時(shí)則分別稱為二元書及二元完全樹.二元樹中,每個(gè)結(jié)點(diǎn)最多可以有兩個(gè)兒子,一般稱位于左邊的為左兒子,右邊的為右兒子.9.1.3二元樹四元樹：四元完全樹：9.1.3二元樹二元樹：二元完全樹：9.1.1樹及其基本性質(zhì)例：設(shè)G是二元完全樹,G有15個(gè)結(jié)點(diǎn),其中有8片樹葉,則G有__條邊,G的次數(shù)是__,G的除根外的分支點(diǎn)數(shù)是__,G中次數(shù)為3的結(jié)點(diǎn)數(shù)是__.解：

G是樹,結(jié)點(diǎn)數(shù)n=15,所以邊數(shù)m=n-1=14. G的次數(shù)=2m=28. G是二元完全樹,葉為8片,故G有一個(gè)根,次數(shù)為2,其余均為次數(shù)為3的分支點(diǎn)為15-8-1=6.

綜上,G有14條邊,G的次數(shù)是28,G的除根外的分支點(diǎn)數(shù)是6,G中次數(shù)為3的結(jié)點(diǎn)數(shù)是6.

9.1.3二元樹例9.4可用二元樹表示算術(shù)表達(dá)式,如

(v1-v2)/v3+v4(v5-v6/v7)可用下圖的有序二元樹表示9.1.3二元樹例9.5很多計(jì)算機(jī)中的程序流程圖可用有序二元樹表示.如下圖圖(a)中的流程圖即可用圖(b)中的有序二元樹表示.9.1.3二元樹對(duì)二元樹表示外向樹：對(duì)外向樹的結(jié)點(diǎn)從根開始逐級(jí)討論,每級(jí)從左到右順序討論,若一結(jié)點(diǎn)與前一結(jié)點(diǎn)是兄弟則在二元樹中作為前一結(jié)點(diǎn)的右兒子,若一結(jié)點(diǎn)是某一結(jié)點(diǎn)的最左邊兒子,則在二元樹中作為某一結(jié)點(diǎn)的左兒子.例9.69.1.4生成樹一個(gè)連通圖G=<V,E>的生成樹TG=<V’,E’>是G的一個(gè)子圖,它是樹,并且有V’=V,E’?E.由一個(gè)連通圖G尋找它的生成樹的過程是:

在G中尋找基本回路,找到后在此回路中刪除一邊,并繼續(xù)尋找,直至G中無基本回路出現(xiàn)為止.如果連通圖G是一個(gè)(n,m)圖,則可知TG是一個(gè)(n,n-1)圖,故由G求得TG必須刪除的邊數(shù)為m-(n-1)=m-n+1,這個(gè)數(shù)稱為G的基本回路的秩.

即G的基本回路的秩就是為了打斷它的所有基本回路必須從G中刪除的最小邊數(shù),每一條被刪除的邊叫做G的弦,所有弦的集合稱為生成樹T的補(bǔ).9.1.4生成樹例：試證明一棵二元完全樹必有奇數(shù)個(gè)結(jié)點(diǎn).證明： 設(shè)二元完全樹T有n個(gè)結(jié)點(diǎn),m條邊.依定義,T中每個(gè)分支結(jié)點(diǎn)都關(guān)聯(lián)兩條邊,所以m必為偶數(shù).

又因?yàn)門是樹,有n=m+1,故n為奇數(shù),因此二元完全樹必有奇數(shù)個(gè)結(jié)點(diǎn).9.1.4生成樹一個(gè)連通圖G的生成樹不是唯一的.9.1.4生成樹例9.8設(shè)有6個(gè)城市v1,v2,…,v6,它們間有輸油管連通,其布置圖如圖a所示,為了保衛(wèi)油管不受破壞,在每段油管間須派一連士兵看守,為保證正常供應(yīng),最少需多少連士兵看守？它們應(yīng)駐在哪些油管處？由圖可知此圖中n=6,m=11,故其生成樹的邊為5,即至少需五連士兵看守.其看守地段即該圖的生成樹,如圖(b).生成樹不是唯一的,(c)(d)亦可.9.1.4生成樹最小生成樹：?jiǎn)栴}： 如果給圖的每個(gè)邊賦予一個(gè)權(quán)(在上題中,該權(quán)即兩城市間的距離),尋找生成樹使得它的總長(zhǎng)度最短.尋找過程：對(duì)每條邊按距離長(zhǎng)短由短到長(zhǎng)順序排列按排列順序?qū)⑦吋尤雸D中,如出現(xiàn)回路,則刪去權(quán)最大的一個(gè)邊這樣加入n-1個(gè)邊即得最小生成樹9.1.4生成樹定義：最小生成樹:設(shè)G=<V,E,w>是一個(gè)邊賦權(quán)的連通無向圖,任取e∈E,e的權(quán)為實(shí)數(shù)w(e).若T是G的一棵生成樹,T中數(shù)值的權(quán)值之和稱為樹T的權(quán),記為.G的所有生成樹中,權(quán)最小的 那棵生成樹稱為圖G的最小生成樹.設(shè)T=<V’,E’>是G=<V,E>的一棵最小生成樹,經(jīng)典的最小生成樹算法有以下幾個(gè)：9.1.4生成樹1.Kruskal算法 首先將E中的邊按權(quán)值由小到大排序,得到邊的有序序列S. 1)令i=1,E’={S[1]}; 2)令i=i+1,選取邊S[i],如果S[i]與E’中的邊不構(gòu)成簡(jiǎn)單回路,則令E’=E’∪{S[i]}; 3)重復(fù)步驟(2),直到|E’|=|V|-1為止.9.1.4生成樹9.1.4生成樹9.1.4生成樹2.Prim算法

1)從V中任意選取一個(gè)結(jié)點(diǎn)v0,令V’={v0}; 2)在V’與V-V’之間選一條權(quán)最小的邊e=(vi,vj),其中vi∈V’,vj∈V-V’.

并且令E’=E’∪{e},V’=V’∪{vj}; 3)重復(fù)步驟(2),直到V’=V為止.9.1.4生成樹3.破圈法

1)令E’=E; 2)選取E’中的一條簡(jiǎn)單回路C,設(shè)C中權(quán)最大的邊為e,令E’=E’-{e}; 3)重復(fù)步驟(2),直到|E’|=|V|-1為止.

即不停地選取圖G中的一條簡(jiǎn)單回路,從回路中刪去權(quán)值最大的一條片,直到圖中無簡(jiǎn)單回路為止.9.2平面圖9.2.1平面圖的基本概念最少交叉點(diǎn)是一個(gè).9.2.1平面圖的基本概念定義9.6

一個(gè)圖不管它的圖形的幾何形狀如何變化,它們的邊之間總有交叉現(xiàn)象出現(xiàn),則稱此圖為非平面圖,否則稱為平面圖.直觀判定法：無回路的圖一定是平面圖,故研究圖的平面性問題僅對(duì)有回路的圖而言.有回路的圖中總可以找到一些不相交叉的基本回路來,當(dāng)一圖中有些邊產(chǎn)生交叉時(shí),可以用一些不同的方法將交叉的邊分別放置在某基本回路內(nèi)或某基本回路外.只有當(dāng)各放置方法均避免不了邊的交叉時(shí),才說明此圖是非平面圖.9.2.1平面圖的基本概念9.2.1平面圖的區(qū)域平面圖中四周為邊所包圍的最小平面塊稱為平面圖的區(qū)域而包圍區(qū)域的回路稱為此區(qū)域的邊界區(qū)域面積為有限者稱為有限區(qū)域

區(qū)域面積為無限者稱為無限區(qū)域.9.2.1平面圖的區(qū)域面的次數(shù):

設(shè)r是連通平面圖G的一個(gè)面,面r的邊界回路長(zhǎng)度稱為該面的次數(shù),記為deg(r).一個(gè)平面圖有一個(gè)唯一的無限區(qū)域一個(gè)平面圖按區(qū)域?qū)⒄麄€(gè)平面完全劃分定理:設(shè)G=<V,E>是一個(gè)連通平面圖,則圖G中所有面的次數(shù)之和等于邊數(shù)的兩倍,即9.2.2平面圖的區(qū)域定理9.4(歐拉公式)

設(shè)圖G是一個(gè)(n,m)連通平面圖,它的區(qū)域數(shù)為r,則此時(shí)有n-m+r=2.定理9.5

設(shè)圖G是一個(gè)(n,m)連通平面圖,且圖G中無環(huán),其邊數(shù)大于1,則必有m≤3n-6.如一個(gè)連通無環(huán)邊數(shù)大于1的圖G不滿足定理9.5,則可判斷該圖是非平面圖.9.2.2平面圖的區(qū)域例：傳說歐洲有個(gè)國(guó)王生有五個(gè)兒子,在臨死前留下遺囑,將自己的土地分給了這五個(gè)兒子.五個(gè)王子在各自的領(lǐng)地上分別修筑了宮殿,并且想在每?jī)勺鶎m殿間都修建一條直達(dá)的道路,并且要求任意兩條道路都不交叉.問他們的愿望能實(shí)現(xiàn)嗎?

如左圖,n=5,m=10 m>3n-6,

故是非平面圖 所以不能實(shí)現(xiàn).9.2.2平面圖的區(qū)域例:設(shè)連通簡(jiǎn)單平面圖G有20個(gè)結(jié)點(diǎn),如果G是3次正則圖,那么它將平面分割成多少個(gè)不同的區(qū)域?解:

圖G的結(jié)點(diǎn)數(shù)n=20.

圖G是3次正則圖，故每個(gè)結(jié)點(diǎn)的次數(shù)均為3,則有2m=3n=60,得m=30.

根據(jù)歐拉公式

r=m-n+2=30-20+2=12.

所以平面圖G將平面分割成了12個(gè)不同的區(qū)域.9.2.3判別平面圖的

庫拉托夫斯基定理基本減縮：在一個(gè)圖G=<V,E>中將邊(vi1,vj1),(vi2,vj2),…,(vik,vjk)刪除,并分別將結(jié)點(diǎn)vi1,與vj1,vi2與vj2,…,vik與vjk