離散下-習(xí)題課

11/23/11第十一章，格和布爾代數(shù)例：設(shè)S110={1,2,5,10,11,22,55,110}是110的所有因數(shù)的集合,令glb,lub是最大公約數(shù)和最小公倍數(shù)運(yùn)算。下面簡記為glb—*,lub—證明<S110,*,>是一個(gè)布爾代數(shù)。證明:110=1×2×5×11質(zhì)因子分解式中因子是不重復(fù)的。記(x)為x分解的質(zhì)因數(shù)的集合,例(55)={1,5,11}。而12=1×2×2×3,質(zhì)因子分解中,因子是重復(fù)的。<S110,D>的哈斯圖與<S30,D>,<P(A),>,A={a,b,c}是完全相同的。容易驗(yàn)證,交換律顯然成立。

11/23/11第十一章，格和布爾代數(shù)x,y,z∈S110,x*(yz)=(x)∩((y)∪(z))=((x)∩(y))∪((x)∩(z))=(x*y)(x*z)同理x(y*z)＝(xy)*(xz)分配律成立。顯然1是S110的最小元,110是S110的最大元。x*110=x,x1=x,同一律成立。11/23/11第十一章，格和布爾代數(shù)記﹁x=110/x,因110中質(zhì)因數(shù)分解中質(zhì)因數(shù)不重復(fù)。故﹁x與x的質(zhì)因數(shù)沒有重復(fù)的。∴﹁x*x=1,﹁xx=(﹁x)∪(x)=110互補(bǔ)律是成立,∴<S110,*,,﹁,1,110>是布爾代數(shù)。第十一章，格和布爾代數(shù)本章的主要知識(shí)點(diǎn)有：格的代數(shù)性質(zhì)；基于格的布爾代數(shù)定義方法；布爾代數(shù)的同態(tài)、同構(gòu)；幾種特殊的布爾代數(shù).本章的學(xué)習(xí)需要注意如下幾點(diǎn)：格是一種非常重要的代數(shù)結(jié)構(gòu),

它與集合論中介紹的偏序關(guān)系緊密相關(guān),

本章中僅僅介紹了格的基本概念以及為討論布爾代數(shù)而介紹了兩種特殊的格,

但這也是以后根據(jù)需要進(jìn)一步學(xué)習(xí)格論的基礎(chǔ).

學(xué)習(xí)格,

重點(diǎn)應(yīng)在于理解格的概念,

以及討論格是一種代數(shù)結(jié)構(gòu)的思路.

此外,

理解相關(guān)證明的基本思路也是非常重要的.本章習(xí)題類型主要有概念題、判斷題,

如布爾代數(shù)的概念及其判斷,

以及證明題,

如證明等式、某代數(shù)結(jié)構(gòu)是布爾代數(shù)或格等.

這些都需要抓住基本概念,

以及基本性質(zhì)進(jìn)行直接證明.

此外,

由于對(duì)布爾代數(shù)的討論中指出了其元素的原子表達(dá)式以及基集的基數(shù)性質(zhì),

在習(xí)題中主要反映為解答題的形式來深化這些知識(shí)點(diǎn).練習(xí)1下面那些構(gòu)成格，那些不能？練習(xí)2設(shè)L是模12加群<Z12,>的子群格，給出L的所有4元子格。書上187書上習(xí)題218,第3題練習(xí)3設(shè)R為實(shí)數(shù)集，其中K0=K2=0,K1=K3=-1,K4=-2。令S={At|t=0,1,2,3,4}。畫出偏序集的哈斯圖并求其極大，極小，最大，最小元。說明該偏序集構(gòu)成什么格？練習(xí)4設(shè)B是布爾代數(shù)，證明：在格<L；≤>中,

如果a≤b≤c,

則有

1)aúb=bùc

2)(aùb)ú(bùc)=b=(aúb)ù(aúc)證明：格<L；≤>中,

對(duì)任意a,b,c,d∈L,

有

1)(aùb)ú(cùd)≤(aúc)ù(búd).

