(電大復(fù)習(xí))《離散數(shù)學(xué)》1-9作業(yè)答案--任務(wù)07答案

形成性考核 作業(yè) 1 離散數(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 的鄰接矩陣為0101010010000011100000100， 則 G 的邊數(shù)為 ( D ) A 5 B 6 C 3 D 4 2設(shè)圖 G ，則下列結(jié)論成立的是 ( C ) A deg(V)=2E B deg(V)=E CEvVv 2)deg( DEvVv )deg(3設(shè)有向圖（ a）、（ b）、（ c）與（ d）如 下 圖所示 ， 則下列結(jié)論成立的是 ( D ) 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 ） A b, d B d 姓 名： 學(xué) 號(hào)： 得 分： 教師簽名： a b d c e 4 題圖 形成性考核 作業(yè) 2 C a, c D b, e 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 ) 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 對(duì)偶圖 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設(shè) G 是有 n 個(gè)結(jié)點(diǎn)， m 條邊的連通圖，必須刪去 G 的 ( A )條邊，才能確定 G 的一棵生成樹(shù) A 1mn B mn C 1mn D 1nm 10 已知一棵無(wú)向 樹(shù) T 中有 8 個(gè)結(jié)點(diǎn)， 4 度， 3 度， 2 度的分支點(diǎn)各一個(gè)， T的樹(shù)葉數(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 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)的簡(jiǎn)單圖，若在 G 中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于 n-1 ，則在 G 中存在一條漢密爾頓路 6 設(shè)無(wú)向圖 G 是 漢密爾 頓圖，則 V 的任意非空子集 V1，都有 W(G-V1) V1 7 設(shè)完全圖 Kn有 n 個(gè)結(jié)點(diǎn) (n2)， m 條 邊， 當(dāng) 當(dāng) m=2n 時(shí)， Kn中存在歐拉回路 8 設(shè)圖 GV,E，其中 Vn， Em則圖 G 是樹(shù)當(dāng)且僅當(dāng) G 是連通的， a b c d e 5 題圖 形成性考核 作業(yè) 3 且 m 2V-2 9 連通無(wú)向圖 G 有 6 個(gè)頂點(diǎn) 9 條邊，從 G 中刪去 4 條邊才有可能得到 G 的一棵生成樹(shù) T 10 設(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ù)，這里不滿足。 形成性考核 作業(yè) 4 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=2 4下圖給出的樹(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)不滿足，即不同構(gòu)。 四、 計(jì)算題 形成性考核 作業(yè) 5 1 設(shè) G=， 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) (2)G=0110010110110110110000100(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), (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)值 v1 v2 v3 v4 v5 形成性考核 作業(yè) 6 解： (2)G=011000101011110010010001011001010110(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)值為 22 4設(shè)有一組權(quán)為 2, 3, 5, 7, 17, 31， 試畫(huà)出相應(yīng)的最優(yōu)二叉樹(shù) ， 計(jì)算 該 最優(yōu)二叉樹(shù) 的 權(quán) 形成性考核 作業(yè) 7 解： (1)圖畫(huà)在材料紙上 (2)由圖得到最優(yōu)二叉樹(shù)的權(quán)為： 65 五 、 證明 題 1 設(shè) G 是一個(gè) n 階無(wú)向簡(jiǎn)單圖， n 是大于等于 3 的奇數(shù)證明圖 G 與它的補(bǔ)圖 G 中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等 證明：因?yàn)?G 是 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ù)，故 G 中 需要的是奇數(shù)的結(jié)點(diǎn)，偶數(shù)度數(shù)，故 G 和 G 的奇數(shù)度數(shù)相同，頂點(diǎn)個(gè)數(shù)也是相同的。即證。 2 設(shè)連通圖 G 有 k 個(gè)奇數(shù)