離散數(shù)學(xué)第七章檢測(cè)題

1、離散數(shù)學(xué)第七章檢測(cè)題一、單項(xiàng)選擇題每題2分，共20 分1 .以下圖中是哈密爾頓圖的是 2(1)(2)(3)(J)1.下面給出的四個(gè)圖中，哪個(gè)不是漢密爾頓圖4.(1) (2) 1.以下是歐拉圖的是2(1) (2) 1 .以下各圖不是歐拉圖的是2(1)(2)Q)1. 以下各圖不是歐拉圖的是42設(shè)A(G)是有向圖G：V,E：的鄰接矩陣，其第i列中“ 1的數(shù)目為()。(C)A .結(jié)點(diǎn)Vi的度數(shù);B 結(jié)點(diǎn)Vi的出度;C.結(jié)點(diǎn)Vi的入度；D .結(jié)點(diǎn)Vj的度數(shù)。2設(shè)A(G)是有向圖G V,E)的鄰接矩陣，其第i行中“1的數(shù)目為()。(B)A .結(jié)點(diǎn)Vi的度數(shù)；B .結(jié)點(diǎn)Vi的出度；C.結(jié)點(diǎn)Vi的入度；D .

2、結(jié)點(diǎn)Vj的度數(shù)。3.無(wú)向圖G中有16條邊，且每個(gè)結(jié)點(diǎn)的度數(shù)均為2，那么結(jié)點(diǎn)數(shù)是(B )A.8B.16C.4D.323.一個(gè)無(wú)向樹(shù)中有 6條邊，那么它結(jié)點(diǎn)數(shù)為(C ).A 5 ； B 6 ； C 7 ；D 8.3.設(shè)完全二叉樹(shù) T有t片葉子，e條邊，那么有(3).5. 假設(shè)圖G有一條路經(jīng)過(guò)圖中每個(gè)結(jié)點(diǎn)恰好一次,A.有一條歐拉路C.有一條漢密爾頓路6. 無(wú)向圖節(jié)點(diǎn)間的連通關(guān)系是一個(gè)A偏序關(guān)系；B相容關(guān)系；7. 下面哪一種圖不一定是樹(shù)(1).無(wú)圈連通圖；(3).每對(duì)結(jié)點(diǎn)間都有路的圖；&設(shè)G= V, E為無(wú)向圖，VB.是歐拉圖D.是漢密爾頓圖: )C等價(jià)關(guān)系；).有n個(gè)結(jié)點(diǎn)n 1條邊的連通圖;

3、 連通但刪去一條邊就不連通的圖.D擬序關(guān)系.(1).完全圖;(2).零圖;7,E23，那么G 一定是.簡(jiǎn)單圖;(4).多重圖.(1). e 2(t 1) ；(2). e 2(t 1)；.e2(t 1);(4) . e 2(t1).4.假設(shè)具有n個(gè)結(jié)點(diǎn)的完全圖是歐拉圖，那么n為(B).A偶數(shù)；B奇數(shù)；C 9;D 10.4.無(wú)向圖G是歐拉圖，當(dāng)且僅當(dāng)().(1)(1). G連通且所有結(jié)點(diǎn)的度數(shù)為偶數(shù)；(2).G的所有結(jié)點(diǎn)的度數(shù)為偶數(shù)；(3). G連通且所有結(jié)點(diǎn)的度數(shù)為奇數(shù)；(4).G的所有結(jié)點(diǎn)的度數(shù)為奇數(shù).二、填空題每空1分，共20分1. 在以下圖中，結(jié)點(diǎn) V2的度數(shù)是，結(jié)點(diǎn)V5的度數(shù)是2在一棵根

