離散數(shù)學(xué)《離散數(shù)學(xué)》課后練習(xí)

1、 由頂點(diǎn)集a,b,d,f誘導(dǎo)出的子圖107、14解：求下列賦權(quán)圖頂點(diǎn)間的距離。acbd(a,b)=3,d(a，c)=3,d(a,d)=,d(a,e)=8,d(a,f)=16,d(b,c)=1,d(b,d)=,d(b,e)=6,d(b,f)=13,gd(c,d)=,d(c,e)=5,d(c,f)=12,ggd(d,e)=,d(d,f)=,d(e,f)=7,108、v3Sl(v2)l(v3)l(vg4)l(vg5)l(vg6)tl(t)v134ggv23v1,v2413gv34v1,v2,v376v56v1,v2,v3,v5710v47v1,v2,v3,v5,v49v69解：v1,v2,v3,v5

2、,v4,v6故v1到v2,v3,v4,v5,v6的距離分別是3，4，7，6，9。該圖的鄰接矩陣為1100000100001100001001000一000000011010012000211002一000000010010101100-.000100010303-01000010000200100000001120051004300故圖的可達(dá)矩陣為0011111100111000001100011110、求下列圖的生成樹。P=110、求下列圖的生成樹。下面是它的兩棵生成樹：V。若存在一條從u到v下面是它的兩棵生成樹：V。若存在一條從u到v的一條通路，則必有一條從u到v的長(zhǎng)度不超過n-1的通路。

3、若l-n-1,則結(jié)論顯然、n,故v0,v1,vl中必有一個(gè)頂點(diǎn)是重復(fù)出現(xiàn)的。不妨設(shè)vi=vj(Oijl),則新通路v0e1v1e2viej+1vl+1ej+2vj+2elvl是一條從u到v的通路，且此通路長(zhǎng)度比原通路長(zhǎng)度至少少1。若新通路的長(zhǎng)度一n-1,則結(jié)論得證。否則對(duì)新通路重復(fù)上述過程，必可以得到一條從u到v的長(zhǎng)為n-1的通路。111、在一個(gè)有n個(gè)頂點(diǎn)的G=中,證明：l的長(zhǎng)為l的通路。設(shè)v0e1v1e2elvll的長(zhǎng)為l的通路。112、設(shè)簡(jiǎn)單平面圖G中頂點(diǎn)數(shù)n=7,邊數(shù)m=15。證明：G是連通的。證明：設(shè)G具有k個(gè)連通分支G1,G2,，Gk。設(shè)Gi的頂點(diǎn)數(shù)為ni,邊數(shù)為mi,i=1,2,k

4、。先證每個(gè)連通分支的頂點(diǎn)數(shù)都大于1。否則說明G中有孤立結(jié)點(diǎn)。由于G是簡(jiǎn)單圖，從而要使G的邊數(shù)是15,則G只有兩個(gè)連通分支，其中一個(gè)是由孤立結(jié)點(diǎn)導(dǎo)出的，另一個(gè)是K6。但K6不是平面圖，故要每個(gè)連通分支的頂點(diǎn)數(shù)都大于1。同理可證，每個(gè)連通分支的頂點(diǎn)數(shù)都大于2。由此可得，G的每個(gè)連通分支至少有3個(gè)頂點(diǎn)。從而即m=i=1即m=i=1(3n-6)=3n-6k從而1521-6k，即k1。從而k=1，故G是連通圖。113、已知一棵無(wú)向樹中有2個(gè)2度頂點(diǎn)、1個(gè)3度頂點(diǎn)、3個(gè)4度頂點(diǎn)，其余頂點(diǎn)度數(shù)都為1。問它有多少個(gè)1度頂點(diǎn)？解：設(shè)它有k個(gè)1度頂點(diǎn)，則由歐拉握手定理工veVdeg(v)=2IEI可得2IEI=k

5、+4+3+12=k+19。再由于它是一棵樹，故|E|=k+2+1+3-1=k+5從而2(k+5)=k+19,k=9。故它有9個(gè)1度頂點(diǎn)。114、有向圖G是強(qiáng)連通的G中有一回路，它至少通過每個(gè)頂點(diǎn)一次。證明：=設(shè)G=是強(qiáng)連通圖。任取u,vGV,則u和v相互可達(dá)，即從u到v有路徑P1，從v到u有路徑P1。故從P1和P2首尾相接可得到一條經(jīng)過u和v的回路C1。若C1經(jīng)過G中所有頂點(diǎn)至少一次，則C1就是滿足結(jié)論要求的回路。否則若C1沒有經(jīng)過頂點(diǎn)w,則類似地我們可得到一條經(jīng)過u和w的回路C2。從C1和C2我們可得到一條經(jīng)過更多頂點(diǎn)的回路C3(先從u經(jīng)過P1到v再?gòu)膙經(jīng)過C2回到v再?gòu)膙經(jīng)過P2回到u)。

6、對(duì)C3重復(fù)上述過程，直到得到一條經(jīng)過所有頂點(diǎn)的回路為止。U若G中存在一條經(jīng)過G中所有頂點(diǎn)至少一次的回路，則G中任意兩個(gè)頂點(diǎn)是相互可達(dá)的，從而G是強(qiáng)連通的。115、一個(gè)有向圖是單向連通圖它有一條經(jīng)過所有結(jié)點(diǎn)的路。證明：=設(shè)G=是單向連通圖。任取u,v*V，貝Vu可達(dá)v或v可達(dá)u。不妨設(shè)u可達(dá)V，即從u到v有路徑P1。若P1經(jīng)過G中所有頂點(diǎn)至少一次，則P1就是滿足結(jié)論要求的路徑。否則若P1沒有經(jīng)過頂點(diǎn)w,則如果v經(jīng)過路徑T可達(dá)w,連接P1和T我們可得一條經(jīng)過P1經(jīng)過的所有頂點(diǎn)及w的更長(zhǎng)的路徑P2；否則若w經(jīng)過路徑S可達(dá)u,連接S和P1我們也可得一條經(jīng)過w及P1經(jīng)過的所有頂點(diǎn)的更長(zhǎng)的路徑P2；再否則我們一定可以找到P1經(jīng)過的兩個(gè)相鄰頂點(diǎn)t和s,t到s有邊，t經(jīng)過路徑T1可達(dá)w,w經(jīng)過路徑T2可達(dá)s(否則就與u可達(dá)w,w可達(dá)v矛盾)，我們構(gòu)造這樣一條路徑P2:從u出發(fā)經(jīng)過P1到達(dá)t,t經(jīng)過路徑T1到達(dá)w,再?gòu)膚出發(fā)經(jīng)過路徑T2到達(dá)s,然后從s出發(fā)經(jīng)過P1到達(dá)v。這是一條經(jīng)過w及P1所經(jīng)過的所有