2018國(guó)家開放大學(xué)離散數(shù)學(xué)(本)形考任務(wù)答案

.4教師簽名：離散數(shù)學(xué)圖論部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共3弱知識(shí)點(diǎn)，重點(diǎn)復(fù)習(xí)，爭(zhēng)取盡快掌握．本次形考書面作業(yè)是第二次作業(yè)，大家要認(rèn)真及時(shí)地完成圖論部分的綜合練習(xí)作業(yè)．要求：學(xué)生提交作業(yè)有以下三種方式可供選擇：1.可將此次作業(yè)用A4解答過程，完成作業(yè)后交給輔導(dǎo)教師批閱．2.在線提交word文檔3.自備答題紙張，將答題過程手工書寫，并拍照上傳．一、填空題G1．已知圖中有1個(gè)12個(gè)23個(gè)34個(gè)4度結(jié)G點(diǎn)，則的邊數(shù)是152．設(shè)給定圖(如右由圖所示)，則圖的點(diǎn)割集是{f}，{e,c}．GG．GVE3．設(shè)是一個(gè)圖，結(jié)點(diǎn)集合為，邊集合為，則G的結(jié)點(diǎn)度數(shù)之和等于邊數(shù)的兩倍．GG4．無向圖存在歐拉回路，當(dāng)且僅當(dāng)連通且不含奇數(shù)度結(jié)點(diǎn)．G=VEnG5．設(shè)<，>是具有個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若在中每一對(duì)結(jié)點(diǎn)度數(shù)之和大G，則在中存在一條漢密爾頓路．于等于︱v︱G=<VE>V,中具有一條漢密爾頓回路，則對(duì)于結(jié)點(diǎn)集的每個(gè)非空子6．若圖SGSW集，在中刪除中的所有結(jié)點(diǎn)得到的連通分支數(shù)為，則中結(jié)點(diǎn)數(shù)|與SS|W滿足的關(guān)系式為W≤S．Knnm7有個(gè)結(jié)點(diǎn)(2)，條邊，當(dāng)n為奇數(shù)時(shí)時(shí)，Knn中存在歐拉回路．ve8．結(jié)點(diǎn)數(shù)與邊數(shù)滿足e=v-1關(guān)系的無向連通圖就是樹．..GG9．設(shè)圖是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18，則可從中刪去條邊后使之變成樹．i10．設(shè)正則5叉樹的樹葉數(shù)為17，則分支數(shù)為=4．二、判斷說明題（判斷下列各題，并說明理由．）GG是無向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖存在一條歐拉回路．G則圖G存在一條歐拉回路?！盙2．如下圖所示的圖存在一條歐拉回路．答：錯(cuò)誤。因?yàn)閳D中存在奇數(shù)度結(jié)點(diǎn)，所以不存在歐拉回路。G3．如下圖所示的圖不是歐拉圖而是漢密爾頓圖．G答：正確。因?yàn)橛?個(gè)結(jié)點(diǎn)的度數(shù)為奇數(shù)，所以不是歐拉圖；而對(duì)于圖中任意點(diǎn)集V中的非空子集V1，都有P(G-V1)≤V1P(G-V1)是從圖中刪除..V1結(jié)點(diǎn)及其關(guān)聯(lián)的邊。GG4．設(shè)是一個(gè)有7個(gè)結(jié)點(diǎn)16條邊的連通圖，則為平面圖．答：錯(cuò)誤。若G是連通平面圖，那么若V≥3,就有e≤3v-6而16>3×7－6，所以不滿足定理?xiàng)l件，敘述錯(cuò)誤。GG5．設(shè)是一個(gè)連通平面圖，且有6個(gè)結(jié)點(diǎn)11條邊，則有7個(gè)面．答：正確。因?yàn)檫B通平面圖滿足歐拉公式。即：v-e+r=2。由此題條件知6-11+7=2成立三、計(jì)算題..GVEVvvvvvEvvvvvv1．設(shè)=<，>，={，，，，}，={(,)，(,)，(,)，1(,)，(,)，(,)}，試2345132324vvvvvv34354(1)給出的圖形表示；5G(2)寫出其鄰接矩陣；(4)畫出其補(bǔ)圖的圖形．(3)求出每個(gè)結(jié)點(diǎn)的度數(shù)；）））(4)..GVEVabcdeEabac2．圖=<,>，其中={,,,,}，={(,),(,),(,),aebdbececd(,),(,),(,),(,),(,)}，對(duì)應(yīng)邊的權(quán)值依次為2、1、2、de3、6、1、4及5，試GG（2）寫出的鄰接矩陣；（1）畫出的圖形；G（3）求出權(quán)最小的生成樹及其權(quán)值．（2）（3）..其中權(quán)值是：7G3．已知帶權(quán)圖如右圖所示．G(1)求圖的最小生成樹；(2)計(jì)算該生成樹的權(quán)值．答：（1）（2）權(quán)值：184．設(shè)有一組權(quán)為2,3,5,7,17,31，試畫出相應(yīng)的最優(yōu)二叉樹，計(jì)算該最優(yōu)二叉樹的權(quán)．..權(quán)值：65四、證明題Gnn1．設(shè)是一個(gè)階無向簡(jiǎn)單圖，是大于等于3的奇數(shù)．證明圖與它的G補(bǔ)圖G中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等．a(chǎn)為Ga記為a’,則deg(a)+deg(a’)=n-1,而n為奇數(shù)，則a’必為奇數(shù)度頂點(diǎn)。由a的任意性，容易得知結(jié)論成立。..kGkG2．設(shè)連通圖有個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在