蘇XI友離散數(shù)學(xué)作業(yè)ppt課件

1、作業(yè)作業(yè) 13P173-7.1 下列各組數(shù)中下列各組數(shù)中,哪些能構(gòu)成無(wú)向圖的哪些能構(gòu)成無(wú)向圖的度數(shù)列度數(shù)列?哪些能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列哪些能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列?(1)1,1,1,2,3.能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列.例如例如,(2)3,3,3,3.可以構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列可以構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列,例如例如,作業(yè)作業(yè) 13(3)1,3,3,3.(3)1,3,3,3.不能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列不能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)列. .因因?yàn)橛幸粋€(gè)懸掛點(diǎn)為有一個(gè)懸掛點(diǎn), ,則其余三個(gè)頂點(diǎn)度數(shù)不可能則其余三個(gè)頂點(diǎn)度數(shù)不可能均為均為3,3,但可構(gòu)成無(wú)向圖的度數(shù)列但可構(gòu)成無(wú)向圖的度數(shù)列

2、, ,例如例如, ,作業(yè)作業(yè)13P173-7.5 下面各無(wú)向圖中有幾個(gè)頂點(diǎn)下面各無(wú)向圖中有幾個(gè)頂點(diǎn)?(2)21條邊條邊,3個(gè)個(gè)4度頂點(diǎn)度頂點(diǎn),其余的都是其余的都是3度頂點(diǎn)度頂點(diǎn).解解.設(shè)該圖有設(shè)該圖有n個(gè)頂點(diǎn)個(gè)頂點(diǎn),則由握手定理則由握手定理 34(n3)3=221,解得解得,n=13.故該圖有故該圖有13個(gè)頂點(diǎn)個(gè)頂點(diǎn).P173-7.6 35條邊條邊,每個(gè)頂點(diǎn)的度數(shù)至少為每個(gè)頂點(diǎn)的度數(shù)至少為3的的圖最多有幾個(gè)頂點(diǎn)圖最多有幾個(gè)頂點(diǎn)?解解.設(shè)該圖最多有設(shè)該圖最多有n個(gè)頂點(diǎn)個(gè)頂點(diǎn),由握手定理由握手定理 3n352,那么那么 n70/3=23.故該圖最多有故該圖最多有23個(gè)頂點(diǎn)個(gè)頂點(diǎn).作業(yè)作業(yè)13P17

3、3-7.13 設(shè)設(shè)G1,G2,G3均為均為4階無(wú)向簡(jiǎn)單圖階無(wú)向簡(jiǎn)單圖,它們均有兩它們均有兩條邊條邊,它們能彼此均非同構(gòu)嗎它們能彼此均非同構(gòu)嗎?為什么為什么?解解.G1,G2,G3彼此不能均非同構(gòu)彼此不能均非同構(gòu).因?yàn)橐驗(yàn)?階階2條邊的非同構(gòu)條邊的非同構(gòu)無(wú)無(wú)向簡(jiǎn)單圖只有向簡(jiǎn)單圖只有2個(gè)個(gè). 事實(shí)上事實(shí)上,因?yàn)閳D只有兩條邊因?yàn)閳D只有兩條邊,故總度數(shù)為故總度數(shù)為4,且為無(wú)向簡(jiǎn)單且為無(wú)向簡(jiǎn)單圖圖,因而每個(gè)頂點(diǎn)度數(shù)最多為因而每個(gè)頂點(diǎn)度數(shù)最多為2.將將4分解為分解為4個(gè)數(shù)的和且每個(gè)數(shù)個(gè)數(shù)的和且每個(gè)數(shù)不超過(guò)不超過(guò)2,得下面得下面3組數(shù)組數(shù): (0,0,2,2), (0,1,1,2), (1,1,1,1) 而

