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

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

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

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

4、非空子集S，在G中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為W，則S中結(jié)點(diǎn)數(shù)|S|與W滿足的關(guān)系式為 4無(wú)向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且 5設(shè)有向圖D為歐拉圖，則圖D中每個(gè)結(jié)點(diǎn)的入度 應(yīng)該填寫：等于出度6設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n³2)，m條邊，當(dāng) 時(shí)，K中存在歐拉回路7設(shè)G是連通平面圖，v, e, 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)系的無(wú)向連通圖就是樹10設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18，則可從G中刪去 條邊后使之變成樹11已知一棵無(wú)向樹T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度

5、的分支點(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，若去掉其中的元素 ，則該序列集合構(gòu)成前綴碼三、判斷說(shuō)明題1如圖六所示的圖G存在一條歐拉回路v1v2v3v5v4dbacefghn圖六 2給定兩個(gè)圖G1，G2（如圖七所示）：（1）試判斷它們是否為歐拉圖、漢密爾頓圖？并說(shuō)明理由（2）若是歐拉圖，請(qǐng)寫出一條歐拉回路v1v2v3v4v5v6ooooov5v1v2v4v6ov3圖八 圖七3判別圖G(如圖八所示)是不是平面圖，并說(shuō)明理由4設(shè)G是一個(gè)有6個(gè)結(jié)點(diǎn)14條邊的連

6、通圖，則G為平面圖四、計(jì)算題1設(shè)圖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是強(qiáng)連通圖、單側(cè)連通圖還是弱連通圖？2設(shè)圖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）求出每個(gè)結(jié)點(diǎn)的度數(shù)； （4）畫出圖G的補(bǔ)圖的圖形3設(shè)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）求出每個(gè)結(jié)點(diǎn)的度數(shù)； （4）畫出其補(bǔ)圖的圖形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) ，對(duì)應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5，試（1

8、）畫出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)二元樹； （2）計(jì)算它們的權(quán)值7給出右邊所示二元有序樹的三種遍歷結(jié)果五、證明題1若無(wú)向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定是連通的2設(shè)G是一個(gè)n階無(wú)向簡(jiǎn)單圖，n是大于等于2的奇數(shù)證明圖G與它的補(bǔ)圖中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等 3設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加條邊才能使其成為歐拉圖參考解答一、單項(xiàng)選擇題1B 2D 3C 4C 5A 6D 7D 8C

9、 9A 10D 11A 12A二、填空題115 2f，c，e 3W£|S|4所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) 5等于出度6n為奇數(shù) 7v-e+r =2 83 9e=v-1 104 115123 130三、判斷說(shuō)明題 1解：正確 因?yàn)閳DG為連通的，且其中每個(gè)頂點(diǎn)的度數(shù)為偶數(shù) 2解：（1）圖G1是歐拉圖 因?yàn)閳DG1中每個(gè)結(jié)點(diǎn)的度數(shù)都是偶數(shù)圖G2是漢密爾頓圖因?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問(wèn)題：請(qǐng)大家想一想，為什么圖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是平面圖因?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的外面，就得到一個(gè)平面圖，如圖九所示 4解：錯(cuò)誤 不滿足“設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡(jiǎn)單平面圖，若v3，則e3v-6”四、計(jì)算題1oooooa1a2a3a4a5解：（1）圖G是有向圖： （2）鄰接矩陣如下：（

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

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

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