4、樹(shù)中，有且只有一個(gè)結(jié)點(diǎn)的入度為0 ，其余所有結(jié)點(diǎn)的入度均為1 。2. 在一棵根樹(shù)中，入度為0 的結(jié)點(diǎn)稱(chēng)為樹(shù)根，出度為 0的結(jié)點(diǎn)稱(chēng)為樹(shù)葉。3設(shè)圖GG2 ME；,且E2 Ei，如果，那么稱(chēng)G2是Gi的子圖，如果，那么稱(chēng)G2是G1的生成子圖。V2 V1,V2 V1 4. 在任何圖G V,E中，degv=，其奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)必為v V偶數(shù) 。5. 一棵有9個(gè)葉結(jié)點(diǎn)的完全三叉樹(shù)，有_ 4 個(gè)內(nèi)點(diǎn)。5.一棵有6個(gè)葉結(jié)點(diǎn)的完全二叉樹(shù)，有_5_個(gè)內(nèi)點(diǎn)：而假設(shè)一棵樹(shù)有 2個(gè)結(jié)點(diǎn)度數(shù)為2,一個(gè)結(jié)點(diǎn)度數(shù)為3, 3個(gè)結(jié)點(diǎn)度數(shù)為4，其余是葉結(jié)點(diǎn)，那么該樹(shù)有個(gè)葉結(jié)點(diǎn)。0 101/ 、10 116設(shè)圖 G V,E- , V

5、 V1,V2,V3,V4的鄰接矩陣 AG=,!110010 00那么V1的入度degV1= 3 ，從 V到V4長(zhǎng)度為2的路共有1 條。三、答題每題6分，共30分0 10 1 . 10 111 .設(shè)圖 G V,E , V V1 , V2 , V3 , V4的鄰接矩陣 AG=110 010 0 0 求V1的入度degVf , V4的出度degV4，及從 V到V4長(zhǎng)度為2的路徑的條數(shù) 。 解：degV1=3： 2分degV4=1: 2分從v到V4長(zhǎng)度為2的路徑有1條2分。1對(duì)有向圖G '；V,E；'，通過(guò)鄰接矩陣 A解以下問(wèn)題：1 從V4到V5長(zhǎng)度為4的路有幾條?2 G V,E 中長(zhǎng)

6、度為3的回路有幾條?解:0100000110A000011000101000001101000203000100020300000330A 01000,A300110 , A410002020000022020004001101000203000所以，1從V4到V5長(zhǎng)度為4的路有4條。它們是：V1V2V4V1 ；V4V1V2V4V5 ；V4V5V2V3V5 ； V4V5V2V4V。2GV, E中長(zhǎng)度為3的回路有3條。它們是：V1V2V4V1 ；V2V4V5V2 ； V2V3VV2。1對(duì)有向圖G V,E 求解以下問(wèn)題：1寫(xiě)出鄰接矩陣A；2G V,E 中長(zhǎng)度為3的不同的路有幾條？其中不同的回路有幾

7、條？并請(qǐng)羅列 說(shuō)明。解：1鄰接矩陣為:0010010010A00001110000001000110110010000100010(2)A200010 ,A31100001101001111100001101那么，GME，中長(zhǎng)度為3的不同的路有10條，其中有1條不同的回路。它們是：V1V5V4v1 也是回路；V1V5V4V2 ； <1V2V3V5 ；V2V3V5V4；V3V5v4m;V3V5V4V2；V4V1V2V3；V4V2V3V5;V5V4V1V2；V5V4V2V3 02. 棵樹(shù)有2個(gè)2度結(jié)點(diǎn)，1個(gè)3度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn)，求其葉結(jié)點(diǎn)的數(shù)目.設(shè)葉結(jié)點(diǎn)數(shù)目為t,那么由 degv =2 |

8、 E |及| E | = |v|-1 得：2分v V2X2 + 1X3 + 3X4+t = 22 + 1 + 3 + t-12 分解之得：t = 9.2.設(shè)有2 8盞燈，擬公用一個(gè)電源，求至少需要4插頭的接線(xiàn)板的數(shù)目。解：設(shè)至少需要4插頭的接線(xiàn)板i個(gè)，那么有4-1 i=28-12 分故i=9即至少需要9個(gè)4插頭的接線(xiàn)板。1分2.一棵樹(shù)有2個(gè)4度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，其余結(jié)點(diǎn)都是葉子，求其葉結(jié)點(diǎn)的數(shù)目。2. 設(shè)有33盞燈，擬公用一個(gè)電源，求至少需要5插頭的接線(xiàn)板的數(shù)目。解：設(shè)至少需要5插頭的接線(xiàn)板i個(gè)，那么有5-1 i=33-12 分故i=8即至少需要8個(gè)5插頭的接線(xiàn)板。1分3. 設(shè)有6個(gè)城市V1

