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

下載本文檔

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

文檔簡(jiǎn)介

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

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

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

①②③樹(shù)葉分支點(diǎn)無(wú)向樹(shù)的定義及其性質(zhì)證明:

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

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

當(dāng)n=0時(shí),G為平凡樹(shù),m=0,結(jié)論顯然成立.

設(shè)n≤k(k≥1)時(shí)結(jié)論成立,證明n=k+1時(shí)結(jié)論也成立.設(shè)e=(u,v)為G中一條邊,由(2)知,u,v之間除路徑uv外,再無(wú)別的通路,因而G-e得2個(gè)連通分支G1和G2.設(shè)它們的頂點(diǎn)數(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中無(wú)回路.若G中有回路,從回?zé)o向樹(shù)的定義及其性質(zhì)

路中刪去任意一條邊后,所得圖仍然連通.若所得圖中還有回路,再?gòu)幕芈分袆h除一條邊,直到所得圖中無(wú)回路為止.設(shè)共刪去r(r≥1)條邊所得圖為G’.G’無(wú)回路,但仍為連通圖即G’是樹(shù).由(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)個(gè)連通分支G1,G2,…,Gk.由(4)知,Gi(1≤i≤k)都是樹(shù).設(shè)Gi有mi條邊,ni個(gè)頂點(diǎn),則由(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是連通的,又知是無(wú)回路的,即G是樹(shù).由(1)=>(2)知,G中任意兩個(gè)不相鄰頂點(diǎn)u和v之間存在惟一的路徑Puv.Puv再加新邊(u,v)形成惟一的圈.無(wú)向樹(shù)的定義及其性質(zhì)

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

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

設(shè)T=<V,E>是非平凡的無(wú)向樹(shù),則T至少有兩片樹(shù)葉.證明:設(shè)T是非平凡樹(shù),有n個(gè)頂點(diǎn)m條邊.由樹(shù)的定義易知,非平凡的樹(shù)中,每個(gè)頂點(diǎn)的度數(shù)均大于等于1.設(shè)G中有k個(gè)1度頂點(diǎn),即k片樹(shù)葉,則其余n-k個(gè)分支點(diǎn)的度數(shù)均大無(wú)向樹(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è)無(wú)向樹(shù)T中有4度、3度、2度的分支點(diǎn)各1個(gè),其余的頂點(diǎn)為樹(shù)葉,問(wèn)T中有幾片樹(shù)葉?又問(wèn)滿足T中度序列的無(wú)向樹(shù)在同構(gòu)的意義下是惟一的嗎?解:

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

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

(1)

畫(huà)出全部不同構(gòu)的6階無(wú)向樹(shù);

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

是圖中的4個(gè)割集,它們有一個(gè)共同的特點(diǎn),每個(gè)割集中生成樹(shù)與基本回路和基本割集

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

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

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

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

基本回路系統(tǒng)為{Ce,Cb,Cc,Ci}.T的5條樹(shù)枝是a,d,f,g,h.所對(duì)應(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}.你能找出求樹(shù)枝e’對(duì)應(yīng)的基本割集的方法嗎?(將e’從T

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

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

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

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

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

(b)

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

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

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

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

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

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

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

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

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

e是T的邊.因而T’=(T+ek)-e是G的生成樹(shù).因ek是T*中不屬于T的下標(biāo)最小的邊,故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}]不含圈.

當(dāng)克拉斯科算法進(jìn)行到第k步時(shí),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)樹(shù).但

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

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

中選邊ek+1滿足以下兩個(gè)條件:

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

(b)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

設(shè)是長(zhǎng)度為n的符號(hào)串,稱其串,

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

由一棵給定的2元正則樹(shù),

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

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

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

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

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

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

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

超圖定義6.3.1

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

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

Ej=>i=j.超圖

H=(E1,E2,…,Em)稱為r-均勻的,如果|Ei|=r(1≤i≤m).若超圖H=(E1,E2,…,Em)滿足|Ei|≤2(1≤i≤m),則H即為一個(gè)無(wú)向圖。反之任何一個(gè)無(wú)孤立頂點(diǎn)的無(wú)向圖都是一個(gè)超圖。定義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)矩陣。也可用平面上的圖形來(lái)表示一個(gè)超圖.將v1,v2,…,vn用平面上的n個(gè)小圓圈表示.如果Ei={v},則Ei用過(guò)v的一個(gè)環(huán)來(lái)表示.如果E={u,v},則Ei用連接u與v的線段來(lái)表示.如果|Ei|≥3,則Ei用恰包含Ei中點(diǎn)的閉曲線表示。圖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的對(duì)偶超圖。圖22給出了圖21中超圖的對(duì)偶超圖的圖形及其關(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上的簡(jiǎn)單圖(H)2:u,v(u≠v)

在(H)2中有邊相連

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

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

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

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

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

則稱P是一個(gè)長(zhǎng)為k的圈.注意:只包含一個(gè)頂點(diǎn)的邊在超圖中不稱為圈.

顯然超圖H是連通的

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

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

超圖

超圖H無(wú)圈

G(H)無(wú)圈,H連通

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

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

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

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

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

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

超圖

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

若H是一個(gè)簡(jiǎn)單超圖,則Tr(Tr(H))=H.從定理5.3.2立得,對(duì)任意超圖H與F,Tr(H)=F

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

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

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

(即Ei(1≤i超圖

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

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

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

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

超圖☆所以解決這一問(wèn)題的實(shí)際步驟是:

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

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

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

B是永真式。5.運(yùn)用真值表方法證明:

①?(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,進(jìn)而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.寫(xiě)出含有3個(gè)命題變?cè)臉O大項(xiàng)或極小項(xiàng)(所求布爾項(xiàng)的腳標(biāo)是十進(jìn)制腳標(biāo)):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)的對(duì)偶式.4.由范式判定命題公式P→P∧(Q→P).5.求命題公式P∧(Q∨

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

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

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

個(gè)做解釋的例子.5.深入理解對(duì)一階謂詞公式的解釋的概念.六、一階邏輯等值演算部分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)造以下證明:

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

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

A∪B.(5)A∩BA.2.用集合演算的第②種方法證明:對(duì)任意集合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è)總括自反性反自反對(duì)稱性反對(duì)稱傳遞性集合表達(dá)式關(guān)系矩陣關(guān)系圖自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R-1R∩SR∪SR-SRS舉反例舉反例舉反例舉反例舉反例舉反例舉反例舉反例2.按照要求填表:3.按照要求填表:課程作業(yè)總括4.設(shè)R是非空集合A上的自反關(guān)系.證明:R在A上對(duì)稱且傳遞當(dāng)且僅當(dāng)成立若〈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).十一、等價(jià)關(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. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論