《離散數(shù)學(xué)形考任務(wù)07答案》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)形考任務(wù)07答案（8頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、姓 名： 學(xué) 號： 得 分： 教師簽名： 離散數(shù)學(xué)作業(yè)7 離散數(shù)學(xué)圖論部分形成性考核書面作業(yè) 本課程形成性考核書面作業(yè)共3次，內(nèi)容主要分別是圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型安排練習(xí)題目，目的是通過綜合性書面作業(yè)，使同學(xué)自己檢驗(yàn)學(xué)習(xí)成果，找出掌握的薄弱知識點(diǎn)，重點(diǎn)復(fù)習(xí)，爭取盡快掌握。本次形考書面作業(yè)是第二次作業(yè)，大家要認(rèn)真及時(shí)地完成圖論部分的綜合練習(xí)作業(yè)。 要求：將此作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有解答

2、過程，完成并上交任課教師（不收電子稿）。并在07任務(wù)界面下方點(diǎn)擊“保存”和“交卷”按鈕，以便教師評分。 一、單項(xiàng)選擇題 1．設(shè)圖G的鄰接矩陣為，則G的邊數(shù)為( D )． A．5 B．6 C．3 D．4 2．設(shè)圖G＝，則下列結(jié)論成立的是 ( C )． A．deg(V)=2E B．deg(V)=E C． D． 3．設(shè)有向圖（a）、（b）、（c）與（d）如下圖所示，則下列結(jié)論成立的是( D )． a b d c e

3、o o o o o 4題圖 A．（a）是強(qiáng)連通的 B．（b）是強(qiáng)連通的 C．（c）是強(qiáng)連通的 D．（d）是強(qiáng)連通的 4．給定無向圖G如右圖所示，下面給出的結(jié) 點(diǎn)集子集中，不是點(diǎn)割集的為（ B ）． A．{b, d} B．mzebxcnn0 C．{a, c} D．{b, e} o a o o o o b c d e 5題圖 5．圖G如右圖所示，以下說法正確的是 ( C ) ． A．{(a, c)}是割邊 B．{(a, c)}是邊割集 C．{(b, c)}是邊割

4、集 D．{(a, c) ,(b, c)}是邊割集 6．無向圖G存在歐拉通路，當(dāng)且僅當(dāng)(D )． A．G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) B．G中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) C．G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) D．G連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) 7．若G是一個(gè)歐拉圖，則G一定是( C )． A．平面圖 B．漢密爾頓圖 C．連通圖 D．對偶圖 8．設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( A )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 9．

5、設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的( A )條邊，才能確定G的一棵生成樹． A． B． C． D． 10．已知一棵無向樹T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為（D ）． A．8 B．5 C．4 D．3 二、填空題 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)，則G的邊數(shù)是 15 ． 2．設(shè)給定圖G(如右由圖所示)，則圖G的點(diǎn)割集是 {f,c}

6、 ． 3．設(shè)G是一個(gè)圖，結(jié)點(diǎn)集合為V，邊集合為E，則 G的結(jié)點(diǎn) 度數(shù) 等于邊數(shù)的兩倍． 4．設(shè)有向圖D為歐拉圖，則圖D中每個(gè)結(jié)點(diǎn)的入度 　等于出度　　 ． 5．設(shè)G=是具有n個(gè)結(jié)點(diǎn)的簡單圖，若在G中每一對結(jié)點(diǎn)度數(shù)之和大于等于 n-1 ，則在G中存在一條漢密爾頓路． 6．設(shè)無向圖G＝是漢密爾頓圖，則V的任意非空子集V1，都有 W(G-V1) V1． 7．設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n2)，m條邊，當(dāng) 當(dāng)m=2n 時(shí)，K中存在歐拉回路． 8．設(shè)圖G=<

7、V,E>，其中|V|=n，|E|=m．則圖G是樹當(dāng)且僅當(dāng)G是連通的，且m= 2V-2 ． 9．連通無向圖G有6個(gè)頂點(diǎn)9條邊，從G中刪去 4 條邊才有可能得到G的一棵生成樹T． 10．設(shè)正則5叉樹的樹葉數(shù)為17，則分支數(shù)為i = 4 ． 三、判斷說明題（判斷下列各題，并說明理由．） 1．(1) 如果圖G是無向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路．． (2) 圖G1，(如下圖所示) 是歐拉圖． 解：(1)錯(cuò)，圖G是無向圖，當(dāng)且僅當(dāng)G是連通的，且所有結(jié)點(diǎn)度數(shù)均為偶數(shù)，這里不能確定G圖是否是連通的

