離散數(shù)學(xué)作業(yè)5[答案]

1、一、填空題1已知圖G中有1個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，4個(gè)4度結(jié)點(diǎn)，貝UG的邊數(shù)是15.直、才&2設(shè)給定圖G（如右由圖所示），則圖G的點(diǎn)割集是/f,c3. 設(shè)G是一個(gè)圖，結(jié)點(diǎn)集合為V,邊集合為E,則G的結(jié)點(diǎn)等于邊數(shù)的兩倍.w4. 無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù).5. 設(shè)G=是具有n個(gè)結(jié)點(diǎn)的簡單圖，若在G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n-1，則在G中存在一條漢密爾頓路.6. 若圖G=中具有一條漢密爾頓回路，則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S,在G中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為W,則S中結(jié)點(diǎn)數(shù)|S|與W滿足的關(guān)系式為_W|S|.7. 設(shè)完全圖Kn有n個(gè)結(jié)

2、點(diǎn)（n2）,m條邊，當(dāng)n為奇數(shù)時(shí)，Kn中存在歐拉回路.8. 結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足e=v-1關(guān)系的無向連通圖就是樹.9. 設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18,則可從G中刪去4條邊后使之變成樹.10. 設(shè)正則5叉樹的樹葉數(shù)為17,則分支數(shù)為i=4.二、判斷說明題（判斷下列各題，并說明理由.）1. 如果圖G是無向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路.不正確，圖G是無向圖，當(dāng)且僅當(dāng)G是連通，且所有結(jié)點(diǎn)度數(shù)均為偶數(shù)，這里不能確定圖G是否是連通的。2. 如下圖所示的圖G存在一條歐拉回路.錯(cuò)誤.因?yàn)閳DG為中包含度數(shù)為奇數(shù)的結(jié)點(diǎn).3. 如下圖所示的圖G不是歐拉圖而是漢密爾頓圖.G形成性

3、考核作業(yè)5答案解：錯(cuò)，既不是歐拉圖也不是漢密爾頓圖，歐拉圖要求所有結(jié)點(diǎn)度數(shù)均為偶數(shù)，這里結(jié)點(diǎn)bd各有三個(gè)節(jié)點(diǎn)；漢密爾頓圖要求每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于總結(jié)點(diǎn)數(shù)，這里不滿足。4 設(shè)G是一個(gè)有7個(gè)結(jié)點(diǎn)16條邊的連通圖，則G為平面圖.錯(cuò)，沒有提到面5 設(shè)G是一個(gè)連通平面圖，且有6個(gè)結(jié)點(diǎn)11條邊，則G有7個(gè)面.對(duì)，由歐拉定理得到：結(jié)點(diǎn)-邊+面=2，即為連通平面圖，這里6-11+7=2三、計(jì)算題1. 設(shè)G=，V=v1，v2,v3,v4,v5，E=(V1,V3),(V2,V3)，(V2,V4)，(V3,V4)，(V3,V5)，(V4,V5)，試(1) 給出G的圖形表示；(2)寫出其鄰接矩陣；(3)求出每個(gè)

4、結(jié)點(diǎn)的度數(shù)；(4)畫出其補(bǔ)圖的圖形.解：(1)G的圖形如圖十二圖十二(2)鄰接矩陣：00100001101101101101001106(3) V1，V2，V3，V4，V5結(jié)點(diǎn)的度數(shù)依次為1，2，4，3，2(4) 補(bǔ)圖如圖十三：2圖G=，其中V=a,b,c,d,e,E=(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)，對(duì)應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5,試(1)畫出G的圖形；(2)寫出G的鄰接矩陣；(3)求出G權(quán)最小的生成樹及其權(quán)值.解：(1)G的圖形表示如圖十四：(2) 鄰接矩陣：0110110011100110110111110(

5、3) 粗線表示最小的生成樹，如圖十五最小的生成樹的權(quán)為1+1+2+3=7:3.已知帶權(quán)圖G如右圖所示.(1)求圖G的最小生成樹；計(jì)算該生成樹的權(quán)值.（1）有點(diǎn)，其生M有于參邊.用KnnkilM袪就其權(quán)最小的生成樹TS第I步，取具呈小權(quán)1的邊匸第2步，取窮余邊中具豪小投2的邊：第趴取崩余邊中不與前2養(yǎng)邊構(gòu)成回踣的具堆小權(quán).1的加第4步，取剰余邊中不與前3條邊枸成回踣的具最小權(quán)密的迦第五歩取捌余邊中不與前4條邊構(gòu)成回踣的具母小權(quán)7的邊.所犧小生處樽Tin右圖.該章中生成務(wù)恂權(quán)為（r）=l+2+3+S+7-lS4設(shè)有一組權(quán)為2,3,5,7,17,31,試畫出相應(yīng)的最優(yōu)二叉樹，計(jì)算該最優(yōu)二叉樹的權(quán).C

6、-i:從乙兒亠乙17J1中選2為繪低涇納點(diǎn).并從權(quán)數(shù)屮刪去川添上他們的和數(shù).即5t5t7t17.3H再從5$A17,31叩選久，為恆魏E2懇殆點(diǎn)+并規(guī)上述數(shù)列中!去.再潘上他們的和數(shù)即7,10,17,1：拾后.從人10,17SJ|中選7,10為債敬第*層緒點(diǎn).井從上譴數(shù)列申鵬冉泠丨他心的和數(shù).t|J17.17,31：泉優(yōu)二夏囲如右絹何衍亠加優(yōu)二楚囲權(quán)位為古2x5+3x5+5x4+7x3+17x2+31xl=10+5+202L+34+3l=lJl四、證明題證明圖G與它的1.設(shè)G是一個(gè)n階無向簡單圖，n是大于等于3的奇數(shù).補(bǔ)圖G中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等.證明：G=,G=.則g是由用階無問完全圖的邊刪去E所器劉的.所以對(duì)于枉意第點(diǎn)口“、*在G和E屮的度數(shù)之和等于存在中的鷹數(shù)”由in是大于等J3的砂從向匚的埒給點(diǎn)都昆留數(shù)度的5-1&2）度）.于是若nwF在O中是奇數(shù)度緒點(diǎn)”則它在U中也是奇數(shù)度皓點(diǎn).故圖G與它的補(bǔ)圖石中的奇數(shù)度結(jié)點(diǎn)牛數(shù)相零.k2. 設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加k條邊才能2使其成為歐拉圖.證明：由定理3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)，可知k