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

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

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

3、且所有結(jié)點的度數(shù)全為偶數(shù)DG連通且至多有兩個奇數(shù)度結(jié)點11設(shè)G是有n個結(jié)點，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹A B C D12無向簡單圖G是棵樹，當且僅當( )AG連通且邊數(shù)比結(jié)點數(shù)少1 BG連通且結(jié)點數(shù)比邊數(shù)少1CG的邊數(shù)比結(jié)點數(shù)少1 DG中沒有回路二、填空題ooooocabedof圖四1已知圖G中有1個1度結(jié)點，2個2度結(jié)點，3個3度結(jié)點，4個4度結(jié)點，則G的邊數(shù)是 2設(shè)給定圖G(如圖四所示)，則圖G的點割集是 3若圖G=中具有一條漢密爾頓回路，則對于結(jié)點集V的每個非空子集S，在G中刪除S中的所有結(jié)點得到的連通分支數(shù)為W，則S中結(jié)點數(shù)|S|與W滿足的關(guān)系式為

4、4無向圖G存在歐拉回路，當且僅當G連通且 5設(shè)有向圖D為歐拉圖，則圖D中每個結(jié)點的入度 應(yīng)該填寫：等于出度6設(shè)完全圖K有n個結(jié)點(n2)，m條邊，當 時，K中存在歐拉回路7設(shè)G是連通平面圖，v, e, r分別表示G的結(jié)點數(shù)，邊數(shù)和面數(shù)，則v，e和r滿足的關(guān)系式 8設(shè)連通平面圖G的結(jié)點數(shù)為5，邊數(shù)為6，則面數(shù)為 9結(jié)點數(shù)v與邊數(shù)e滿足 關(guān)系的無向連通圖就是樹10設(shè)圖G是有6個結(jié)點的連通圖，結(jié)點的總度數(shù)為18，則可從G中刪去 條邊后使之變成樹11已知一棵無向樹T中有8個結(jié)點，4度，3度，2度的分支點各一個，T的樹葉數(shù)為 12設(shè)G是有6個結(jié)點，8條邊的連通圖，則從G中刪去 條邊，可以確定圖G的一棵生

5、成樹13給定一個序列集合000，001，01，10，0，若去掉其中的元素 ，則該序列集合構(gòu)成前綴碼三、判斷說明題1如圖六所示的圖G存在一條歐拉回路v1v2v3v5v4dbacefghn圖六 2給定兩個圖G1，G2（如圖七所示）：（1）試判斷它們是否為歐拉圖、漢密爾頓圖？并說明理由（2）若是歐拉圖，請寫出一條歐拉回路v1v2v3v4v5v6ooooov5v1v2v4v6ov3圖八 圖七3判別圖G(如圖八所示)是不是平面圖，并說明理由4設(shè)G是一個有6個結(jié)點14條邊的連通圖，則G為平面圖四、計算題1設(shè)圖G=，其中V=a1, a2, a3, a4, a5,E=，（1）試給出G的圖形表示；（2）求G的鄰

6、接矩陣；（3）判斷圖G是強連通圖、單側(cè)連通圖還是弱連通圖？2設(shè)圖G=，V= v1，v2，v3，v4，v5，E= (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) ，試（1）畫出G的圖形表示； （2）寫出其鄰接矩陣；（2）求出每個結(jié)點的度數(shù)； （4）畫出圖G的補圖的圖形3設(shè)G=，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試（1）給出G的圖形表示； （2）寫出其鄰接矩陣；（3）求出每個結(jié)點的度數(shù)； （4）畫出其補圖的圖形4圖G

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

8、設(shè)G是一個n階無向簡單圖，n是大于等于2的奇數(shù)證明圖G與它的補圖中的奇數(shù)度頂點個數(shù)相等 3設(shè)連通圖G有k個奇數(shù)度的結(jié)點，證明在圖G中至少要添加條邊才能使其成為歐拉圖參考解答一、單項選擇題1B 2D 3C 4C 5A 6D 7D 8C 9A 10D 11A 12A二、填空題115 2f，c，e 3W|S|4所有結(jié)點的度數(shù)全為偶數(shù) 5等于出度6n為奇數(shù) 7v-e+r =2 83 9e=v-1 104 115123 130三、判斷說明題 1解：正確 因為圖G為連通的，且其中每個頂點的度數(shù)為偶數(shù) 2解：（1）圖G1是歐拉圖 因為圖G1中每個結(jié)點的度數(shù)都是偶數(shù)圖G2是漢密爾頓圖因為圖G2存在一條漢密爾頓

9、回路（不惟一）： 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的歐拉回路為：（不惟一）：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是平面圖因為只要把結(jié)點v2與v6的連線(v2, v6)拽到結(jié)點v1的外面，把把結(jié)點v3與v6的連線(v3, v6)拽到結(jié)點v4,

10、 v5的外面，就得到一個平面圖，如圖九所示 4解：錯誤 不滿足“設(shè)G是一個有v個結(jié)點e條邊的連通簡單平面圖，若v3，則e3v-6”四、計算題1oooooa1a2a3a4a5解：（1）圖G是有向圖： （2）鄰接矩陣如下：（3）圖G是單側(cè)連通圖，也是弱連通圖 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結(jié)點的度數(shù)依次為1，

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

12、7,11,13,17,19,23,29,31中選5,5為倒數(shù)第2層結(jié)點，并從上述數(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é)點，并從 如圖十六上述數(shù)列中刪去，再添上他們的和數(shù)，即17,17,24,19,23,29,31； （2）權(quán)值為：26+36+55+74+114+134+173+193+233+293+312 =12+18+25+28+44+52+51+57+69+87+62=5057解：）前根：，）中根：，）后根：，五、證明題1證明：用反證法設(shè)G中的兩個奇數(shù)度結(jié)點分別為u和v假設(shè)u和v不連通，即它們之間無任何通路，則G至少有兩個連通分支G1，G2，且u和v分別屬于G1和G2，于是G1和G2各含有一個奇數(shù)度結(jié)點這與定理3.1.2的推論矛盾因而u和v一定是連通的2證明：設(shè)，則是由n階無向完全圖的邊刪去E所得到的所以對于任意結(jié)點，u在G和中的度數(shù)之和等于u在中的度數(shù)由于n是大于等于2的