離散數(shù)學(xué)圖與樹_第1頁
離散數(shù)學(xué)圖與樹_第2頁
離散數(shù)學(xué)圖與樹_第3頁
離散數(shù)學(xué)圖與樹_第4頁
離散數(shù)學(xué)圖與樹_第5頁
已閱讀5頁,還剩53頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

第六章樹及其應(yīng)用樹是圖論中最重要的概念之一。它在許多領(lǐng)域中,特別是在計算機學(xué)科中得到了廣泛的應(yīng)用.本章介紹無向樹及有向樹的概念、性質(zhì)及其應(yīng)用.注意:①本章所談回路均指初級回路即圈或簡單回路即閉跡.②在圖論中討論的樹,有些術(shù)語來源于自然界的樹.6.1無向樹6.1.1無向樹的定義及其性質(zhì)定義6.1.1連通不含回路的無向圖稱無向樹,簡稱為樹.常用T表示一棵樹.平凡圖稱為平凡樹.若非連通無向圖的每一連通分支都是樹(分支數(shù)p≥2),則稱其為森林.設(shè)T=<V,E>是一棵樹.v

V,若d(v)=1,則稱v為T的樹葉,若d(v)≥2,則稱v為分支點。無向樹的定義及其性質(zhì)例圖中的①為平凡樹,②為由兩棵樹組成的森林,③為一棵無向樹:樹有多個等價的定義或性質(zhì),以下定理中的各命題都體現(xiàn)樹的特征或性質(zhì).定理6.1.1

設(shè)G=<V,E>是n階無向圖,|E|=m.則以下命題等價(它們的每一個都可以作為樹的定義):(1)G為樹(即G連通不含回路);(2)G的每對頂點之間有唯一的一條路徑;(3)G連通且m=n-1;(4)G中無回路且m=n-1;(5)G中無回路,但在G的任一對不相鄰頂點上加一新邊后就惟一產(chǎn)生一條初級回路;(6)G連通,但刪去任何一邊后所得圖不再連通(G邊為橋).

①②③樹葉分支點無向樹的定義及其性質(zhì)證明:

(1)=>(2).設(shè)u,v是G中兩個頂點,G是樹具有連通性,u,v之間有通路,因而必有路徑.若路徑多于兩條,就形成回路,這與G中無回路矛盾.

(2)=>(3).由于G中任意兩個頂點之間均有路徑,所以任意兩個頂點都是連通的,故G是連通圖.下面用第二數(shù)學(xué)歸納法證明m=n-1.

當n=0時,G為平凡樹,m=0,結(jié)論顯然成立.

設(shè)n≤k(k≥1)時結(jié)論成立,證明n=k+1時結(jié)論也成立.設(shè)e=(u,v)為G中一條邊,由(2)知,u,v之間除路徑uv外,再無別的通路,因而G-e得2個連通分支G1和G2.設(shè)它們的頂點數(shù)與邊數(shù)分別為n1,n2;m1,m2.易知n1≤k且n2≤k.由歸納假設(shè)得m1=n1-1,m2=n2-1.從而得m=m1+m2+1=n1-1+n2-1+1=n-1.

(3)=>(4).只需證明G中無回路.若G中有回路,從回無向樹的定義及其性質(zhì)

路中刪去任意一條邊后,所得圖仍然連通.若所得圖中還有回路,再從回路中刪除一條邊,直到所得圖中無回路為止.設(shè)共刪去r(r≥1)條邊所得圖為G’.G’無回路,但仍為連通圖即G’是樹.由(1)=>(2)=>(3)知,G’中m’=n’-1.而n’=n,m’=m-r.于是得m=n-1+r(r≥1),這與條件m=n-1矛盾.

(4)=>(5).由條件(4)易證G是連通的.否則設(shè)G有k(k≥2)個連通分支G1,G2,…,Gk.由(4)知,Gi(1≤i≤k)都是樹.設(shè)Gi有mi條邊,ni個頂點,則由(1)=>(2)=>(3)知,mi=ni-1(1≤i≤k).于是n=n1+n2+…+nk=m1+1+m2+1+

…+mk+1=m+k(k≥2).這與m=n-1矛盾.因而G是連通的,又知是無回路的,即G是樹.由(1)=>(2)知,G中任意兩個不相鄰頂點u和v之間存在惟一的路徑Puv.Puv再加新邊(u,v)形成惟一的圈.無向樹的定義及其性質(zhì)

(5)=>(6).首先證明G是連通圖.否則,設(shè)G1,G2是G的兩個連通分支.v1和v2分別是G1與G2中的一個頂點.在G中加邊(v1,v2)不形成回路,這與已知條件矛盾.若G中存在邊e=(u,v),G-e仍連通.說明在G-e中存在u到v的通路.

此通路與e構(gòu)成G中回路,這與G中無回路矛盾.(6)=>(1).只需證明G中無回路.若G中含回路C.在C上刪除一邊e后,G-e連通,這與(6)中條件矛盾.除了由定理6.1.1.給出的樹的充分必要條件外,樹還有下述重要的必要條件.定理6.1.2

設(shè)T=<V,E>是非平凡的無向樹,則T至少有兩片樹葉.證明:設(shè)T是非平凡樹,有n個頂點m條邊.由樹的定義易知,非平凡的樹中,每個頂點的度數(shù)均大于等于1.設(shè)G中有k個1度頂點,即k片樹葉,則其余n-k個分支點的度數(shù)均大無向樹的定義及其性質(zhì)

于等于2,由握手引理可知

k+2(n-k)≤=2m,由定理6.1.1知m=n-1,代入上式得k+2(n-k)≤2n-2,即k≥2.例6.1.1

