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

1、離散數(shù)學圖論部分綜合練習一、單項選擇題1設圖G的鄰接矩陣為則G的邊數(shù)為( )A6 B5 C4 D32已知圖G的鄰接矩陣為 ，則G有（ ） A5點，8邊 B6點，7邊 C6點，8邊 D5點，7邊ooooocabedof圖一3設圖G<V, E>，則下列結論成立的是 ( )Adeg(V)=2½E½ Bdeg(V)=½E½C D4圖G如圖一所示，以下說法正確的是 ( ) A(a, d)是割邊B(a, d)是邊割集 圖二C(d, e)是邊割集D(a, d) ,(a, c)是邊割集5如圖二所示，以下說法正確的是 ( )Ae是割點 Ba, e是點割集Cb,

2、 e是點割集 Dd是點割集6如圖三所示，以下說法正確的是 ( ) A(a, e)是割邊 B(a, e)是邊割集C(a, e) ,(b, c)是邊割集 D(d, e)是邊割集 圖三7設有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結論成立的是 ( ) 圖四 A（a）是強連通的 B（b）是強連通的C（c）是強連通的 D（d）是強連通的應該填寫：D 8設完全圖K有n個結點(n2)，m條邊，當（ ）時，K中存在歐拉回路Am為奇數(shù) Bn為偶數(shù) Cn為奇數(shù) Dm為偶數(shù)9設G是連通平面圖，有v個結點，e條邊，r個面，則r= ( )Aev2 Bve2 Cev2 Dev210無向圖G存在歐拉通路，當且僅

3、當( )AG中所有結點的度數(shù)全為偶數(shù) BG中至多有兩個奇數(shù)度結點CG連通且所有結點的度數(shù)全為偶數(shù)DG連通且至多有兩個奇數(shù)度結點11設G是有n個結點，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹A B C D12無向簡單圖G是棵樹，當且僅當( )AG連通且邊數(shù)比結點數(shù)少1 BG連通且結點數(shù)比邊數(shù)少1CG的邊數(shù)比結點數(shù)少1 DG中沒有回路二、填空題ooooocabedof圖四1已知圖G中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，則G的邊數(shù)是 2設給定圖G(如圖四所示)，則圖G的點割集是 3若圖G=<V, E>中具有一條漢密爾頓回路，則對于結點集V的每個

4、非空子集S，在G中刪除S中的所有結點得到的連通分支數(shù)為W，則S中結點數(shù)|S|與W滿足的關系式為 4無向圖G存在歐拉回路，當且僅當G連通且 5設有向圖D為歐拉圖，則圖D中每個結點的入度 應該填寫：等于出度6設完全圖K有n個結點(n³2)，m條邊，當 時，K中存在歐拉回路7設G是連通平面圖，v, e, 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度

5、的分支點各一個，T的樹葉數(shù)為 12設G<V, E>是有6個結點，8條邊的連通圖，則從G中刪去 條邊，可以確定圖G的一棵生成樹13給定一個序列集合000，001，01，10，0，若去掉其中的元素 ，則該序列集合構成前綴碼三、判斷說明題1如圖六所示的圖G存在一條歐拉回路v1v2v3v5v4dbacefghn圖六 2給定兩個圖G1，G2（如圖七所示）：（1）試判斷它們是否為歐拉圖、漢密爾頓圖？并說明理由（2）若是歐拉圖，請寫出一條歐拉回路v1v2v3v4v5v6ooooov5v1v2v4v6ov3圖八 圖七3判別圖G(如圖八所示)是不是平面圖，并說明理由4設G是一個有6個結點14條邊的連

6、通圖，則G為平面圖四、計算題1設圖G=<V，E>，其中V=a1, a2, a3, a4, a5,E=<a1, a2>，<a2, a4>，<a3, a1>，<a4, a5>，<a5, a2>（1）試給出G的圖形表示；（2）求G的鄰接矩陣；（3）判斷圖G是強連通圖、單側連通圖還是弱連通圖？2設圖G=<V，E>，V= v1，v2，v3，v4，v5，E= (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) ，試（1）畫出G的圖形表示； （2）寫出

