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

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

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

3、存在歐拉 回路.A . m為奇數(shù)B. n為偶數(shù)C. n為奇數(shù)D. m為偶數(shù)9. 設G是連通平面圖，有v個結點，e條邊，r個面，那么r=.A . e v+ 2B . v+ e 2C . e v 2D . e+ v+ 210. 無向圖G存在歐拉通路，當且僅當.A . G中所有結點的度數(shù)全為偶數(shù)B . G中至多有兩個奇數(shù)度結點C . G連通且所有結點的度數(shù)全為偶數(shù)D . G連通且至多有兩個奇數(shù)度結點11. 設G是有n個結點，m條邊的連通圖，必須刪去G的條邊，才能確定G的一棵生成樹.A . m n 1B . m nC . m n 1D . n m 112 .無向簡單圖G是棵樹，當且僅當A . G連通且

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

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

6、示的圖G存在一條歐拉回路.圖六2. 給定兩個圖G1，G2如圖七所示：1試判斷它們是否為歐拉圖、漢密爾頓圖？并說明理由.2假設是歐拉圖，請寫出一條歐拉回路.3 判別圖 并說明理由.圖Ga圖七G(如圖八所示)是不是平面圖,個有6個結點14條邊的連 通圖，貝U G為平面圖.4設G是四、計算題1 設圖GE1試給出V3V, E，其中 V ai, a2, a3, a4, a5 ,ai, a2 , a2, a4 , a3, ai , a4, a5 , a5, a2G的圖形表示；2求G的鄰接矩陣；3判斷圖G是強連通圖、單側連通圖還是弱連通圖?2 .設圖 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求出每個結點的度數(shù)；4畫出圖G的補圖的圖形.3. 設 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求出每個結點的度數(shù)；4畫出其補圖的圖形.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) ,對應邊的權值依次為 2、i、2、3、6、i、4及5 ,試i畫出G的圖形；2寫出G的鄰接矩陣；3求出G權最小的生成樹及其權值.5用Dijkstra算法求右圖中A點到其它各點的最短路徑6. 設有一組權為 2,3,5,7,11,13,17,19,23,29,31試1畫出相應的最優(yōu)二元樹；7. 給出右邊所示二元有序樹的o三種遍歷結果.五、證明題1 假設無向圖G中只有兩個奇數(shù)度結點，那么這兩個結點一定是連通的.2設G是一個n階無向簡單圖，n是大于等于2

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

10、圖.因為圖G2存在一條漢密爾頓回路不惟一：a(a, b)b(b, e) e(e, f) f (f, g) g(g, d) d(d, c) c(c, a)a問題：請大家想一想，為什么圖 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是平面圖.因為只要把結點V2與V6的連線(V2, V6)拽 到結點V1的外面，把把結點V3與V6的連線V3, V6拽到結點V4, V5的外面，

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

12、00001101101101101001103V1, V2, V3 , V4, V5 結點的度數(shù)依次為 1, 2, 4, 3, 24補圖如圖十三:4解：2鄰接矩陣：01101100111001101101111103粗線表示最小的生成樹，如圖十五最小的生成樹的權為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為最低層結點，并 從權數(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層結點，并從上述數(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層結點，并從 上述數(shù)列中刪去，再添上他們的和數(shù)，即 17,17,24,19,23,29,31;2權值為：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. 證明：用反證法.設G中的兩個奇數(shù)度結點分別為u和v.假設u和v 不連通，即它們之間無任何通路，那么 G至少有兩個連通分支 G1, G2，且u和v 分別屬于G1和G2,于是G1和G2各含有一個奇數(shù)度結點.這與定理的推論矛盾.因 而u和V 定是連通的.2. 證明：設G V,E ，G V,E .那么E是由n階無向完全圖Kn的邊 刪去E所得到的所以對于任意結點u V , u在G和G中的度數(shù)之和等于u在 Kn中的度數(shù)由于n是