設(shè)無向樹T中有4度、3度、2度的分支點各1個,其余的頂點為樹葉,問T中有幾片樹葉?又問滿足T中度序列的無向樹在同構(gòu)的意義下是惟一的嗎?解:

設(shè)T有x片樹葉,則T有x+3個頂點.由定理6.1.1知,T有(x+3)-1條邊,再由握手引理x+2+3+4=2(x-2),解得x=5.即T有5片樹葉.度序列相同的樹不同構(gòu)。如圖,不同構(gòu)的2

棵樹的度序列都為1,1,1,1,1,2,3,4.無向樹的定義及其性質(zhì)例6.1.2

(1)

畫出全部不同構(gòu)的6階無向樹;

(2)

畫出度序列為1,1,1,2,2,2,3的所有非同構(gòu)的7階無向樹樹.解:

設(shè)所求樹的頂點數(shù)為n,邊數(shù)為m.由題設(shè)已知n=6.①由無向樹的性質(zhì)可知m=n-1=5;②樹是簡單圖,其頂點的度滿足1≤d(vi)≤5,i=1,2,3,4,5;③由握手引理可知,=10.將10度分配6個頂點,滿足上述條件,有5種方案:5,1,1,1,1,1;4,2,1,1,1,1;3,3,1,1,1,1;3,2,2,1,1,1和2,2,2,2,1,1(為什么?).不同度序列對應(yīng)不同構(gòu)的樹,但相同度序列可能對應(yīng)不止一棵樹.方案3,2,2,1,1,1對應(yīng)2棵非同構(gòu)的樹,這由3度頂點是否夾在兩個2度頂點之間而定.其余方案各對應(yīng)1棵樹.無向樹的定義及其性質(zhì)

所得6棵非同構(gòu)的樹如圖所示:

(2)畫出所有非同構(gòu)的無向樹不是件易事,但當n較小時還是不難畫出的.本題是7階非同構(gòu)無向樹度數(shù)分配方案中的一種,它有3個2度頂點,1個3度頂點,3個1度頂點,3度頂點與1個2度頂點相鄰;與2個2度頂點相鄰;與3個2度頂點相鄰,所得3棵樹顯然非同構(gòu),所以共有3棵非同構(gòu)的樹:生成樹與基本回路和基本割集6.1.2生成樹與基本回路和基本割集定義6.1.2

設(shè)G=<V,E>是無向連通圖.若樹T是G的生成子圖,則稱T是G的生成樹。G在T中的邊稱為T的樹枝。G不在T中的邊稱為T的弦.T所有弦的集合的導(dǎo)出子圖稱為T的余樹.余樹未必連通,也未必不含回路.因而余樹不一定是樹,更不一定是生成樹。圖中②為①的生成樹,③為②的余樹:生成樹與基本回路和基本割集定理6.1.3

任何無向連通圖G都存在生成樹.證明:若G中無回路,則G本身就是G的生成樹.若G中含有回路C,在C中任意刪去一條邊,不影響圖的連通性.若所得圖中還有回路,就在此回路中刪去一條邊,繼續(xù)這個過程,直到所得圖中無回路為止.設(shè)最后的圖為T,則T是G的生成樹.由定理6.1.3可得以下3個推論.推論1.無向連通圖G的生成樹在下述兩種意義下都不一定是惟一的(如圖所示):

①非同構(gòu)意義下;即兩棵生成樹存在不同的邊就認為它們是不同的.

②在同構(gòu)的意義下;即連通圖G可存在非同構(gòu)的生成樹.推論2.設(shè)n階無向簡單連通圖G中有m條邊,則m≥n-1.生成樹與基本回路和基本割集證明:由定理6.1.3,G中存在生成樹T.設(shè)T有m’條邊,m’=n-1.因而m≥m’=n-1.推論3.設(shè)n階無向連通圖G中有m條邊,T是G的一棵生成樹,T’是T的余樹,則T’有m-n+1條邊,T有m-n+1條弦(為什么).例6.1.3

給出下圖中①的兩棵非同構(gòu)的生成樹,并指出它們的樹枝和弦。解:圖中②和③深綠色邊所示的圖都是圖①的生成樹,

顯然它們是非同構(gòu)的.e2,e3,e4,e5為T②的樹枝,e1,e6為弦;e1,e2,e4,e5為T③的樹枝,e3,e6為弦.在②中加弦e1;e6分別產(chǎn)生初級回路e3e1e4e2和e6e4e5.在③中加弦e3;e6分別產(chǎn)生初級回路e3e1e4e2和e6e4e5.這些回路的共同特點是:它們中均只含1條弦,其余的邊都是生成樹與基本回路和基本割集

樹枝.稱這樣的回路為基本回路.定義如下:定義6.1.3

設(shè)G是m條邊的n階連通圖,T是G的一棵生成樹,T的m-n+1條弦為e1,e2,…,em-n+1.G中僅含T的一條弦er(1≤r≤m-n+1)的回路Cr稱作對應(yīng)弦er的基本回路.{C1,C2,

…,Cm-n+1}稱作對應(yīng)生成樹T的基本回路系統(tǒng).在例6.1.3中,樹②對應(yīng)弦e1的基本回路是e1e4e2e3;對應(yīng)弦e6的基本回路是e6e4e5.基本回路系統(tǒng)為:{e1e4e2e3,e6e4e5}.樹③的基本回路系統(tǒng)是{e3e1e4e2,e6e4e5}.一般,G的不同生成樹的基本回路可能不同,但基本回路的個數(shù)是相同的,都等于m-n+1.再看例6.1.3圖②,{e5,e6},{e4,e1,e6},{e2,e1},{e3,e1}

