離散數(shù)學《離散數(shù)學》課后練習

1、 由頂點集a,b,d,f誘導出的子圖107、14解：求下列賦權圖頂點間的距離。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故圖的可達矩陣為0011111100111000001100011110、求下列圖的生成樹。P=110、求下列圖的生成樹。下面是它的兩棵生成樹：V。若存在一條從u到v下面是它的兩棵生成樹：V。若存在一條從u到v的一條通路，則必有一條從u到v的長度不超過n-1的通路。

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

4、。先證每個連通分支的頂點數(shù)都大于1。否則說明G中有孤立結點。由于G是簡單圖，從而要使G的邊數(shù)是15,則G只有兩個連通分支，其中一個是由孤立結點導出的，另一個是K6。但K6不是平面圖，故要每個連通分支的頂點數(shù)都大于1。同理可證，每個連通分支的頂點數(shù)都大于2。由此可得，G的每個連通分支至少有3個頂點。從而即m=i=1即m=i=1(3n-6)=3n-6k從而1521-6k，即k1。從而k=1，故G是連通圖。113、已知一棵無向樹中有2個2度頂點、1個3度頂點、3個4度頂點，其余頂點度數(shù)都為1。問它有多少個1度頂點？解：設它有k個1度頂點，則由歐拉握手定理工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個1度頂點。114、有向圖G是強連通的G中有一回路，它至少通過每個頂點一次。證明：=設G=是強連通圖。任取u,vGV,則u和v相互可達，即從u到v有路徑P1，從v到u有路徑P1。故從P1和P2首尾相接可得到一條經(jīng)過u和v的回路C1。若C1經(jīng)過G中所有頂點至少一次，則C1就是滿足結論要求的回路。否則若C1沒有經(jīng)過頂點w,則類似地我們可得到一條經(jīng)過u和w的回路C2。從C1和C2我們可得到一條經(jīng)過更多頂點的回路C3(先從u經(jīng)過P1到v再從v經(jīng)過C2回到v再從v經(jīng)過P2回到u)。

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