2)(aùb)ú(bùc)ú(cùa)≤(aúb)ù(búc)ù(cúa).9第十四章圖的基本概念主要內(nèi)容無向圖、有向圖、關(guān)聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu)通路與回路及其分類無向圖的連通性與連通度有向圖的連通性及其分類圖的矩陣表示10基本要求深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系記住通路與回路的定義、分類及表示法深刻理解與無向圖連通性、連通度有關(guān)的諸多概念會(huì)判別有向圖連通性的類型熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣9階無向圖G中，每個(gè)頂點(diǎn)的度數(shù)不是5就是6.證明G中至少有5個(gè)6度頂點(diǎn)或至少有6個(gè)5度頂點(diǎn).練習(xí)5證關(guān)鍵是利用握手定理的推論.方法一：窮舉法設(shè)G中有x個(gè)5度頂點(diǎn)，則必有(9x)個(gè)6度頂點(diǎn)，由握手定理推論可知，(x,9x)只有5種可能：(0,9),(2,7),(4,5),(6,3),(8,1）它們都滿足要求.方法二：反證法否則，由握手定理推論可知，“G至多有4個(gè)5度頂點(diǎn)并且至多有4個(gè)6度頂點(diǎn)”，這與G是9階圖矛盾.數(shù)組2,2,2,2,3,3能簡單圖化嗎？若能，畫出盡可能多的非同構(gòu)的圖來.練習(xí)6只要能畫出6階無向簡單圖，就說明它可簡單圖化.下圖的4個(gè)圖都以此數(shù)列為度數(shù)列，請(qǐng)證明它們彼此不同構(gòu)，都是K6的子圖.P293,習(xí)題17,23練習(xí)7用擴(kuò)大路徑法證明.情況一：

+.證明D中存在長度

+1的圈.設(shè)

=v0v1…vl為極大路徑，則l

(為什么?).由于d(v0)

，所以在

上存在PLAY鄰接到v0，于是情況二：+

，只需注意d+(vl)

+.設(shè)D=<V,E>為有向簡單圖，已知(D)2，+(D)>0，(D)>0，證明D中存在長度max{+,}+1的圈.為D中長度

+1的有向圈練習(xí)8(1)D中有幾種非同構(gòu)的圈？(2)D中有幾種非圈非同構(gòu)的簡單回路？(3)D是哪類連通圖?(4)D中v1到v4長度為1,2,3,4的通路各多少條？其中幾條是非初級(jí)的簡單通路？(5)D中v1到v1長度為1,2,3,4的回路各多少條？討論它們的類型.(6)D中長度為4的通路（不含回路）有多少條？(7)D中長度為4的回路有多少條？(8)D中長度4的通路有多少條？其中有幾條是回路？(9)寫出D的可達(dá)矩陣.4．有向圖D如圖所示，回答下列諸問：練習(xí)916解答(1)D中有3種非同構(gòu)的圈，長度分別為1,2,3，請(qǐng)畫出它們的圖形.(2)D中有3種非圈的非同構(gòu)的簡單回路，它們的長度分別為4,5,6.請(qǐng)畫出它們的圖形來.(3)D是強(qiáng)連通的（為什么？）為解(4)—(8)，只需先求D的鄰接矩陣的前4次冪.

17(4)v1到v4長度為1,2,3,4的通路數(shù)分別為0,0,2,2.其中只有長度為4的兩條是非初級(jí)的簡單通路（定義意義下），見下圖所示.解答18解答(5)v1到v1長度為1,2,3,4的回路數(shù)分別為1,1,3,5.其中長度為1的是初級(jí)的(環(huán))；長度為2的是復(fù)雜的；長度為3的中有1條是復(fù)雜的，2條是初級(jí)的；長度為4的有1條是復(fù)雜的，有4條是非初級(jí)的簡單回路.請(qǐng)?jiān)趫D中行遍以上各回路.(6)長度為4的通路(不含回路)為33條.(7)長度為4的回路為11條.(8)長度4的通路88條，其中22條為回路.(9)44的全1矩陣.19第十五章歐拉圖

主要內(nèi)容歐拉通路、歐拉回路、歐拉圖、半歐拉圖及其判別法哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖帶權(quán)圖、貨郎擔(dān)問題基本要求深刻理解歐拉圖、半歐拉圖的定義及判別定理深刻理解哈密頓圖、半哈密頓圖的定義.會(huì)用哈密頓圖的必要條件判斷某些圖不是哈密頓圖.會(huì)用充分條件判斷某些圖是哈密頓圖.要特別注意的是，不能將必要條件當(dāng)作充分條件，也不要將充分條件當(dāng)必要條件.201.設(shè)G為n（n2）階無向歐拉圖，證明G中無橋方法二：反證法.利用歐拉圖無奇度頂點(diǎn)及握手定理的推論.否則，設(shè)e=(u,v)為G中橋，則Ge產(chǎn)生兩個(gè)連通分支G1,G2，不妨設(shè)u在G1中，v在G2中.由于從G中刪除e時(shí)，只改變u,v的度數(shù)(各減1)，因而G1與G2中均只含一個(gè)奇度頂點(diǎn)，這與握手定理推論矛盾.練習(xí)1方法一：直接證明法.命題(*)：設(shè)C為任意簡單回路，e為C上任意一條邊，則Ce連通.證設(shè)C為G中一條歐拉回路，任意的eE(C)，可知Ce是Ge的子圖，由()知Ce連通，所以e不為橋.212.