是圖中的4個割集,它們有一個共同的特點,每個割集中生成樹與基本回路和基本割集

都有且只有1條樹枝,其余邊均為弦.稱這樣的割集為生成樹T②對應(yīng)的基本割集.下面是其一般定義.定義6.1.4設(shè)T是n階連通圖G的一棵生成樹,e1,e2,…,en-1為T的樹枝.設(shè)Sr是只含樹枝er(1≤r≤n-1),其余邊均為弦的割集.稱Sr為對應(yīng)樹枝er的基本割集,{S1,S2,…,Sn-1}為對應(yīng)T的基本割集系統(tǒng).一般,G的不同生成樹的基本割集可以不同,但基本割集的個數(shù)是相同的,都等于n-1.在例6.1.3中,對應(yīng)生成樹③也有4個基本割集:{e5,e6},{e4,e3,e6},{e2,e3},{e1,e3}.由它們組成的集合,就是③

的基本割集系統(tǒng).例6.1.4

在題圖G中,深綠色邊構(gòu)成G的生成樹T.求對應(yīng)T的基本回路和基本生成樹與基本回路和基本割集

割集系統(tǒng).解:G的頂點數(shù)n=6,邊數(shù)m=9,基本回路個數(shù)為m-n+1=4;基本割集個數(shù)為n-1=5.T的4條弦為e,b,c,i.它們對應(yīng)的基本回路分別是:Ce=edfg,Cb=bda,Cc=cadfgh,Ci=igh.

基本回路系統(tǒng)為{Ce,Cb,Cc,Ci}.T的5條樹枝是a,d,f,g,h.所對應(yīng)的基本割集分別是:Sa={a,b,c},Sd={d,e,b,c},Sf={f,e,c},Sg={g,e,i,c},Sh={h,i,c}.基本割集系統(tǒng)為{Sa,Sd,Sf,Sg,Sh}.你能找出求樹枝e’對應(yīng)的基本割集的方法嗎?(將e’從T

中刪除.T-e’有兩個連通分支,記為T1,T2.設(shè)V1,V2為T1,T2的頂點集.則e’對應(yīng)的基本割集Se’={e|e∈E(G)∧e的一個端點在V1中,一個端點在V2中}.無向連通圖G的怎樣的邊不在G的任何生成樹中,怎樣的邊必在G的每個生成樹中?(環(huán);橋或割邊)最小生成樹6.1.3最小生成樹現(xiàn)在我們討論最小生成樹問題。先看一個例子:假定要修建連接n個城市的公路網(wǎng),已知連接城市vi與vj的公路造價是wij,要求設(shè)計公路網(wǎng)使總造價最小。如果把城市看成頂點,公路看成邊,公路的造價wij看成是邊的權(quán),則該問題就是在一個賦權(quán)無向連通圖中求一棵權(quán)最小的生成樹.定義6.1.5

設(shè)G為無向連通賦權(quán)圖,T是G的一棵生成樹,T的各邊的權(quán)的和稱為T的權(quán),記作W(T).G的所有生成樹中權(quán)最小的一棵生成樹稱為G的最小生成樹。最小生成樹亦稱最優(yōu)樹。設(shè)G=<V,E,W>是賦權(quán)無向連通圖.求G的生成樹T,使得權(quán)W(T)=最小.圖G是有限圖,只有有限棵生成樹,故最優(yōu)樹總是存在的.

最小生成樹1956年克拉斯科(J.Kruskal)給出了求解上述問題的一個算法.這個算法稱為Kruskal算法,其步驟如下:☆輸入賦權(quán)無向連通圖G=<V,E,W>,其中|V|=n.①取G的非環(huán)邊,使得W(e)最小;

②邊e1,e2,…,ek選定后,從E-{e1,e2,…,ek}中選邊ek+1滿足以下兩個條件:

(a)G[{e1,e2,…,ek+1}]不含圈,及

(b)

在滿足(a)的前提下W(ek+1)最??;

③當②不能進行時,則算法停止并輸出G[{e1,e2,…,ek}].上述Kruskal算法求最優(yōu)樹的方法,稱避圈法.下面是由

Kruskal算法求最優(yōu)樹的具體例釋:對最優(yōu)樹算法的例釋

**Kruskal算法的輸出一定是G的最優(yōu)樹嗎?以下定理從理論上回答了這個問題.**定理6.6.4

Kruskal算法輸出的T*=G[{e1,e2,…,ek}]是賦權(quán)連通無向圖G的一棵最優(yōu)樹.**Kruskal算法證明:

首先證明當算法終止時T*一定是G的生成樹.若G[{e1,e2,…,ek}]不是G的生成樹,則由算法知它是一森林.

這樣由G的連通性知,總可以在E-{e1,e2,…,ek}中選邊

ek+1使得G[{e1,e2,…,ek,ek+1}]無圈且W(ek+1)最小.這樣算法會進行下去直到G[{e1,e2,…,ek}]是生成樹,即k=n-1時為止.

若T*不是最優(yōu)樹,則在全部最優(yōu)樹中選最優(yōu)樹T,使T與T*的公共邊數(shù)最大.因T*不是最優(yōu)樹,T*≠T.設(shè)在T*的邊集{e1,e2,…,en-1}中不屬于T的下標最小的邊為ek,由定理知T+ek包含圈C,因T*是樹,故C中有不屬于T*的邊e,顯然

e是T的邊.因而T’=(T+ek)-e是G的生成樹.因ek是T*中不屬于T的下標最小的邊,故e1,e2,…,ek-1既是T*中的邊也是T中的邊.因e不是T*的邊,故e

E-{e1,e2,…,ek-1}.又**Kruskal算法

因e是T中的邊,所以e1,e2,…,ek-1,e都是T中的邊.于是

G[{e1,e2,…,ek-1,e}]不含圈.

當克拉斯科算法進行到第k步時,e和ek都屬于E-{e1,e2,

…,ek-1}又G[{e1,e2,…,ek-1,e}]和G[{e1,e2,…,ek-1,ek}]

都不含圈,由算法②中的(b)可知W(ek)≤W(e),從而W(T’)=W(T)+W(ek)-W(e)≤W(T),故T’也是G的一棵最優(yōu)樹.但

T’與T*的公共邊數(shù)比T與T*的公共邊數(shù)多1,這與T的選擇矛盾.求最優(yōu)樹的算法不止一種.下面給出的是稱為破圈法的最優(yōu)樹算法.☆輸入賦權(quán)無向連通圖G=〈V,E,W〉.

①選取e1,使得W(e1)最大且G-e1連通;②當Gk=G-{e1,e2,…,ek}選定時,在E-{e1,e2,…,ek}**Kruskal算法

中選邊ek+1滿足以下兩個條件:

(a)Gk+1=G-{e1,…,ek,ek+1}連通,及

(b)

在滿足(a)的前提下,W(ek+1)最大;

③當步驟②不能進行時輸出Gh=G-{e1,…eh}.不難證明,這一算法的輸出Gh是G的一棵最優(yōu)樹.上面所介紹的兩個算法分別被形象地稱為避圈法與破圈法.這兩個算法有一共同特點,就是在過程中的每一步都取目前最為有利的選擇.這種只顧眼前的最佳選擇而不顧整體效果如何的算法,稱之為貪婪型算法.需要指出的是:一般,貪婪型算法并不一定總能給出問題的最優(yōu)解。根樹及其應(yīng)用6.2根樹及其應(yīng)用

一個有向圖D,如果D的基礎(chǔ)圖是無向樹,則稱D為有向樹.在有向樹中,最為重要的是根樹,它在諸如數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)庫等專業(yè)課程中占據(jù)著極其重要的位置。6.2.1根樹及其分類定義6.2.1

