離散數(shù)學(xué)圖論部分經(jīng)典試題及答案(2024060324)

1、離散數(shù)學(xué)圖論局部綜合練習(xí)一、單項(xiàng)選擇題1 .設(shè)圖G的鄰接矩陣為01100).B.10011100000100101010那么G的邊數(shù)為(A. 62.圖5G的鄰接矩陣為C. 40001000110101那么G有A . 5 點(diǎn)，C . 6 點(diǎn)，丨.8邊8邊B . 6點(diǎn)，7邊D . 5點(diǎn)，7邊3.設(shè)圖G = <V, E>,那么以下結(jié)論成立的是(A . deg(V)=2 EB . deg(V)= EC . deg(v) 2E|Iv V4 .圖G如圖一所示，以下說法正確的選項(xiàng)是A .B .C .D .5.如圖二所示，以下說法正確的選項(xiàng)是(A . e是割點(diǎn)B . a,e是點(diǎn)割集C . b, e

2、是點(diǎn)割集D . d是點(diǎn)割集(a, d)是割邊(a, d)是邊割集(d, e)是邊割集(a, d) ,(a, c)是邊割集B. deg(V)=D. deg(v)v V).6.如圖三所示，以下說法正確的選項(xiàng)是A . (a, e)是割邊C. (a, e) ,(b, ©是邊割集E(圖一).).(a, e)是邊割集圖 (d, e)是邊割集圖三7設(shè)有向圖a、 b、 c與d如圖四所示，貝U以下結(jié)論成立的是圖四A a是強(qiáng)連通的B .b是強(qiáng)連通的.B . G連通且結(jié)點(diǎn)數(shù)比邊數(shù)少1D . G中沒有回路.C.c是強(qiáng)連通的D.d是強(qiáng)連通的應(yīng)該填寫：D8設(shè)完全圖Kn有n個(gè)結(jié)點(diǎn)n?2, m條邊，當(dāng) 丨時(shí)，K.中

3、存在歐拉 回路.A . m為奇數(shù)B. n為偶數(shù)C. n為奇數(shù)D. m為偶數(shù)9. 設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，那么r=.A . e v+ 2B . v+ e 2C . e v 2D . e+ v+ 210. 無向圖G存在歐拉通路，當(dāng)且僅當(dāng).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)11. 設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的條邊，才能確定G的一棵生成樹.A . m n 1B . m nC . m n 1D . n m 112 .無向簡(jiǎn)單圖G是棵樹，當(dāng)且僅當(dāng)A . G連通且

4、邊數(shù)比結(jié)點(diǎn)數(shù)少1C . G的邊數(shù)比結(jié)點(diǎn)數(shù)少1、填空題1 .圖G中有1個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn), 點(diǎn)，貝U G的邊數(shù)是.3個(gè)3度結(jié)點(diǎn)，4個(gè)4度結(jié)ce d圖四2. 設(shè)給定圖G如圖四所示，那么圖G的點(diǎn)割集是3 假設(shè)圖G=<V, E>中具有一條漢密爾頓回路， 那么對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S,在G中刪除S 中的所有結(jié)點(diǎn)得到的連通分支數(shù)為 W，那么S中結(jié)點(diǎn) 數(shù)|S與 W滿足的關(guān)系式為 .4無向圖G存在歐拉回路，當(dāng)且僅當(dāng) G連通 且.5設(shè)有向圖D為歐拉圖，那么圖D中每個(gè)結(jié)點(diǎn)的入度 應(yīng)該填寫：等于出度6設(shè)完全圖Kn有n個(gè)結(jié)點(diǎn)(n 2)，m條邊，當(dāng)時(shí)，匚 中存在歐拉回路.7設(shè)G是連通平面圖，v,e

