姓 名： 學(xué) 號(hào)： 得 分： 教師簽名： 離散數(shù)學(xué)作業(yè)7離散數(shù)學(xué)圖論部分形成性考核書(shū)面作業(yè)本課程形成性考核書(shū)面作業(yè)共3次，內(nèi)容主要分別是圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型安排練習(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ò)程，完成并上交任課教師（不收電子稿）。并在07任務(wù)界面下方點(diǎn)擊“保存”和“交卷”按鈕，以便教師評(píng)分。一、單項(xiàng)選擇題1設(shè)圖G的鄰接矩陣為，則G的邊數(shù)為( D )A5 B6 C3 D42設(shè)圖G<V, E>，則下列結(jié)論成立的是 ( C )Adeg(V)=2E Bdeg(V)=EC D3設(shè)有向圖（a）、（b）、（c）與（d）如下圖所示，則下列結(jié)論成立的是( D )abdceooooo4題圖A（a）是強(qiáng)連通的 B（b）是強(qiáng)連通的C（c）是強(qiáng)連通的 D（d）是強(qiáng)連通的4給定無(wú)向圖G如右圖所示，下面給出的結(jié)點(diǎn)集子集中，不是點(diǎn)割集的為（ B ）Ab, d Bd Ca, c Db, eoaoooobcde5題圖5圖G如右圖所示，以下說(shuō)法正確的是 ( C ) A(a, c)是割邊B(a, c)是邊割集C(b, c)是邊割集D(a, c) ,(b, c)是邊割集6無(wú)向圖G存在歐拉通路，當(dāng)且僅當(dāng)(D )AG中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) BG中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)CG連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)DG連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)7若G是一個(gè)歐拉圖，則G一定是( C ) A平面圖 B漢密爾頓圖 C連通圖 D對(duì)偶圖 8設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( A ) Aev2 Bve2 Cev2 Dev29設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的( A )條邊，才能確定G的一棵生成樹(shù)A B C D10已知一棵無(wú)向樹(shù)T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度的分支點(diǎn)各一個(gè)，T的樹(shù)葉數(shù)為（D ）A8 B5 C4 D3二、填空題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 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=<V，E>是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若在G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于 n-1 ，則在G中存在一條漢密爾頓路6設(shè)無(wú)向圖G<V，E>是漢密爾頓圖，則V的任意非空子集V1，都有 W(G-V1) V17設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n2)，m條邊，當(dāng) 當(dāng)m=2n 時(shí)，K中存在歐拉回路8設(shè)圖G=<V,E>，其中|V|=n，|E|=m則圖G是樹(shù)當(dāng)且僅當(dāng)G是連通的，且m= 2V-2 9連通無(wú)向圖G有6個(gè)頂點(diǎn)9條邊，從G中刪去 4 條邊才有可能得到G的一棵生成樹(shù)T10設(shè)正則5叉樹(shù)的樹(shù)葉數(shù)為17，則分支數(shù)為i = 4 三、判斷說(shuō)明題（判斷下列各題，并說(shuō)明理由）1(1) 如果圖G是無(wú)向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路(2) 圖G1，(如下圖所示) 是歐拉圖 解：(1)錯(cuò)，圖G是無(wú)向圖，當(dāng)且僅當(dāng)G是連通的，且所有結(jié)點(diǎn)度數(shù)均為偶數(shù)，這里不能確定G圖是否是連通的。 (2)錯(cuò)，由歐拉圖的定理“無(wú)向圖G具有一條歐拉路，當(dāng)且僅當(dāng)G是連通的，且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)”得到這里任何一個(gè)結(jié)點(diǎn)都沒(méi)有奇數(shù)度結(jié)點(diǎn)。2圖G2（如下圖所示）不是歐拉圖而是漢密爾頓圖 解：錯(cuò)，既不是歐拉圖也不是漢密爾圖。歐拉圖要求所有結(jié)點(diǎn)度數(shù)均為偶數(shù)，這里結(jié)點(diǎn)b,d各有三個(gè)節(jié)點(diǎn)；漢密爾圖要求每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于總結(jié)點(diǎn)數(shù)，這里不滿(mǎn)足。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è)面解：(1)錯(cuò)，沒(méi)有提到面。 (2)對(duì)，由歐拉定理得到：結(jié)點(diǎn)-邊+面=2，即為連通平面圖，這里6-11+7=24下圖給出的樹(shù)是否同構(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)不滿(mǎn)足，即不同構(gòu)。四、計(jì)算題1設(shè)G=<V，E>，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試(1) 給出G的圖形表示； (2) 寫(xiě)出其鄰接矩陣；(3) 求出每個(gè)結(jié)點(diǎn)的度數(shù)； (4) 畫(huà)出其補(bǔ)圖的圖形解：(1) v1v2v3v4v5(2)G= (3)v1度數(shù)為1，v2度數(shù)為2，v3度數(shù)為4，v4度數(shù)為3，v5度數(shù)為22圖G=<V, E>，其中V=a, b, c, d, e, f ，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f) ，對(duì)應(yīng)邊的權(quán)值依次為5，2，1，2，6，1，9，3及8(1) 畫(huà)出G的圖形； (2) 寫(xiě)出G的鄰接矩陣；(3) 求出G權(quán)最小的生成樹(shù)及其權(quán)值解：(2)G= (3)最小生成樹(shù)是(a,e),(e,c),(b,d),(d,f)權(quán)值為3已知帶權(quán)圖G如右圖所示 (1) 求圖G的最小生成樹(shù)； (2)計(jì)算該生成樹(shù)的權(quán)值解：(1)最小生成樹(shù)為1,4,3,2,7,5 (2)權(quán)值為224設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31，試畫(huà)出相應(yīng)的最優(yōu)二叉樹(shù)，計(jì)算該最優(yōu)二叉樹(shù)的權(quán)解：(1)圖畫(huà)在材料紙上 (2)由圖得到最優(yōu)二叉樹(shù)的權(quán)為：65五、證明題1設(shè)G是一個(gè)n階無(wú)向簡(jiǎn)單圖，n是大于等于3的奇數(shù)證明圖G與它的補(bǔ)圖中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等證明：因?yàn)镚是n階無(wú)向簡(jiǎn)單圖，且n是大于等于3的奇數(shù)，故無(wú)向圖的結(jié)點(diǎn)數(shù)為奇數(shù)，又對(duì)于任何圖有奇數(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文檔可自由編輯打印