一棵非平凡的有向樹,如果有一個頂點的入度為0,其余頂點的入度均為1,則稱此有向樹為根樹.在根樹中,稱入度為0的頂點為樹根;稱入度為1,出度為0的頂點為樹葉;稱入度為1,出度大于0的頂點為內(nèi)點;內(nèi)點和樹根統(tǒng)稱為分支點。右圖中的①是一棵根樹,

②是根樹①的簡圖(①的基礎(chǔ)圖,是一般根樹圖)。樹根樹葉內(nèi)點分支點根樹及其分類

在根樹T中,樹根到任一頂點v的路長稱為v的層數(shù),記作

l(v),層數(shù)最大頂點的層數(shù)稱為樹高,記作h(v).h(v)為根樹T的高度。上頁附圖所示根樹T中,有0,1,2,3共4層,樹高為3.

一棵根樹可以看作一棵家族樹:若頂點a鄰接到頂點b則稱b為a的兒子,a為b的父親;若b,c的父親相同,則稱b,c為兄弟;若a≠d,而a可達d,則稱a為d的祖先,d為a的后代.

在根樹T中,稱由一個非根頂點a及其后代導(dǎo)出的子圖T’為T的以a為根的根子樹。上述概念,從前頁附圖所示根樹T中,都可顯然指定.在應(yīng)用中,往往將根樹同層上的頂點或它們所關(guān)聯(lián)的邊排序(次序可全標在頂點處,也可以全標在邊上,標序數(shù)不要求一定是連續(xù)的數(shù)),這樣的根樹稱為有序樹。根樹及其分類根據(jù)根樹各分支點兒子的多少以及頂點是否排序,可將根樹分類:

設(shè)T是非平凡的根樹.如果T的每個分支點至多有r個兒子,則稱T為r元樹;如果T的每個分支點都恰有r個兒子,則稱T為r元正則樹,進而,若所有樹葉的層數(shù)都為樹高,則稱T為r元完全正則樹.如果T還是有序樹,則相應(yīng)稱之為r元有序樹,r元有序正則樹和r元有序完全正則樹。在所有r-元樹中,2元樹最重要,在數(shù)據(jù)結(jié)構(gòu)中稱2叉樹.下面討論2元樹的應(yīng)用.6.2.2最優(yōu)樹與哈夫曼(Huffman)算法定義6.2.2

設(shè)2元樹T有t片樹葉v1,v2,…,vt,權(quán)分別為w1,w2,…,wt,稱W(T)=為T的權(quán),其中l(wèi)(vi)是vi的層數(shù).在所有含有t片樹葉,帶權(quán)w1,w2,…,wt的2元樹中,最優(yōu)樹與哈夫曼算法

權(quán)最小的2元樹稱最優(yōu)2元樹。附圖中,給出了帶權(quán)1,3,4,5,6

的4棵2元樹:其權(quán)分別為47,54,43和42(由哈夫曼算法將知,權(quán)為42的第四棵2元樹為最優(yōu)2元樹).

☆Huffman算法給定遞增實數(shù)列:w1≤w2≤…≤wt.

①連接權(quán)為w1,w2的兩片樹葉,得一分支點,其權(quán)為w1+w2;

②在w1+w2,w3…,wt中選出兩個最小的權(quán),連接它們對應(yīng)的頂點(不一定是樹葉),得新分支點及所帶的權(quán);最優(yōu)樹與哈夫曼算法

③重復(fù)②,直到形成t-1個分支點,t片樹葉為止。例6.2.1

求帶權(quán)為1,3,4,5,6的最優(yōu)2元樹,