5、,r分別表示G的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，那么v，e 和r滿足的關(guān)系式.8. 設(shè)連通平面圖G的結(jié)點(diǎn)數(shù)為5，邊數(shù)為6，那么面數(shù)為 .9. 結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足關(guān)系的無向連通圖就是樹.10. 設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18,那么可從G中刪去 條邊后使之變成樹.11. 一棵無向樹T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為 .12 .設(shè)G = <V, E>是有6個(gè)結(jié)點(diǎn)，8條邊的連通圖，那么從G中刪去條邊，可以確定圖G的一棵生成樹.13 .給定一個(gè)序列集合000, 001, 01，10，0，假設(shè)去掉其中的元素，那么該序列集合構(gòu)成前綴碼.三、判斷說明題1 .如圖六所

6、示的圖G存在一條歐拉回路.圖六2. 給定兩個(gè)圖G1，G2如圖七所示：1試判斷它們是否為歐拉圖、漢密爾頓圖？并說明理由.2假設(shè)是歐拉圖，請(qǐng)寫出一條歐拉回路.3 判別圖 并說明理由.圖Ga圖七G(如圖八所示)是不是平面圖,個(gè)有6個(gè)結(jié)點(diǎn)14條邊的連 通圖，貝U G為平面圖.4設(shè)G是四、計(jì)算題1 設(shè)圖GE1試給出V3V, E，其中 V ai, a2, a3, a4, a5 ,ai, a2 , a2, a4 , a3, ai , a4, a5 , a5, a2G的圖形表示；2求G的鄰接矩陣；3判斷圖G是強(qiáng)連通圖、單側(cè)連通圖還是弱連通圖?2 .設(shè)圖 G=<V, E>, V= vi , V2,

7、V3, V4, V5 , E= (vi, V2), (vi, V3), (V2, V3), (V2, V4),(V3, V4),(V3, V5),(V4, V5)，試i畫出G的圖形表示；2寫出其鄰接矩陣；2求出每個(gè)結(jié)點(diǎn)的度數(shù)；4畫出圖G的補(bǔ)圖的圖形.3. 設(shè) G=<V , E> , V= Vi , V2 , V3 , V4 , V5 , E=(Vi,V3),(V2,V3),(V2,V4),(V3,V4), (W,V5),(V4,V5)，試i給出G的圖形表示；2寫出其鄰接矩陣；3求出每個(gè)結(jié)點(diǎn)的度數(shù)；4畫出其補(bǔ)圖的圖形.4. 圖 G=<V, E> ,其中 V= a, b,

8、c, d, e , E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ,對(duì)應(yīng)邊的權(quán)值依次為 2、i、2、3、6、i、4及5 ,試i畫出G的圖形；2寫出G的鄰接矩陣；3求出G權(quán)最小的生成樹及其權(quán)值.5用Dijkstra算法求右圖中A點(diǎn)到其它各點(diǎn)的最短路徑6. 設(shè)有一組權(quán)為 2,3,5,7,11,13,17,19,23,29,31試1畫出相應(yīng)的最優(yōu)二元樹；7. 給出右邊所示二元有序樹的o三種遍歷結(jié)果.五、證明題1 假設(shè)無向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，那么這兩個(gè)結(jié)點(diǎn)一定是連通的.2設(shè)G是一個(gè)n階無向簡(jiǎn)單圖，n是大于等于2

9、的奇數(shù)證明圖G與它的 補(bǔ)圖G中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等.3設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加與條邊才能 使其成為歐拉圖.參考解答、單項(xiàng)選擇題1. B2. D9. A10. D3. C11. A4. C12. A5. A6. D7. D8. C二、填空題1. 152. f，c，e3. W |S|4.所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)5.等于出度6. n為奇數(shù)7. v-e+r =28. 39. e=v-110. 411. 512. 313. 0三、判斷說明題1 .解：正確.因?yàn)閳DG為連通的，且其中每個(gè)頂點(diǎn)的度數(shù)為偶數(shù).2.解：1圖Gi是歐拉圖.因?yàn)閳DGi中每個(gè)結(jié)點(diǎn)的度數(shù)都是偶數(shù).圖G2是漢密爾頓