9、, V2,，V6，它們之間有輸油管連通，其布置如以下圖，S數(shù)字中 Si為邊的編號(hào)，括號(hào)內(nèi)數(shù)字為邊的權(quán)，它是兩城市間的距離，為了保衛(wèi)油管不受破壞，在每段油管間派一連士兵看守，為保證每個(gè)城市石油的正常供給最少需多少連士兵看守？輸油管道總長(zhǎng)度越短，士兵越好防守。求他們看守的最短管道的長(zhǎng)度。要求寫(xiě)出求解過(guò)程解：為保證每個(gè)城市石油的正常供給最少需5連士兵看守求看守的最短管道相當(dāng)于求圖的最小生成樹(shù)問(wèn)題，此圖的最小生成樹(shù)為:因此看守的最短管道的長(zhǎng)度為:W(T)=1 +1 + 2+ 2+ 2=8.3今有煤氣站 A，將給一居民區(qū)供給煤氣，居民區(qū)各用戶(hù)所在位置如下圖，鋪設(shè)各用戶(hù) 點(diǎn)的煤氣管道所需的費(fèi)用 單位：萬(wàn)元

10、如圖邊上的數(shù)字所示。要求設(shè)計(jì)一個(gè)最經(jīng)濟(jì)的煤氣管道路線(xiàn)，并求所需的總費(fèi)用。解：該問(wèn)題相當(dāng)于求圖的最小生成樹(shù)問(wèn)題，此圖的最小生成樹(shù)為:4分因此如圖鋪設(shè)煤氣管道所需費(fèi)用最小，最小費(fèi)用為：WT= 2+ 2 + 2+ 2+ 2+ 2 + 2+3 +3 +4+1 = 25.2 分3以下圖給出的賦權(quán)圖表示八個(gè)城市及架起城市間直接通訊線(xiàn)路的預(yù)測(cè)造價(jià).試給出一個(gè)設(shè)計(jì)方案使得各城市間能夠通訊且總造價(jià)最小，并計(jì)算出最小造價(jià).解：該問(wèn)題相當(dāng)于求上圖的最小生成樹(shù)。1分按以下圖架起八個(gè)城市間直接通訊線(xiàn)路的造價(jià)最小.最小造價(jià)為:W T =180+240+200+280+120+90+220=13302 分2 分3.以下圖給

11、出的賦權(quán)圖表示七個(gè)城市a,b,c,d,e ,f,g及架起城市間直接通訊線(xiàn)路的預(yù)測(cè)造價(jià).試給出一個(gè)設(shè)計(jì)方案使得各城市間能夠通訊且總造價(jià)最小，并計(jì)算出最小造價(jià).Tg3. (6分)某發(fā)電廠(chǎng)a要向b,c,d,e四個(gè)地點(diǎn)送電，發(fā)電廠(chǎng)可以和 b,c,d直接架接電線(xiàn)，地 點(diǎn)e可以和b與d直接架設(shè)電線(xiàn)，其他由于地理原因無(wú)法直接架設(shè)電線(xiàn)，在a, b, c , d和e之間架設(shè)電線(xiàn)時(shí)不能有回路存在，否那么會(huì)造成浪費(fèi)。請(qǐng)找出所有電線(xiàn)架設(shè)方案，使從a可向b，c ，d，e 供電。解：分別用5個(gè)結(jié)點(diǎn)代表a, b,c, d, e,將可以直接架接電線(xiàn)的結(jié)點(diǎn)之間連一條線(xiàn)，便 得到下面的圖A，由于在a, b, c ,d和e之間架設(shè)