并計算它的權(quán).解:為了熟悉哈夫曼算法,右圖將計算最優(yōu)樹的過程分步驟給出.所得最優(yōu)樹是圖中排在最右的一棵樹,其權(quán)W(T)=42.在計算機通信事業(yè)中,常用二進制碼表示字符.例如用00,01,10,11分別表示A,B,C,D.稱這種表示法為等長表示法.在傳輸過程中,若A,B,C,D出現(xiàn)的頻率相等,用等長的表示法是很好的表示法.但當它們出現(xiàn)的頻率并不根樹及其應(yīng)用

相同時,譬如A占50%,B占25%,C占20%,D只占5%,能否找到非等長的表示法,既能節(jié)省二進制數(shù)位,又能實現(xiàn)準確無誤地傳輸?這就是下面要討論的所謂前綴碼.6.2.3最佳前綴碼定義6.2.3

設(shè)是長度為n的符號串,稱其串,

分別為該符號串的長度為1,2,…,n-1的前綴.設(shè)符號串集合A={}.若對于任意的βi,βj∈A,i≠j,βi,βj都互不為前綴,則稱A為前綴碼.如果A中符號串都以0,1兩個符號構(gòu)成,則稱A為二元前綴碼。例如{1,01,001,000},{00,10,11,011,0100,0101}都是二元前綴碼.而{1,01,111,1100}不是前綴碼,因為1是111和1100的前綴。如何產(chǎn)生二元前綴碼?可用2元樹產(chǎn)生二元前綴碼.最佳前綴碼給定一棵有t片樹葉的2元樹T.設(shè)v為T的一個分支點,則v至少有一個兒子,至多有兩個兒子.若v有兩個兒子,在由引出的兩條邊上,左邊的標上0,右邊的標上1.若v只有一個兒子,在由v引出的邊上可標上0,也可標上1.設(shè)vi是T的任意一片樹葉,從樹根到vi的通路上各邊的標號組成的0,1符號串放在vi處,t片樹葉處的t個符號串組成的集合為一個2元前綴碼.由以上的作法看出,vi處的符號串的前綴均在vi所在的通路上除vi外的頂點處達到,因而所得符號串集合為2元前綴碼.特別若T存在帶一個兒子的分支點,則由T產(chǎn)生的前綴碼可能不惟一,但若T為正則2元樹,則由T產(chǎn)生的2元前綴碼是惟一的.此即定理6.2.1

由一棵給定的2元正則樹,

可以產(chǎn)生惟一的一個二元前綴碼。右圖所示2元正則樹產(chǎn)生的前綴碼為:{00,10,11,010,0110,0111}.根樹及其應(yīng)用若已知要傳輸符號的頻率,用各符號出現(xiàn)頻率的100倍當權(quán),用Huffman算法求最優(yōu)二叉樹T,則稱由T產(chǎn)生的前綴碼為最佳前綴碼.用最佳前綴碼傳輸對應(yīng)的符號,可以使傳輸?shù)亩M制位數(shù)最省。例6.2.2

設(shè)在通信中八進制數(shù)字出現(xiàn)的頻率為:7-5%,6-5%,5-5%,4-10%,3-10%,2-15%,1-20%,0-30%.求傳輸它們的最佳前綴碼。解:用100乘各頻率,并寫成遞增序得:w1=5,w2=5,w3=5,W4=10,w5=10,w6=15,w7=20,w8=30,它們與7,6,5,4,3,2,1,0分別對應(yīng).用哈夫曼算法求最優(yōu)2元樹如圖所示:

圖中方框內(nèi)的八個碼字組成的集合是最佳前綴碼.根樹及其應(yīng)用

8個碼字傳輸數(shù)字的對應(yīng)情況是:01-0,11-1,001-2,100-3,101-4,0001-5,00001-6,00000-7.注意:除了等長的碼字可以互換(如0與1的碼字,2,3,4的碼字,6,7的碼字)外其余的碼字不可互換.顯然一旦碼字與傳輸?shù)臄?shù)字定下來以后,等長的碼字也是不能互換的。6.2.4根樹的周游及其應(yīng)用

若對于一棵根樹的每個頂點都訪問一次且僅訪問一次,則稱為行遍或周游一棵樹。對于2元有序正則樹,主要有以下3種周游或行遍方法:①中序行遍法.其訪問次序為:左子樹,樹根,右子樹;②前序行遍法.其訪問次序為:樹根,左子樹,右子樹;③后序行遍法.其訪問次序為:左子樹,右子樹,樹根.對下頁圖的根樹按中序,前序,后序的周游結(jié)果分別為:根樹及其應(yīng)用(db(hei))a(fcg),a(bd(ehi))(cfg),(d(hie)b)(fgc)a.利用2元有序樹可以表達算式,然后根據(jù)不同的訪問方法得到不同的算法.利用2元有序樹存放算式時,

在每一步上都要將算式(或其子式)的最高層次的運算放在樹根(或子樹的樹根)上,將參加運算的數(shù)放在樹葉上,并規(guī)定被除數(shù)、在左子樹樹葉上。例6.2.3