證明下圖不是哈密頓圖.(破壞必要條件)方法一.利用定理15.6，取V1={a,c,e,h,j,l}，則p(GV1)=7>|V1|=6練習(xí)2方法二.G為二部圖，互補(bǔ)頂點(diǎn)子集V1={a,c,e,h,j,l},V2={b,d,f,g,i,k,m}，|V1|=67=|V2|.方法三.利用可能出現(xiàn)在哈密頓回路上的邊至少有n(n為階數(shù))條——這也是哈密頓圖的一個(gè)必要條件，記為（）.此圖中，n=13，m=21.由于h,l,j均為4度頂點(diǎn)，a,c,e為3度頂點(diǎn)，且它們關(guān)聯(lián)邊互不相同.而在哈密頓回路上，每個(gè)頂點(diǎn)準(zhǔn)確地關(guān)聯(lián)兩條邊，于是可能用的邊至多有21(32+31)=12.這達(dá)不到（）的要求.223．某次國際會(huì)議8人參加，已知每人至少與其余7人中的4人有共同語言，問服務(wù)員能否將他們安排在同一張圓桌就座，使得每個(gè)人都與兩邊的人交談？解圖是描述事物之間關(guān)系的最好的手段之一.做無向圖G=<V,E>,其中

V={v|v為與會(huì)者}，E={(u,v)|u,vV且u與v有共同語言，且u

v}.易知G為簡單圖且vV,d(v)4，于是，u,vV,有d(u)+d(v)8，由定理15.7的推論可知G為哈密頓圖.服務(wù)員在G中找一條哈密頓回路C，按C中相鄰關(guān)系安排座位即可.練習(xí)3由本題想到的：哈密頓回圖的實(shí)質(zhì)是能將圖中所有的頂點(diǎn)排在同一個(gè)圈中.234.距離(公里)如圖所示.他如何走行程最短？

練習(xí)4最短的路為ABCDA，距離為36公里，其余兩條各為多少？24第十六章習(xí)題課主要內(nèi)容無向樹及其性質(zhì)生成樹、最小生成樹、基本回路系統(tǒng)、基本割集系統(tǒng)根樹及其分類、最優(yōu)樹、最佳前綴碼、波蘭符號(hào)法、逆波蘭符號(hào)法基本要求深刻理解無向樹的定義及性質(zhì)熟練地求解無向樹準(zhǔn)確地求出給定帶權(quán)連通圖的最小生成樹深刻理解基本回路、基本割集的概念，并會(huì)計(jì)算理解根樹及其分類等概念會(huì)畫n階（n較?。┓峭瑯?gòu)的無向樹及根樹（1n6）熟練掌握求最優(yōu)樹及最佳前綴碼的方法掌握波蘭符號(hào)法與逆波蘭符號(hào)法25（2）（3）從而解出練習(xí)11.無向樹T有ni個(gè)i度頂點(diǎn)，i=2,3,…,k，其余頂點(diǎn)全是樹葉，求T的樹葉數(shù).解用樹的性質(zhì)：邊數(shù)m=n1（n為階數(shù)），及握手定理.(1)262．設(shè)n階非平凡的無向樹T中，(T)

k，k1.證明T至少有k片樹葉.證反證法.否則，T至多有s片樹葉，s<k，下面利用握手定理及樹的性質(zhì)m=n1推出矛盾.由于(T)

k，故存在v0，d(v0)

k.于是，由此解出s

k，這與s<k矛盾.證本題的方法有多種，請(qǐng)用分支點(diǎn)都是割點(diǎn)來證明.練習(xí)2273．設(shè)G為n階無向簡單圖，n5，證明G或中必含圈.本題的方法很多，證明中用：G與邊數(shù)之和為Kn的邊數(shù)，以及樹的性質(zhì)：m=n1.

方法一.反證法.否則G與的各連通分支都是樹.設(shè)G與的連通分支分別為G1,G2,…,Gs和G1,G2,…,Gs.令ni,mi與nj,mj

分別為Gi,Gj的頂點(diǎn)數(shù)和邊數(shù).于是得n25n+40，解出1

n4,矛盾于n5.練習(xí)328方法二.在G與中存在一個(gè)，比如說G，它的邊數(shù)用反證法證明G中必含圈.比方法一簡單.