10、圖.因?yàn)閳DG2存在一條漢密爾頓回路不惟一：a(a, b)b(b, e) e(e, f) f (f, g) g(g, d) d(d, c) c(c, a)a問題：請(qǐng)大家想一想，為什么圖 Gi不是漢密爾頓圖，圖G2不是歐拉圖 2圖Gi的歐拉回路為：不惟一：V3圖九vi(vi, V2) V2 (v2, V3) V3 (V3, V4)V4(V4, V5)V5 (V5, V2) V2 (V2, V6)V6 (V6, V4) V4 (V4, V1)V13. 解：圖G是平面圖.因?yàn)橹灰呀Y(jié)點(diǎn)V2與V6的連線(V2, V6)拽 到結(jié)點(diǎn)V1的外面，把把結(jié)點(diǎn)V3與V6的連線V3, V6拽到結(jié)點(diǎn)V4, V5的外面，

11、就得到一個(gè)平 面圖，如圖九所示.4. 解：錯(cuò)誤.不滿足“設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡(jiǎn)單平面圖，假設(shè)V?3,那么e< 3v-6.四、計(jì)算題1.解：1圖G是有向圖：2鄰接矩陣如下:a2a301000I00010/ 'A(D) 10000/700001a4a5a1010003圖G是單側(cè)連通圖，也是弱連通圖.2.解：1圖G如圖十2鄰接矩陣為圖十01100101101101101101001103deg(V1)=2 deg(v2)=3 deg(v3)=4 deg(V4)=3 deg=24補(bǔ)圖如圖十V2", V5V3V4圖十一3.解：1G的圖形如圖十二2鄰接矩陣：圖十二001

12、00001101101101101001103V1, V2, V3 , V4, V5 結(jié)點(diǎn)的度數(shù)依次為 1, 2, 4, 3, 24補(bǔ)圖如圖十三:4解：2鄰接矩陣：01101100111001101101111103粗線表示最小的生成樹，如圖十五最小的生成樹的權(quán)為1+1+2+3=7:5. 解：注意算法執(zhí)行過程的數(shù)據(jù)要完整的表示。6. 解：1最優(yōu)二叉樹如圖十六所示：方法Huffman：從 2,3,5,7,11,13,17 ,19,23,29,31中選2,3為最低層結(jié)點(diǎn)，并 從權(quán)數(shù)中刪去，再添上他們的和數(shù)，即 5,5,7,11,13,17,19,23,29,31再從 5,5,7,11,13,17,

13、19,23,29,31中選5,5為倒數(shù)第2層結(jié)點(diǎn)，并從上述數(shù)列中 刪去，再添上他們的和數(shù)，即7,10,11,13,17,19,23,29,31;然后，從 7,10,11,13,17,19,23,29,31 中 選7,10和11,13為倒數(shù)第3層結(jié)點(diǎn)，并從 上述數(shù)列中刪去，再添上他們的和數(shù)，即 17,17,24,19,23,29,31;2權(quán)值為：2 6+3 6+5 5+7 4+11 4+13 4+17 3+19 3+23 3+29 3+31 2=12+18+25+28+44+52+51+57+69+87+62=5057.解：a前根：a，b，d，g，e，h，i，c，fb中根：g，d，b，h，e，i，a，c，fc后根：g，d，h，i，e，b，f，c，a五、證明題1. 證明：用反證法.設(shè)G中的兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u和v.假設(shè)u和v 不連通，即它們之間無任何通路，那么 G至少有兩個(gè)連通分支 G1, G2，且u和v 分別屬于G1和G2,于是G1和G2各含有一個(gè)奇數(shù)度結(jié)點(diǎn).這與定理的推論矛盾.因 而u和V 定是連通的.2. 證明：設(shè)G V,E ，G V,E .那么E是由n階無向完全圖Kn的邊 刪去E所得到的所以對(duì)于任意結(jié)點(diǎn)u V , u在G和G中的度數(shù)之和等于u在 Kn中的度數(shù)由于n是