①用2元有序樹表示算式((a-b*c)*d+e)÷(f*g+h).②用3種行遍法訪問該2元有序樹.解:①的解如圖.②中序:((a-b*c)*d+e)÷(f*g+h);前序:÷+*-a*bcde+*fgh(稱波蘭符號法);后序:abc*-d*e+fg*h+÷(稱逆波蘭符號法)。對第六章樹及其應(yīng)用的小結(jié)定義部分:無向樹、森林、平凡樹、樹葉、分支點,生成樹、樹枝、弦、余樹,最優(yōu)樹,基本回路和基本割集,根樹,r元樹;定理部分:關(guān)于樹定價的(6條)定理,平凡樹至少有兩片樹葉定理,無向連通圖存在生成樹定理及其三條推論,2元正則樹產(chǎn)生惟二元前綴碼定理;算法部分:Kruskal算法,Huffman算法;術(shù)語部分:避圈法與破圈法,貪婪算法;例題部分:關(guān)于樹中的度,在連通賦權(quán)圖中求最優(yōu)樹,基本回路和基本割集,根樹及應(yīng)用的例.第六章樹及其應(yīng)用的課后作業(yè)1.畫出互不同構(gòu)的6棵6階樹.2.證明:Δ(T)≥k的樹T至少含有k片樹葉.3.證明階數(shù)大于等于2的連通無向圖中至少有兩個頂點,將它們刪除之后得到的圖仍是連通圖.4.在賦權(quán)無向連通圖G中有一長為k的圈C,且C上每一邊的權(quán)皆取最小值.證明G中至少有k棵不同的最優(yōu)樹.**6.3超圖離散數(shù)學(xué)的一項基本任務(wù)是研究集合的各類有限子集族的結(jié)構(gòu)和性質(zhì)。這些子集族通常具有實際的應(yīng)用背景和優(yōu)美的數(shù)學(xué)結(jié)構(gòu)。所謂超圖實際上就是有限集合上的有限子集族。人們之所以將其稱為超圖主要是強調(diào)處理這類數(shù)學(xué)對象時的數(shù)學(xué)觀點,數(shù)學(xué)語言和研究方法。它們大多是圖論式的,是圖論中的概念和方法非常自然的推廣。用圖論的語言描述這類問題往往具有直觀和易于把握本質(zhì)的特點??梢园褵o向圖理解為在有限集合上,由一元子集與二元子集構(gòu)成的子集族,所以超圖是無向圖的一個自然的推廣。超圖理論在各類學(xué)科中有著廣泛的應(yīng)用。如在計算機學(xué)科中,有關(guān)數(shù)據(jù)庫結(jié)構(gòu)的研究,以及很多優(yōu)化問題的算法都是以超圖理論為理論基礎(chǔ)的.本節(jié)討論超圖的一些最基本的概念和性質(zhì)。

超圖定義6.3.1

設(shè)V={v1,v2,…,vn}是一有限集合,V上的一個超圖H是V上的一個子集族(E1,E2,…,Em),其中Ei滿足①

Ei≠φ,1≤i≤m;②稱vi(1≤i≤n)為超圖H的頂點,Ei(1≤i≤m)為超圖H的邊,n稱為超圖H的階。注意:超圖的邊并不要求互異。超圖H=(E1,E2,…,Em)稱是簡單的,若Ei

Ej=>i=j.超圖

H=(E1,E2,…,Em)稱為r-均勻的,如果|Ei|=r(1≤i≤m).若超圖H=(E1,E2,…,Em)滿足|Ei|≤2(1≤i≤m),則H即為一個無向圖。反之任何一個無孤立頂點的無向圖都是一個超圖。定義6.3.2

設(shè)H=(E1,E2,…,Em)是V={v1,v2,…,vn}上的超圖.定義矩陣AH=(aij)n×m如下:超圖

vi

Ej

,vi

Ej.則稱AH為超圖H的關(guān)聯(lián)矩陣。也可用平面上的圖形來表示一個超圖.將v1,v2,…,vn用平面上的n個小圓圈表示.如果Ei={v},則Ei用過v的一個環(huán)來表示.如果E={u,v},則Ei用連接u與v的線段來表示.如果|Ei|≥3,則Ei用恰包含Ei中點的閉曲線表示。圖21給出了超圖H的圖形和該超圖的關(guān)聯(lián)矩陣:

超圖定義6.3.3

設(shè)H=(E1,E2,…,Em)是V={v1,v2,…,vn}上的超圖。令:V*={e1,e2,…,em},Vi={ej|vi∈Ej},1≤i≤n.則

H*=(V1,V2,…,Vn)是V*上的超圖,稱為H的對偶超圖。圖22給出了圖21中超圖的對偶超圖的圖形及其關(guān)聯(lián)矩陣:超圖容易看出,H*的關(guān)聯(lián)矩陣是H的關(guān)聯(lián)矩陣AH的轉(zhuǎn)置,即.因而有(H*)*=H.

設(shè)H=(E1,E2,…,Em),r(H)=,則分別稱之為超圖H的秩與反秩。若r(H)=s(H),則H是均勻超圖。

設(shè)H是V上的超圖.由H定義V上的簡單圖(H)2:u,v(u≠v)

在(H)2中有邊相連

存在H的邊E,使得u,v∈E.稱(H)2是超圖H的二截圖.當(H)2連通時,稱H是連通的.H的連通分支數(shù)定義為(H)2的連通分支數(shù)。

設(shè)H=(E1,E2,…,Em)是V上的一個超圖.定義V*={e1,e2,…,em}上的圖L(H)為:ei與ej在L(H)中相連

Ei∩Ej≠φ,則稱L(H)為H的代表圖或線圖。

超圖很多超圖的線圖都是有趣的圖類。

設(shè)H是V上的超圖.P=v0E1v1E2…Ekvk是H中的頂點與邊的交替序列.如果vi(0≤i≤k)彼此不同,Ei(1≤i≤k)亦彼此不同且vi-1,vi∈Ei(1≤i≤k),則稱P是H中的一條長為k的從v0到vk的路.如果v0=vk,k≥2且其它頂點邊均互異,

則稱P是一個長為k的圈.注意:只包含一個頂點的邊在超圖中不稱為圈.

顯然超圖H是連通的

H中任意兩頂點之間都有路相連.定理6.3.1n階連通超圖H=(E1,E2,...,Em)中不存在圈