12、電線(xiàn)時(shí)不能有回路存在，而且還要使得從a可向b，c，d，e供電，這樣的電線(xiàn)架設(shè)方案相當(dāng)于是圖 A的最小生成樹(shù)，所以所有電線(xiàn) 架設(shè)方案有如下4種：4.有向圖 G :V,E；：，其中 V a,b,c,d，E ；a,b： ,：a,c；： ,；c,b. ,：c,d.d,a ,(1 )求G的鄰接矩陣A ;(2)用矩陣法判斷該有向圖的連通性。解：0 1100 0 0 0(1) A0 10 110 0 0(2)010110002 0000 30000A2,A310000110011001011111其可達(dá)性矩陣為P000011111111故該有向圖不強(qiáng)連通、是單側(cè)連通的。5. (6分)設(shè)有a,b,c,d, e

13、, f, g等七個(gè)人，a會(huì)講英語(yǔ)；b會(huì)講英語(yǔ)、漢語(yǔ)；c會(huì)講英、 俄語(yǔ)；d會(huì)講日、漢語(yǔ)；e會(huì)講德語(yǔ)、俄語(yǔ)；f會(huì)講法語(yǔ)、日語(yǔ)；g會(huì)講法語(yǔ)、德語(yǔ)。試用圖論方法安排園桌座位，使每人都能與其身邊的人交談。解 分別用7個(gè)結(jié)點(diǎn)代表a,b,c,d,e, f,g七個(gè)人，將會(huì)講同一種語(yǔ)言的人之間連一條線(xiàn)，便得到下面的圖A，容易看出該圖有哈密爾頓回路，圖B便是圖A的一條哈密爾頓回路，于是按此回路安排園桌座位，便能使每人都能與其身邊的人交談。5.一次學(xué)術(shù)會(huì)議的理事會(huì)共有20個(gè)人參加，他們之間有的相互認(rèn)識(shí)，但有的相互不認(rèn)識(shí)。但對(duì)任意兩個(gè)人，他們各自認(rèn)識(shí)的人的數(shù)目之和不小于20,說(shuō)明能否把這20個(gè)人排在圓桌旁，使得任意一

14、個(gè)人認(rèn)識(shí)其旁邊的兩個(gè)人？根據(jù)是什么？解：可以把這20個(gè)人排在圓桌旁，使得任意一個(gè)人認(rèn)識(shí)其旁邊的兩個(gè)人。(1分)根據(jù)是：分別用20個(gè)結(jié)點(diǎn)代表這20個(gè)人，將相互認(rèn)識(shí)的人之間連一條線(xiàn)，便得到一個(gè)無(wú)向簡(jiǎn)單圖 G 'V,E，每個(gè)結(jié)點(diǎn) Vi V的度數(shù)是與 y認(rèn)識(shí)的人的數(shù)目，由題意知Vi,Vj V ,有deg(Vi) deg(Vj) 20,于是G ： V, E中存在哈密爾頓回路，設(shè)CvhVi2L Vi20vh是G；V,E中的一條哈密爾頓回路，按此回路安排園桌座位即符合要求。6.以給定權(quán)1,4, 9, 16, 25, 36, 49, 64, 81, 100構(gòu)造一棵最優(yōu)二叉樹(shù)。go(3分)四.證明與應(yīng)用題(共30分)1. (10分)某次聚會(huì)的成員到會(huì)后相互握手，試用圖論的知識(shí)說(shuō)明與奇數(shù)個(gè)人握手的人 數(shù)一定是一個(gè)偶數(shù)。證：用結(jié)點(diǎn)代表成員，握手的成員之間連一條線(xiàn)，那么所有聚會(huì)的成員之間的握手 情況可以用一個(gè)圖來(lái)表示，其中每個(gè)結(jié)點(diǎn)的度數(shù)就是該結(jié)點(diǎn)所代表的成員握 手的人數(shù)，由于任