8、。 (2)錯(cuò)，由歐拉圖的定理“無向圖G具有一條歐拉路，當(dāng)且僅當(dāng)G是連通的，且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)”得到這里任何一個(gè)結(jié)點(diǎn)都沒有奇數(shù)度結(jié)點(diǎn)。 2．圖G2（如下圖所示）不是歐拉圖而是漢密爾頓圖． 解：錯(cuò)，既不是歐拉圖也不是漢密爾圖。歐拉圖要求所有結(jié)點(diǎn)度數(shù)均為偶數(shù)，這里結(jié)點(diǎn)b,d各有三個(gè)節(jié)點(diǎn)；漢密爾圖要求每一對結(jié)點(diǎn)度數(shù)之和大于等于總結(jié)點(diǎn)數(shù)，這里不滿足。 3．(1) 設(shè)G是一個(gè)有7個(gè)結(jié)點(diǎn)16條邊的連通圖，則G為平面圖． (2) 設(shè)G是一個(gè)連通平面圖，且有6個(gè)結(jié)點(diǎn)11條邊，則G有7個(gè)面．

9、 解：(1)錯(cuò)，沒有提到面。 (2)對，由歐拉定理得到：結(jié)點(diǎn)-邊+面=2，即為連通平面圖，這里6-11+7=2 4．下圖給出的樹是否同構(gòu)的． 解：(a)同構(gòu)，(b),(c)同構(gòu)。 因?yàn)橛蓤D的同構(gòu)相關(guān)聯(lián)，得到同構(gòu)的必要條件：(1)結(jié)點(diǎn)數(shù)目相同。(2)邊數(shù)相同。(3)度數(shù)相同的結(jié)點(diǎn)數(shù)目相同 故(a)不滿足，即不同構(gòu)。 四、計(jì)算題 1．設(shè)G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，

10、(v4,v5) }，試 (1) 給出G的圖形表示； (2) 寫出其鄰接矩陣； (3) 求出每個(gè)結(jié)點(diǎn)的度數(shù)； (4) 畫出其補(bǔ)圖的圖形． 解：(1) v1 v2 v3 v4 v5 (2)G= (3)v1度數(shù)為1，v2度數(shù)為2，v3度數(shù)為4，v4度數(shù)為3，v5度數(shù)為2 2．圖G=，其中V={a, b, c, d, e, f }，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e),

11、(d, f), (e, f) }，對應(yīng)邊的權(quán)值依次為5，2，1，2，6，1，9，3及8． (1) 畫出G的圖形； (2) 寫出G的鄰接矩陣； (3) 求出G權(quán)最小的生成樹及其權(quán)值． 解：(2)G= (3)最小生成樹是{(a,e),(e,c),(b,d),(d,f)}權(quán)值為 3．已知帶權(quán)圖G如右圖所示． (1) 求圖G的最小生成樹； (2)計(jì)算該生成樹的權(quán)值． 解：(1)最小生成樹為{1,4,3,2,7,5} (2)權(quán)值為22

12、 4．設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31，試畫出相應(yīng)的最優(yōu)二叉樹，計(jì)算該最優(yōu)二叉樹的權(quán)． 解：(1)圖畫在材料紙上 (2)由圖得到最優(yōu)二叉樹的權(quán)為：65 五、證明題 1．設(shè)G是一個(gè)n階無向簡單圖，n是大于等于3的奇數(shù)．證明圖G與它的補(bǔ)圖中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等． 證明：因?yàn)镚是n階無向簡單圖，且n是大于等于3的奇數(shù)，故無向圖的結(jié)點(diǎn)數(shù)為奇數(shù)，又對于任何圖有奇數(shù)度數(shù)和偶數(shù)度數(shù)之和是結(jié)點(diǎn)數(shù)的2倍，故G圖的度數(shù)為偶數(shù)，故中需要的是奇數(shù)的結(jié)點(diǎn)，偶數(shù)度數(shù)，故G和的奇數(shù)度數(shù)相同，頂點(diǎn)個(gè)數(shù)也是相同的。即證。 2．設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加條邊才能使其成為歐拉圖． 證明：由于是連通圖并且有k個(gè)奇數(shù)度的結(jié)點(diǎn)，根據(jù)定理“在任何圖中，度數(shù)奇數(shù)的結(jié)點(diǎn)必定是偶數(shù)個(gè)”得到，G圖中的結(jié)點(diǎn)數(shù)為偶數(shù)個(gè)；又連 通圖G要形成歐拉圖，必須是結(jié)點(diǎn)數(shù)為偶數(shù)的；又有結(jié)點(diǎn)度數(shù)的總和是邊數(shù)的2倍，則邊數(shù)E最少要達(dá)到E=，綜上所屬成立，即證。 8 / 8文檔可自由編輯打印