7、其鄰接矩陣；（2）求出每個結點的度數(shù)； （4）畫出圖G的補圖的圖形3設G=<V，E>，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試（1）給出G的圖形表示； （2）寫出其鄰接矩陣；（3）求出每個結點的度數(shù)； （4）畫出其補圖的圖形4圖G=<V, E>，其中V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，對應邊的權值依次為2、1、2、3、6、1、4及5，試（1

8、）畫出G的圖形； （2）寫出G的鄰接矩陣；（3）求出G權最小的生成樹及其權值5.用Dijkstra算法求右圖中A點到其它各點的最短路徑。6設有一組權為2,3,5,7,11,13,17,19,23,29,31,試（1）畫出相應的最優(yōu)二元樹； （2）計算它們的權值7給出右邊所示二元有序樹的三種遍歷結果五、證明題1若無向圖G中只有兩個奇數(shù)度結點，則這兩個結點一定是連通的2設G是一個n階無向簡單圖，n是大于等于2的奇數(shù)證明圖G與它的補圖中的奇數(shù)度頂點個數(shù)相等 3設連通圖G有k個奇數(shù)度的結點，證明在圖G中至少要添加條邊才能使其成為歐拉圖參考解答一、單項選擇題1B 2D 3C 4C 5A 6D 7D 8C

9、 9A 10D 11A 12A二、填空題115 2f，c，e 3W£|S|4所有結點的度數(shù)全為偶數(shù) 5等于出度6n為奇數(shù) 7v-e+r =2 83 9e=v-1 104 115123 130三、判斷說明題 1解：正確 因為圖G為連通的，且其中每個頂點的度數(shù)為偶數(shù) 2解：（1）圖G1是歐拉圖 因為圖G1中每個結點的度數(shù)都是偶數(shù)圖G2是漢密爾頓圖因為圖G2存在一條漢密爾頓回路（不惟一）： a(a, b)b(b, e) e(e, f) f (f, g) g(g, d) d(d, c) c(c, a)a問題：請大家想一想，為什么圖G1不是漢密爾頓圖，圖G2不是歐拉圖。（2）圖G1的歐拉回路為

10、：（不惟一）：ooooov5v1v2v4v6ov3圖九v1(v1, 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的外面，就得到一個平面圖，如圖九所示 4解：錯誤 不滿足“設G是一個有v個結點e條邊的連通簡單平面圖，若v3，則e3v-6”四、計算題1oooooa1a2a3a4a5解：（1）圖G是有向圖： （2）鄰接矩陣如下：（

11、3）圖G是單側連通圖，也是弱連通圖 2v1v2v3v4v5ooooo解：（1）圖G如圖十 （2）鄰接矩陣為 圖十 （3）deg(v1)=2 deg(v2)=3v1v2v3v4v5ooooodeg(v3)=4deg(v4)=3deg(v5)=2 （4）補圖如圖十一 圖十一3解：（1）G的圖形如圖十二 （2）鄰接矩陣： 圖十二 （3）v1，v2，v3，v4，v5結點的度數(shù)依次為1，2，4，3，2 （4）補圖如圖十三： 圖十三4解：（1）G的圖形表示如圖十四： 圖十四（2）鄰接矩陣： （3）粗線表示最小的生成樹，如圖十五 如圖十五最小的生成樹的權為1+1+2+3=7： 5. 解：注意算法執(zhí)行過程的數(shù)

12、據(jù)要完整的表示。6解：（1）最優(yōu)二叉樹如圖十六所示：ooooooooo3271355111734oo1602910ooo231942oo17o24o5331ooo9565方法（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,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,3

13、1中選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解：）前根：，）中根：，）后根：，五、證明題1證明：用反證法設G中的兩個奇數(shù)度結點分別為u和v假設u和v不連通，即它們之間無任何通路，則G至少有兩個連通分支G1，G2，且u和v分別屬于G1和G2，于是G1和G2各含有一個奇數(shù)度結點這與定理3.1.2的推論矛盾因而u和v一定是連通的2證明：設，則是由n階無向完全圖的邊刪去E所得到的所以對于任意結點，u在G和中的度數(shù)之和等于u在中的度數(shù)由于n是大于等于2的奇數(shù)，從而的每個結點都是偶數(shù)度的（度），于是若在