4、而(0,0,2,2)不可能是一不可能是一4階階2條邊的無(wú)向簡(jiǎn)單圖的度數(shù)列條邊的無(wú)向簡(jiǎn)單圖的度數(shù)列,因因2個(gè)頂點(diǎn)為孤立點(diǎn)個(gè)頂點(diǎn)為孤立點(diǎn),則另兩個(gè)頂點(diǎn)的度數(shù)最多為則另兩個(gè)頂點(diǎn)的度數(shù)最多為1,否則否則,會(huì)會(huì)出現(xiàn)平行邊或環(huán)出現(xiàn)平行邊或環(huán).所以所以(4,2)圖只有圖只有2個(gè)非同構(gòu)的圖個(gè)非同構(gòu)的圖,如上圖如上圖.作業(yè)作業(yè)14補(bǔ)充補(bǔ)充1 (1)若無(wú)向圖若無(wú)向圖G中只有兩個(gè)奇度頂點(diǎn)中只有兩個(gè)奇度頂點(diǎn),則這兩個(gè)奇則這兩個(gè)奇度頂點(diǎn)一定是連通的度頂點(diǎn)一定是連通的.(2)若有向圖若有向圖D中只有兩個(gè)奇度頂點(diǎn)中只有兩個(gè)奇度頂點(diǎn),則它們一個(gè)可達(dá)另則它們一個(gè)可達(dá)另一個(gè)或相互可達(dá)嗎一個(gè)或相互可達(dá)嗎?(1)證明證明.設(shè)設(shè)G中的

5、兩個(gè)奇度頂點(diǎn)分別為中的兩個(gè)奇度頂點(diǎn)分別為u和和v,若若u和和v不連不連通通,即它們之間無(wú)任何通路即它們之間無(wú)任何通路,則則G至少有兩個(gè)連通分支至少有兩個(gè)連通分支G1,G2,使得使得u和和v分別屬于分別屬于G1和和G2,于是于是G1和和G2中各中各有有1個(gè)奇度頂點(diǎn)個(gè)奇度頂點(diǎn),這與握手定理的推論矛盾這與握手定理的推論矛盾.因而因而u和和v一定是連通的一定是連通的.(2)解解.有向圖有向圖D中只有兩個(gè)奇度頂點(diǎn)中只有兩個(gè)奇度頂點(diǎn)u和和v,則則u與與v不一定不一定相互可達(dá)相互可達(dá),也不一定一個(gè)可達(dá)另一個(gè)也不一定一個(gè)可達(dá)另一個(gè). 如右圖如右圖,頂點(diǎn)頂點(diǎn)u和和v的度數(shù)均為的度數(shù)均為1,w的度數(shù)為的度數(shù)為2,

6、 但但u不可達(dá)不可達(dá)v,v也不可達(dá)也不可達(dá)u.作業(yè)作業(yè)14補(bǔ)充補(bǔ)充2 設(shè)設(shè)G是是n階無(wú)向簡(jiǎn)單圖階無(wú)向簡(jiǎn)單圖,如果如果G中每一對(duì)頂中每一對(duì)頂點(diǎn)的度數(shù)之和均大于等于點(diǎn)的度數(shù)之和均大于等于n-1,那么那么G是連通圖是連通圖.證明證明.假設(shè)假設(shè)G不是連通圖不是連通圖,則則G至少有兩個(gè)連通分至少有兩個(gè)連通分支支G1,G2,設(shè)設(shè)G1中有中有n1個(gè)頂點(diǎn)個(gè)頂點(diǎn),G2中有中有n2個(gè)頂個(gè)頂點(diǎn)點(diǎn),那么那么 n1+n2n. 分別從分別從G1和和G2中任取一個(gè)頂點(diǎn)中任取一個(gè)頂點(diǎn)u,v,由于由于G是是簡(jiǎn)單圖簡(jiǎn)單圖,從而從而G1和和G2也都是簡(jiǎn)單圖也都是簡(jiǎn)單圖,所以所以 d(u)n1-1,d(v)n2-1, 故故d(u)+