.證明:作二部圖G(H).取H的頂點做為G(H)的一組頂點.取H的邊做為G(H)的另一組頂點.在G(H)中vi與Ej相鄰當且僅當vi∈Ej.圖G(H)共有m+n個頂點,條邊.注意到

超圖

超圖H無圈

G(H)無圈,H連通

G(H)連通.故H是無圈連通超圖

G(H)連通無圈,即G(H)是樹.設(shè)G(H)的邊數(shù)與頂點數(shù)分別為:m(G(H))和n(G(H)),則由樹的一組等價定義知,連通圖G(H)是樹當且僅當m(G(H))=n(G(H))-1,即:或.

設(shè)H=(E1,E2,…,Em)是V上的超圖.如果,并且對任意的邊Ei

,T∩Ei≠φ,則稱T是H的一個橫截或一個徑集.若T是H的橫截,但對,T-{x}都不是H的橫截,則稱T是H的一個極小橫截。

設(shè)T1,T2,…,Tk是H的全部互異的極小橫截,則易證(T1,T2,

…,Tk)是V上一個簡單超圖,稱H的橫截超圖,記為Tr(H).例6.3.1設(shè)V是一個n元集合.由V的全部r(1≤r≤n)元子集構(gòu)成的超圖稱為V上的完全r均勻超圖,記為.顯然共有(n,r)條邊.容易驗證,任何一個具有n-r+1個頂

超圖

點V的子集,都是超圖的1個極小橫截,∴.我們引出下述定理,但不加證明:定理6.3.2

若H是一個簡單超圖,則Tr(Tr(H))=H.從定理5.3.2立得,對任意超圖H與F,Tr(H)=F

Tr(F)=H利用該結(jié)果可以解決下述有趣問題:例6.3.2

保險柜鑰匙問題。國家某安全部門每個成員的保密級分別為1,2,…,k,共k個級別.規(guī)定當在場的成員保密級別之和大于等于r時就可以打開機密文件保險柜.該機密文件柜的鎖和鑰匙應(yīng)該如何配備?解:

該安全部門成員構(gòu)成一個有限集合V.每一個可以打開文件柜的成員小組構(gòu)成V的一個子集。設(shè)全部能打開文件柜的成員的極小組分別是E1,E2,…,Em

(即Ei(1≤i超圖

≤m)組成員的保密級別之和大于等于r,但對任一v

Ei,Ei-v成員組的保密級別之和小于r),則H=(E1,E2,…,Em)

