電大離散數(shù)學作業(yè)答案(圖論部分)

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請聯(lián)系刪除，謝謝！姓名：學號：得分：教師簽名：5離散數(shù)學圖論部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共3次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習，基本上是按照考試的題型（除單項選擇題外）安排練習題目，目的是通過綜合性書面作業(yè)，使同學自己檢驗學習成果，找出掌握的薄弱知識點，重點復習，爭取盡快掌握。本次形考書面作業(yè)是第二次作業(yè)，大家要認真及時地完成圖論部分的綜合練習作業(yè)。要求：將此作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，要求2018年12月5日前完成并上交任課教師（不收電子稿）。并在05任務界面下方點擊“保存”和“交卷”按鈕，以便教師評分。一、填空題1．已知圖G中有1個1度結(jié)點，2個2度結(jié)點，3個3度結(jié)點，4個4度結(jié)點，則G的邊數(shù)是15．2．設(shè)給定圖G如右由圖所示，則圖G的點割集是{f}．3．設(shè)G是一個圖，結(jié)點集合為V，邊集合為E，則G的結(jié)點度數(shù)之和等于邊數(shù)的兩倍．4．無向圖G存在歐拉回路，當且僅當G連通且等于出度．5．設(shè)V，E是具有n個結(jié)點的簡單圖，若在G中每一對結(jié)點度數(shù)之和大于等于n-1，則在G中存在一條漢密爾頓路．6．若圖,E>中具有一條漢密爾頓回路，則對于結(jié)點集V的每個非空子集S，在G中刪除S中的所有結(jié)點得到的連通分支數(shù)為，則S中結(jié)點數(shù)S|與W滿足的關(guān)系式為W(G-V1)V．17．設(shè)完全圖K有n個結(jié)點n，m條邊，當n為奇數(shù)時，K中存在歐拉nn回路．8．結(jié)點數(shù)v與邊數(shù)e滿足e=v-1關(guān)系的無向連通圖就是樹．9．設(shè)圖G是有6個結(jié)點的連通圖，結(jié)點的總度數(shù)為18，則可從G中刪去4條邊后使之變成樹．10．設(shè)正則5叉樹的樹葉數(shù)為17，則分支數(shù)為i．二、判斷說明題（判斷下列各題，并說明理由．）1．如果圖G是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖G存在一條歐拉回1/6路．．(1)不正確，缺了一個條件，圖G應該是連通圖，可以找出一個反例，比如圖G是一個有孤立結(jié)點的圖。2．如下圖所示的圖G存在一條歐拉回路．(2)不正確，圖中有奇數(shù)度結(jié)點，所以不存在是歐拉回路。3．如下圖所示的圖G不是歐拉圖而是漢密爾頓圖．G解：正確因為圖中結(jié)點，b，d，f的度數(shù)都為奇數(shù)，所以不是歐拉圖。如果我們沿著(a,d,g,f,e,b,c,a)，這樣除起點和終點是a外，我們經(jīng)過每個點一次僅一次，所以存在一條漢密爾頓回路，是漢密爾頓圖4．設(shè)G是一個有7個結(jié)點16條邊的連通圖，則G為平面圖．解：(1)錯誤假設(shè)圖G是連通的平面圖，根據(jù)定理，結(jié)點數(shù)v，邊數(shù)為，應滿足e小于等于3v-6，但現(xiàn)在16小于等于3*7-6，顯示不成立。所以假設(shè)錯誤。5．設(shè)G是一個連通平面圖，且有6個結(jié)點11條邊，則G有7個面．(2)正確根據(jù)歐拉定理，有v-e+r=2，邊數(shù)v=11，結(jié)點數(shù)，代入公式求出面數(shù)r=7三、計算題1．設(shè)V，E，V={v，v，v，v，v}，={v,v，v,v)，v,v，12345132324v,v，v,v，v,v)，試343545(1)給出G的圖形表示；(2)寫出其鄰接矩陣；(3)求出每個結(jié)點的度數(shù)；(4)畫出其補圖的圖形．2/6解：(1)v1v2v5vv43(2)鄰接矩陣為0010000110110110110100110(3)vvvvv212345v1v2v5vv432．圖V,E，其中V={a,b,,d,}，E={(a,b),(a,c),(a,e),(b,d),(b,),,),(,d),(d,)，對應邊的權(quán)值依次為2、1、2、3、6、1、4及5，試（1）畫出G的圖形；（2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹及其權(quán)值．（1）G的圖形如下：3/6（2）寫出G的鄰接矩陣（3）G權(quán)最小的生成樹及其權(quán)值3．已知帶權(quán)圖G如右圖所示．(1)求圖G的最小生成樹；計算該生成樹的權(quán)值．解：(1)最小生成樹為4/621753(2)該生成樹的權(quán)值為(1+2+3+5+7)=184．設(shè)有一組權(quán)為2,3,5,7,17,31，試畫出相應的最優(yōu)二叉樹，計算該最優(yōu)二叉樹的權(quán)．63131717155235/6權(quán)為2*5+3*5+5*4+7*3+17*2+31=131四、證明題1．設(shè)G是一個n階無向簡單圖，n是大于等于3的奇數(shù)．證明圖G與它的補圖G中的奇數(shù)度頂點個數(shù)相等．證明：設(shè),，GV,E．則E是由n階無向完全圖K的邊刪去EGVEn所得到的．所以對于任意結(jié)點uV，u在G和G中的度數(shù)之和等于u在K中n的度數(shù)．由于n是大于等于3的奇數(shù)，從而K的每個結(jié)點都是偶數(shù)度的n（1(度），于是若uV在G中是奇數(shù)度結(jié)點，則它在G中也是奇數(shù)度n結(jié)點．故圖G與它的補圖G中的奇數(shù)度結(jié)點個數(shù)相等．k2．設(shè)連通圖G有k個奇數(shù)度的結(jié)點，證明在圖G中至少要添加條邊才2能使其成為歐拉圖．證明：由定理3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點必是偶數(shù)，可