7、d(v)n1+n2-2n-2,與題設(shè)矛盾與題設(shè)矛盾.P174-7.18 有向圖D如下圖所示.求D中長(zhǎng)度為4的通路總數(shù),并指出其中有多少條是回路?又有幾條是 v3到v4的通路?解.圖D的鄰接矩陣為那么 由A4得,aij=15,aii=3,a34=2,故D中長(zhǎng)度為4的通路有15條,其中有3條回路,從v3到v4長(zhǎng)度為4的通路有2條.1000101000010110A .1000201111112121A1000111010111111A1000100101101011A432 ,i=14i=1j=144(4)(4)(4)P203-9.1 設(shè)無(wú)向樹(shù)設(shè)無(wú)向樹(shù)T有有3個(gè)個(gè)3度頂點(diǎn)度頂點(diǎn),2個(gè)個(gè)2度頂點(diǎn)度頂

8、點(diǎn),其余頂點(diǎn)都是樹(shù)葉其余頂點(diǎn)都是樹(shù)葉,問(wèn)問(wèn)T有幾片樹(shù)葉有幾片樹(shù)葉?解解.設(shè)設(shè)T有有t片樹(shù)葉片樹(shù)葉,則則T的總頂點(diǎn)數(shù)為的總頂點(diǎn)數(shù)為3+2+t,總邊數(shù)總邊數(shù)為為3+2+t-1=4+t,由握手定理由握手定理,有有 2(4+t)=33+22+t,解得解得t=5,故故T有有5片樹(shù)葉片樹(shù)葉.P203-9.4 已知已知n(n2)階無(wú)向簡(jiǎn)單圖階無(wú)向簡(jiǎn)單圖G有有n-1條邊條邊,G一定為樹(shù)嗎一定為樹(shù)嗎?解解.不一定不一定.如如G為非連通圖時(shí)就不是樹(shù)為非連通圖時(shí)就不是樹(shù).例如例如,在圖在圖G中中,n=5,m=4,m=n-1,但但G不是樹(shù)不是樹(shù).P203-9.7 在下圖所示的無(wú)向圖在下圖所示的無(wú)向圖G中中,實(shí)線邊所示

9、的子圖實(shí)線邊所示的子圖為為G的一棵生成樹(shù)的一棵生成樹(shù)T,求求G對(duì)應(yīng)于對(duì)應(yīng)于T的基本回路系統(tǒng)和基的基本回路系統(tǒng)和基本割集系統(tǒng)本割集系統(tǒng).解解.對(duì)應(yīng)于弦對(duì)應(yīng)于弦c的基本回路為的基本回路為:Cc=adcb, 對(duì)應(yīng)于弦對(duì)應(yīng)于弦e的基本回路為的基本回路為:Ce=ade, 對(duì)應(yīng)于弦對(duì)應(yīng)于弦g的基本回路為的基本回路為:Cg=agf, 對(duì)應(yīng)于弦對(duì)應(yīng)于弦h的基本回路為的基本回路為:Ch=afhb, 所以對(duì)應(yīng)于所以對(duì)應(yīng)于T的基本回路系統(tǒng)的基本回路系統(tǒng)為為:adcb,ade,agf,afhb. 對(duì)應(yīng)于樹(shù)枝對(duì)應(yīng)于樹(shù)枝a的基本割集為的基本割集為:Sa=a,e,c,g,h, 對(duì)應(yīng)于樹(shù)枝對(duì)應(yīng)于樹(shù)枝b的基本割集為的基本割集為

10、:Sb=b,c,h, 對(duì)應(yīng)于樹(shù)枝對(duì)應(yīng)于樹(shù)枝d的基本割集為的基本割集為:Sd=c,d,e, 對(duì)應(yīng)于樹(shù)枝對(duì)應(yīng)于樹(shù)枝f的基本割集為的基本割集為:Sf=f,g,h, 所以所以T的基本割集的基本割集為為:a,e,c,g,h,b,c,h,c,d,e,f,g,h.P203-9.8 求下圖所示兩帶權(quán)圖的最小生成樹(shù)求下圖所示兩帶權(quán)圖的最小生成樹(shù),并并計(jì)算它們的權(quán)計(jì)算它們的權(quán).解解.(a)的最小生成樹(shù)為的最小生成樹(shù)為T(mén)1,如下圖如下圖.T1的權(quán)為的權(quán)為:W(T1)=1+2+3+1=7.(b)的最小生成樹(shù)為的最小生成樹(shù)為T(mén)2,如右圖如右圖.T2的權(quán)為的權(quán)為:W(T2)=1+2+4+4=11.P204-9.11 下圖

