1、姓名：翟偉錚學(xué)號(hào)：離散數(shù)學(xué)作業(yè)5離散數(shù)學(xué)圖論部分形成性考核書(shū)面作得分：教師簽名：本課程形成性考核書(shū)面作業(yè)共3次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型（除單項(xiàng)選擇題外）安排練習(xí)題目，目的是通過(guò)綜合性書(shū)面作業(yè)，使同學(xué)自己檢驗(yàn)學(xué)習(xí)成果，找出掌握的薄弱知識(shí)點(diǎn)，重點(diǎn)復(fù)習(xí)，爭(zhēng)取盡快掌握。本次形考書(shū)面作業(yè)是第二次作業(yè)，大家要認(rèn)真及時(shí)地完成圖論部分的綜合練習(xí)作業(yè)。要求：將此作業(yè)用A4紙打印岀來(lái)，手工書(shū)寫(xiě)答題，字跡工整，解答題要有解答過(guò)程，要求本學(xué)期第15周末前完成并上交任課教師（不收電子稿）。并在05任務(wù)界面下方點(diǎn)擊“保存”和“交卷”按鈕,以便教師評(píng)分。一、填空題

2、4個(gè)4度結(jié)點(diǎn)，貝UG的邊數(shù)是1已知圖G中有1個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，152設(shè)給定圖G如右由圖所示），則圖G的點(diǎn)割集是f3設(shè)G是一個(gè)圖，結(jié)點(diǎn)集合為V,邊集合為E，則G的結(jié)點(diǎn)度數(shù)之和等于邊數(shù)的兩倍.等于出4無(wú)向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且度n-15設(shè)G=V，E是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若在G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于則在G中存在一條漢密爾頓路.6若圖G=VE中具有一條漢密爾頓回路，則對(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é)點(diǎn)（n?2），m條邊，當(dāng)n為奇數(shù)時(shí)，Kn中存在歐拉回路

3、.8結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足e=v-1關(guān)系的無(wú)向連通圖就是樹(shù).9設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18,則可從G中刪去4條邊后使之變成樹(shù).10.設(shè)正則5叉樹(shù)的樹(shù)葉數(shù)為17,則分支數(shù)為i=_5二、判斷說(shuō)明題（判斷下列各題，并說(shuō)明理由）1如果圖G是無(wú)向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路錯(cuò)。缺了一個(gè)條件，圖G應(yīng)該是連通圖。如反例，圖G是一個(gè)有孤立結(jié)點(diǎn)的圖。2如下圖所示的圖G存在一條歐拉回路.錯(cuò)。圖中有奇數(shù)度結(jié)點(diǎn)，所以不存在歐拉回路。3如下圖所示的圖G不是歐拉圖而是漢密爾頓圖.對(duì)。因?yàn)閳D中結(jié)點(diǎn)a、b、d、f的度數(shù)都為奇數(shù)，所以不是歐拉圖。如果沿著（a,d,g,f,e,b,c,a），這

4、樣除起點(diǎn)和終點(diǎn)是a外，經(jīng)過(guò)每個(gè)點(diǎn)一次且僅一次，所以存在一條漢密爾頓回路，是漢密爾頓圖。4設(shè)G是一個(gè)有7個(gè)結(jié)點(diǎn)16條邊的連通圖，則G為平面圖.錯(cuò)。假設(shè)圖G是連通的平面圖，根據(jù)定理，結(jié)點(diǎn)數(shù)為廠v,邊數(shù)為e,應(yīng)滿足e?3v-6，但現(xiàn)在G16?3*7-6，顯然不成立，所以假設(shè)錯(cuò)誤。對(duì)。根據(jù)歐拉定理，有v-e+r=2，結(jié)點(diǎn)數(shù)v=11，邊數(shù)e=6，代入公式求岀面數(shù)r=7三、計(jì)算題E=(V1,V3)，(V2,V3)，(V2,V4)，(V3,V4)，(V3,V5)，V1?00100/00110(1)V2?V5110110110100110(3)V1，V2：3V3，V4，V5結(jié)點(diǎn)的度數(shù)依次為1,2，4,3，2。

5、1.設(shè)G=<V，E>，V=vi，V2，V3，V4，vs，(V4,V5)，試(1)給岀G的圖形表示；(3)求岀每個(gè)結(jié)點(diǎn)的度數(shù)；(4)寫(xiě)出其鄰接矩陣；畫(huà)岀其補(bǔ)圖的圖形.a,e),(b,3、6、1、42.圖G2<VE>，其中V=a,b,c,d,e，E=(a,b),(a,c),(d),(b,e),(?c,e),(c,d),(d,?V5)，對(duì)應(yīng)邊的權(quán)值依次為2、1、2、及5,試(1)畫(huà)出G的圖形；？(2)寫(xiě)出G的鄰接矩陣；(3)求岀G權(quán)最小的生成樹(shù)及其權(quán)值.101011011101110(2)權(quán)值(1+2+3+5+7)=18，試畫(huà)岀相應(yīng)的最優(yōu)二叉樹(shù)，計(jì)算該最優(yōu)二叉樹(shù)的權(quán).4設(shè)有一

6、組權(quán)為2,3,5,7,17,31A2|3權(quán)為2*5+3*5+5*4+7*3+17*2+3仁131四、證明題1設(shè)G是一個(gè)n階無(wú)向簡(jiǎn)單圖，n是大于等于3的奇數(shù)證明圖G與它的補(bǔ)圖G中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等.證明：設(shè)GV,E,GV,E則E是由n階無(wú)向完全圖Kn的邊刪去E所得到的.所以對(duì)于任意結(jié)點(diǎn)uV,u在G和G中的度數(shù)之和等于u在Kn中的度數(shù).由于n是大于等于3的奇數(shù)，從而Kn的每個(gè)結(jié)點(diǎn)都是偶數(shù)度的(n1(2)度)，于是若uV在G中是奇數(shù)度結(jié)點(diǎn)，則它在G中也是奇數(shù)度結(jié)點(diǎn)故圖G與它的補(bǔ)圖G中的奇數(shù)度結(jié)點(diǎn)個(gè)數(shù)相等.k2設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加條邊才能使其成為歐拉圖.2證明：由定理3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)，可知k是偶數(shù).又根據(jù)定理4