離散數(shù)學(xué)圖論部分形成性考核書面作業(yè)4答案

離散數(shù)學(xué)業(yè)

姓學(xué)得

名號分離數(shù)圖部形性核面業(yè)本課程形成性考核書面作業(yè)共3次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型（除單項(xiàng)選擇題外）安排練習(xí)題目，目的是通過綜合性書面作業(yè)，使同學(xué)自己檢驗(yàn)學(xué)習(xí)成果，找出掌握的薄弱知識點(diǎn)，重點(diǎn)復(fù)習(xí)，爭取盡快掌握。本次形考書面作業(yè)是第二次作業(yè)，大家要認(rèn)真及時(shí)地完成圖論部分的綜合練習(xí)作業(yè)。一、填題1．已知圖G中有個(gè)1結(jié)點(diǎn)，22度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，4個(gè)4結(jié)點(diǎn)，則的邊數(shù)是

15

．2．設(shè)給定G如右由圖所示，則圖的點(diǎn)割集是{f}

．3．設(shè)G是一個(gè)圖，結(jié)點(diǎn)集合為V，邊集合為，則的結(jié)點(diǎn)

度數(shù)之和

等于邊數(shù)的兩倍．4．無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且度．

等于出5．設(shè)G=<，E>是具有個(gè)結(jié)點(diǎn)的簡單圖，若在G每一對結(jié)點(diǎn)度數(shù)之和大于等于

，則在中存在一條漢密爾頓路．6．若圖E>中有一條漢密爾頓回路，則對于結(jié)點(diǎn)集V每個(gè)非空子集S，在中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為，則中結(jié)點(diǎn)數(shù)S|與W滿足的關(guān)系式為7．設(shè)完全K有個(gè)結(jié)點(diǎn)(n，條邊，當(dāng)

．n奇數(shù)

時(shí)，K

中存在歐拉回路．1/8．結(jié)點(diǎn)數(shù)與邊數(shù)e足樹．

e=v-1

關(guān)系的無向連通圖就是9．設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為，則可從G中刪去4

條邊后使之變成樹．10設(shè)正則5樹的樹葉數(shù)為，則分支數(shù)為i=

．二、判說明題（判斷下列各題，并說明理由．）1．如果圖G是無向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路．．(1)不正確，缺了一個(gè)條件，圖G應(yīng)該是連通圖，可以找出一個(gè)反例，比如圖是一個(gè)有孤立結(jié)點(diǎn)的圖。2．如下圖示的圖G在一條歐拉回路．(2)不正確，圖中有奇數(shù)度結(jié)點(diǎn)，所以不存在是歐拉回路。3．如下圖示的圖G是歐拉圖而是漢密爾頓圖．解：正確因?yàn)閳D中結(jié)點(diǎn)，b，d，f的度數(shù)都為奇數(shù)，所以不是歐拉圖。2/13451231345123234354512534如果我們沿著(a,d,g,f,e,b,c,a)，這樣除起點(diǎn)和終點(diǎn)是a，我們經(jīng)過每個(gè)點(diǎn)一次僅一次，所以存在一條漢密爾頓回路，是漢密爾頓圖4．設(shè)G是一個(gè)有個(gè)結(jié)點(diǎn)16邊的連通圖，則為平面圖．解：(1)錯(cuò)誤假設(shè)圖是連通的平面圖，根據(jù)定理，結(jié)點(diǎn)數(shù)v，邊數(shù)為，應(yīng)滿足e小于等于，但現(xiàn)在小于等于3*7-6，顯示不成立。所以假設(shè)錯(cuò)誤。5．設(shè)G是一個(gè)連通平面圖，且有個(gè)結(jié)點(diǎn)條邊，則有7個(gè)面．(2)正確根據(jù)歐拉定理，有，邊數(shù)，結(jié)點(diǎn)數(shù)e=6，代入公式求出面數(shù)r=7三、計(jì)題1．設(shè)=<，E>，V={v，v，，v，v}E={(,，,v)，(,v)，,v)，,v)，,v)}試(1)給出的圖形表示；(3)求出每個(gè)結(jié)點(diǎn)的度數(shù)；解：(1)v

(2)寫出其鄰接矩陣；(4)畫出其補(bǔ)圖的圖形．v

vv

v3/1253412534(2)鄰接矩陣為

(3)

v結(jié)點(diǎn)度數(shù)為，v結(jié)度數(shù)為，結(jié)度數(shù)為3，結(jié)度數(shù)為2v結(jié)度數(shù)為212345(4)補(bǔ)圖圖形為vv

vv

v2．圖GV,E>，其中={,b,,d,e，E={(,b),(a,ca,eb,d),(,e),c,e),(c,d),(,e)}，對應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5，試（1）畫出G的圖形；（2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹及其權(quán)值．（1）G的圖形如下：4/（2）寫出G的鄰接矩陣（3）G權(quán)最小的生成樹及其權(quán)值3．已知帶圖G右圖所示．(1)求圖的最小生成樹；

(2)計(jì)算該生成樹的權(quán)值．解：(1)最小生成樹為5/1

275

3(2)該生成樹的權(quán)值為(1+2+3+5+7)=184．設(shè)有一權(quán)為2,5,7,31，試畫出相應(yīng)的最優(yōu)二叉樹，計(jì)算該最優(yōu)二叉樹的權(quán)．6/63

311

171

75

523權(quán)為

2*5+3*5+5*4+7*3+17*2+31=131四、證題1．設(shè)G是一個(gè)階無向簡單圖，n大于等于3的奇數(shù)．證明圖與它的補(bǔ)G中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等．證明：GEGEn無向完全K的邊刪去n所得到的．所以對于任意結(jié)u，在的度數(shù)之和等于uK中n的度數(shù)．由于n大于等于3的奇數(shù)，從而的每個(gè)結(jié)點(diǎn)都是偶數(shù)度的nn(2)），于是在中是奇數(shù)度結(jié)點(diǎn)，則它G中也是奇數(shù)度結(jié)點(diǎn)．故圖與它的補(bǔ)中的奇數(shù)度結(jié)點(diǎn)個(gè)數(shù)相等．7/2．設(shè)連通Gk個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加能使其成為歐拉圖．

條邊才證明：由定理，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)，可知k偶