11、給出的下圖給出的2元樹(shù)表達(dá)一個(gè)算式元樹(shù)表達(dá)一個(gè)算式.(1)給出這個(gè)算式的表達(dá)式給出這個(gè)算式的表達(dá)式;(2)給出算式的波蘭符號(hào)法表達(dá)式給出算式的波蘭符號(hào)法表達(dá)式;(3)給出算式的逆波蘭符號(hào)法表達(dá)式給出算式的逆波蘭符號(hào)法表達(dá)式.解解.(1)(abc)de) (fg)hij.(2)abcde fghij.(3)abcdefg hij.P204-9.13 設(shè)設(shè)7個(gè)字母在通信中出現(xiàn)的頻率如下個(gè)字母在通信中出現(xiàn)的頻率如下:a:35%,b:20%,c:15%,d:10%,e:10%,f:5%,g:5%.求求傳輸這傳輸這7個(gè)字母的最佳前綴碼個(gè)字母的最佳前綴碼.解解.以以100乘各頻率并由小到大乘各頻率并由小到

12、大排列為排列為:w1=5,w2=5,w3=10,w4=10,w5=15,w6=20,w7=35. 用用huffman算法求帶權(quán)為算法求帶權(quán)為w1,w2,w3,w4,w5,w6,w7的的最優(yōu)最優(yōu)2元樹(shù)如右圖元樹(shù)如右圖. 最佳前綴碼為最佳前綴碼為:01,11,001,100,101,0000,0001. 對(duì)應(yīng)的碼子傳輸?shù)淖帜笧閷?duì)應(yīng)的碼子傳輸?shù)淖帜笧?11傳傳a,01傳傳b,101傳傳c,100傳傳d,001傳傳e,0001傳傳f,0000傳傳g. P188-8.3 完全二部圖完全二部圖Kr,s中中,邊數(shù)邊數(shù)m為多少為多少?解解.Kr,s中中,邊數(shù)邊數(shù)m為為:m=rs.P188-8.6 畫(huà)一個(gè)無(wú)向歐

13、拉圖畫(huà)一個(gè)無(wú)向歐拉圖,使它具有使它具有:(1)偶數(shù)個(gè)頂點(diǎn)偶數(shù)個(gè)頂點(diǎn),偶數(shù)條邊偶數(shù)條邊;(2)奇數(shù)個(gè)頂點(diǎn)奇數(shù)個(gè)頂點(diǎn),奇數(shù)條邊奇數(shù)條邊;(3)偶數(shù)個(gè)頂點(diǎn)偶數(shù)個(gè)頂點(diǎn),奇數(shù)條邊奇數(shù)條邊;(4)奇數(shù)個(gè)頂點(diǎn)奇數(shù)個(gè)頂點(diǎn),偶數(shù)條邊偶數(shù)條邊.解解.(1) (2) (3) (4)P189-8.8 畫(huà)一個(gè)無(wú)向圖畫(huà)一個(gè)無(wú)向圖,使它是使它是:(1)既是歐拉圖既是歐拉圖,又是哈密爾頓圖又是哈密爾頓圖;(2)是歐拉圖是歐拉圖,而不是哈密爾頓圖而不是哈密爾頓圖;(3)是哈密爾頓圖是哈密爾頓圖,而不是歐拉圖而不是歐拉圖;(4)既不是歐拉圖既不是歐拉圖,也不是哈密爾頓圖也不是哈密爾頓圖.解解.(1) (2) (3) (4)P189-8.18 彼得森圖如下圖所示彼得森圖如下圖所示.證明它不是證