離散數(shù)學形考任務07答案

《離散數(shù)學形考任務07答案》由會員分享，可在線閱讀，更多相關《離散數(shù)學形考任務07答案（8頁珍藏版）》請在裝配圖網上搜索。

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

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

3、o o o o o 4題圖 A．（a）是強連通的 B．（b）是強連通的 C．（c）是強連通的 D．（d）是強連通的 4．給定無向圖G如右圖所示，下面給出的結 點集子集中，不是點割集的為（ B ）． A．{b, d} B．nb779tp 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 )． A．G中所有結點的度數(shù)全為偶數(shù) B．G中至多有兩個奇數(shù)度結點 C．G連通且所有結點的度數(shù)全為偶數(shù) D．G連通且至多有兩個奇數(shù)度結點 7．若G是一個歐拉圖，則G一定是( C )． A．平面圖 B．漢密爾頓圖 C．連通圖 D．對偶圖 8．設G是連通平面圖，有v個結點，e條邊，r個面，則r= ( A )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 9．

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

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

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

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

9、 解：(1)錯，沒有提到面。 (2)對，由歐拉定理得到：結點-邊+面=2，即為連通平面圖，這里6-11+7=2 4．下圖給出的樹是否同構的． 解：(a)同構，(b),(c)同構。 因為由圖的同構相關聯(lián)，得到同構的必要條件：(1)結點數(shù)目相同。(2)邊數(shù)相同。(3)度數(shù)相同的結點數(shù)目相同 故(a)不滿足，即不同構。 四、計算題 1．設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) 求出每個結點的度數(shù)； (4) 畫出其補圖的圖形． 解：(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) }，對應邊的權值依次為5，2，1，2，6，1，9，3及8． (1) 畫出G的圖形； (2) 寫出G的鄰接矩陣； (3) 求出G權最小的生成樹及其權值． 解：(2)G= (3)最小生成樹是{(a,e),(e,c),(b,d),(d,f)}權值為 3．已知帶權圖G如右圖所示． (1) 求圖G的最小生成樹； (2)計算該生成樹的權值． 解：(1)最小生成樹為{1,4,3,2,7,5} (2)權值為22

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