構(gòu)成了一個超圖.設(shè)Tr(H)=(F1,F2,…Fh),則Tr(H)就給出了一個鎖和鑰匙的配置方案.共用h把鎖,將第i把鎖的鑰匙分配給Fi組中的人.那么部門任何成員小組E,只要它含有Ei(1≤i≤m)之一必能打開文件柜,否則它將一定不能打開文件柜.為了說明這一點只需證明Ei(1≤i≤m)是超圖(F1,F2,…,Fh)的全部極小橫截,因為這時包含某個Ei的成員有每一把鎖的鑰匙,而不包含任一Ei(1≤i≤m)的成員小組,必定缺少某把鎖的鑰匙.即是要證明Tr((F1,F2,…,Fh))=H.但已知Tr(H)=(F1,F2,

…,Fh),因而由定理2知:Tr((F1,F2,…,Fh)=Tr(Tr(H))=H.

超圖☆所以解決這一問題的實際步驟是:

①構(gòu)造超圖H;②計算超圖Tr(H)(已有現(xiàn)成的算法).☆如果安全部門共有n個成員,并規(guī)定只要有r個人在場就可打開文件柜,那么這個問題的答案是簡單的.這時H=Knr,Tr(H)=Knn-r+1,即需要配置Cnn-r+1把不同的鎖,且每把鎖需有n-r+1把鑰匙.n個成員中的每n-r+1個成員的不同小組每一組的同組成員都恰好得到同一把鎖的鑰匙,就是本問題鎖與鑰匙的配置方案.超圖小結(jié)定義部分:n元集上的超圖H,超圖H的關(guān)聯(lián)矩陣,對偶超圖,超圖H的秩與反秩,2截超圖及其連通性,超圖H中長為k的路和圈,超圖的橫截與極小橫截,橫截超圖;定理部分:連通超圖無圈的充要條件,簡單超圖與極小橫截;例題部分:均勻超圖的極小橫截,保險柜鑰匙問題.建議作業(yè):練習(xí)8-8(P255)(1)(2)(3)(4).課程作業(yè)總括一、命題邏輯基本概念部分1.構(gòu)造一個只含命題變元P,Q,R的命題公式,使之當P,Q為真R為假時該命題公式為真,否則為假.2.構(gòu)造一個只含命題變元P,Q,R的命題公式,使之當P,Q和

R恰有兩個為真時該命題公式為真,否則為假.3.將下述電話系統(tǒng)規(guī)范寫成命題符號形式:

如果電話號碼數(shù)據(jù)庫是打開的,那么監(jiān)督程序被置于關(guān)閉狀態(tài),只要系統(tǒng)不在初態(tài)(首先將原子命題設(shè)為命題標識符,然后恰當使用邏輯聯(lián)詞形成公式).4.證明定理1.1:命題公式A=B當且僅當A

B是永真式。5.運用真值表方法證明:

①?(P∨(?P∧Q))與?P∧?Q邏輯等值;課程作業(yè)總括

②P∧Q→P∨Q是重言式.6.復(fù)習(xí)(理解并區(qū)分)以下概念:

邏輯等值式;重言式(永真式);矛盾式(永假式);一般可滿足式。二、命題邏輯等值演算部分1.按提示和要求證明異或具有以下性質(zhì):

①PQ=QP(真值表法).②P

(QR)=(PQ)

R(等值推演并用①).③P∧(QR)=(P∧Q)

(P∧R)(考慮改∧為∨).④PP=F,FP=P,TP=?P(由定義).⑤若PQ=R,則QR=P,RP=Q,進而PQR=0(等值替換并用①,②).課程作業(yè)總括2.用邏輯聯(lián)詞或非式等值表示與非式P↑Q.3.用等值演算法證明P→Q=?Q→?P.4.證明P↑(Q↑R)≠(P↑Q)↑R以及P↓(Q↓R)≠(P↓Q)↓R(即證↑與↓不具有結(jié)合律).三、范式部分1.寫出含有3個命題變元的極大項或極小項(所求布爾項的腳標是十進制腳標):m0,

M0;m7,

M7;m5,M5.2.設(shè)命題公式G(P,Q,R)的主析取范式為

P∧

Q∧

R,求

命題公式

G(P,Q,R)的主析取范式和主合取范式.3.求命題公式(

(P→Q)∨R)∧(F→R)的對偶式.4.由范式判定命題公式P→P∧(Q→P).5.求命題公式P∧(Q∨

R)的主析取范式和主合取范式.課程作業(yè)總括6.在校田徑運動會上四位短跑好手A,B,C,D同組比賽,甲,

乙,丙三位觀眾同學(xué)猜名次.甲猜A第一,B第二;乙猜C

第二,D第三;丙猜A第二,D第四.如果三位同學(xué)都只猜對了一項,求四位短跑好手的實際名次.四、命題邏輯推理部分1.在推理系統(tǒng)P中證明:小王學(xué)過英語或日語。如果小王學(xué)過英語,則他去過英國。如果他去過英國,他也去過日本。所以小王學(xué)過日語或去過日本。2.在推理系統(tǒng)P中證明:如果周靜是上海人,則她是復(fù)旦大學(xué)或中山大學(xué)的學(xué)生。如果她不想離開上海,她就不是中山大學(xué)學(xué)生。周靜是上海人并且不想離開上海。所以她是復(fù)旦大學(xué)學(xué)生。課程作業(yè)總括五、一階邏輯的公式與分類部分1.符號化命題“不存在可導(dǎo)但不連續(xù)的函數(shù)”.2.符號化命題“每個人的外公都是她母親的父親”.3.符號化命題“在美國留學(xué)的學(xué)生未必都是亞洲人”.4.熟練掌握課程講習(xí)所舉的11個例子和復(fù)習(xí)講習(xí)所舉的5

個做解釋的例子.5.深入理解對一階謂詞公式的解釋的概念.六、一階邏輯等值演算部分1.求一階公式

(x)((y)G(x,y)→(x)(y)(H(x,y)∧(y)(G(y,x)→H(x,y))))的前束范式.2.求1.中公式的司寇倫范式.3.給出一階公式(x)(y)G(x,y)與其司寇倫范式(y)G(課程作業(yè)總括a,y)不邏輯等值的一種解釋I.七、一階邏輯推理理論1.在自然推理系統(tǒng)F中,構(gòu)造以下證明:

每個大學(xué)生或者享有獎學(xué)金或者交費學(xué)習(xí).每個大學(xué)生當且僅當學(xué)習(xí)評優(yōu)才享有獎學(xué)金.有些大學(xué)生學(xué)習(xí)被評優(yōu),但并非所有大學(xué)生學(xué)習(xí)都能被評優(yōu).因此,有些大學(xué)生要交費學(xué)習(xí).八、證明技巧部分1.用數(shù)學(xué)歸納法證明:前n個正奇數(shù)之和為n2.2.用數(shù)學(xué)歸納法證明:?n∈Z+,3|(n3-n).3.用數(shù)學(xué)歸納法證明:?n∈Z+,n!≥2n-1.4.證明命題“對于每個正整數(shù)n,都存在n個連續(xù)的正合數(shù)”.課程作業(yè)總括九、集合及其表示法部分1.用集合演算的第①種方法證明:對任意集合A,B有

(1)A∩E=A.(2)A∩~A=φ.(3)A-B=A∩~B.(4)A

A∪B.(5)A∩BA.2.用集合演算的第②種方法證明:對任意集合A,B,C有A-(B∪C)=(A-B)∩(A-C).十、一般二元關(guān)系部分1.證明:①A×(B∪C)=(A×B)∪(A×C);②A×(B∩C)=(A×B)∩(A×C).課程作業(yè)總括自反性反自反對稱性反對稱傳遞性集合表達式關(guān)系矩陣關(guān)系圖自反性反自反性對稱性反對稱性傳遞性R-1R∩SR∪SR-SRS舉反例舉反例舉反例舉反例舉反例舉反例舉反例舉反例2.按照要求填表:3.按照要求填表:課程作業(yè)總括4.設(shè)R是非空集合A上的自反關(guān)系.證明:R在A上對稱且傳遞當且僅當成立若〈a,b〉〈a,c〉∈R,則〈b,c〉∈R.5.設(shè)R,S,T分別是A到B,B到C和C到D的二元關(guān)系,證明(二元關(guān)系關(guān)于復(fù)合具有結(jié)合律):(RS)T=R(ST).十一、等價關(guān)系與劃分部分1.設(shè)A={1,2,3},R={〈1,2〉,〈2,3〉,〈3,1〉},求r(R),s(R),t(R),sr(R),tr(R)和ts(R).2.設(shè)P(x):x≥3是整數(shù)集合I上的一元謂詞.在I上定義關(guān)系R:iRjP(i)=P(j).證明R是I

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論