1、 離散數(shù)學(xué)圖論部分綜合練習(xí)ooooocabedof圖一1設(shè)圖G<V, E>，則下列結(jié)論成立的是 ( )Adeg(V)=2½E½ Bdeg(V)=½E½C D2圖G如圖一所示，以下說(shuō)確的是 ( ) A(a, d)是割邊B(a, d)是邊割集 圖二C(d, e)是邊割集D(a, d) ,(a, c)是邊割集3如圖二所示，以下說(shuō)確的是 ( )Ae是割點(diǎn) Ba,e是點(diǎn)割集Cb, e是點(diǎn)割集 Dd是點(diǎn)割集4如圖三所示，以下說(shuō)確的是 ( )A(a, e)是割邊 B(a, e)是邊割集C(a, e) ,(b, c)是邊割集 D(d, e)是邊割集圖三5設(shè)有

2、向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是 ( )圖四 A（a）是強(qiáng)連通的 B（b）是強(qiáng)連通的C（c）是強(qiáng)連通的D（d）是強(qiáng)連通的6設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n2)，m條邊，當(dāng)（ ）時(shí)，K中存在歐拉回路Am為奇數(shù) Bn為偶數(shù) Cn為奇數(shù) Dm為偶數(shù)7設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )Aev2 Bve2 Cev2 Dev28無(wú)向圖G存在歐拉通路，當(dāng)且僅當(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)9設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生

3、成樹(shù)ABCD10無(wú)向簡(jiǎn)單圖G是棵樹(shù)，當(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)有回路二、填空題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ù)是ooooocabedof圖四2設(shè)給定圖G(如圖四所示)，則圖G的點(diǎn)割集是3若圖G=<V,E>中具有一條漢密爾頓回路，則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S，在G中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為W，則S中結(jié)點(diǎn)數(shù)|S|與W滿(mǎn)足的關(guān)系式為4無(wú)向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且5設(shè)有向圖D為歐拉圖，則圖D中每個(gè)結(jié)點(diǎn)的入度6設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n³2

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

5、的圖G存在一條歐拉回路v1v2v3v5v4dbacefghn圖六2給定兩個(gè)圖G1，G2（如圖七所示）：（1）試判斷它們是否為歐拉圖、漢密爾頓圖？并說(shuō)明理由（2）若是歐拉圖，請(qǐng)寫(xiě)出一條歐拉回路v1v2v3v4v5v6ooooov5v1v2v4v6ov3圖八圖七3判別圖G(如圖八所示)是不是平面圖，并說(shuō)明理由4設(shè)G是一個(gè)有6個(gè)結(jié)點(diǎn)14條邊的連通圖，則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的圖

6、形表示；（2）判斷圖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）畫(huà)出G的圖形表示； （2）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（3）畫(huà)出圖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）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（3）畫(huà)出其補(bǔ)圖的圖形4圖G=<V, E&

7、gt;，其中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）畫(huà)出G的圖形； （2）求出G權(quán)最小的生成樹(shù)及其權(quán)值5設(shè)有一組權(quán)為2,3,5,7,11,13,17,19,23,29,31,試（1）畫(huà)出相應(yīng)的最優(yōu)二叉樹(shù)；（2）計(jì)算它們的權(quán)值6畫(huà)一棵帶權(quán)為1,2,2,3,4的最優(yōu)二叉樹(shù),計(jì)算它的權(quán)五、證明題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ǔ)圖中的奇

8、數(shù)度頂點(diǎn)個(gè)數(shù)相等3設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加條邊才能使其成為歐拉圖參考解答一、單項(xiàng)選擇題1C2C3A 4D 5D 6C7A8D9A10A二、填空題1152f，c，e3W£|S|4所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)5等于出度6n為奇數(shù)7v-e+r =2839e=v-1104115123130三、判斷說(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,

9、c) c(c, a)a問(wèn)題：請(qǐng)大家想一想，為什么圖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是平面圖因?yàn)橹灰呀Y(jié)點(diǎn)v2與v6的連線(xiàn)(v2, v6)拽到結(jié)點(diǎn)v1的外面，把把結(jié)點(diǎn)v3與v6的連線(xiàn)(v3, v6)拽到結(jié)點(diǎn)v4, v5的外面，就得到一個(gè)平面圖，如圖九所示4解：錯(cuò)誤 不滿(mǎn)足“設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡(jiǎn)單平面圖，若v3，則

10、e3v-6”四、計(jì)算題1oooooa1a2a3a4a5解：（1）圖G是有向圖： （2）圖G是單側(cè)連通圖，也是弱連通圖 2v1v2v3v4v5ooooo解：（1）圖G如圖十（3）deg(v1)=2deg(v2)=3v1v2v3v4v5ooooodeg(v3)=4deg(v4)=3deg(v5)=2 （4）補(bǔ)圖如圖十一圖十一3解：（1）G的圖形如圖十二圖十二（2）v1，v2，v3，v4，v5結(jié)點(diǎn)的度數(shù)依次為1，2，4，3，2 （3）補(bǔ)圖如圖十三：圖十三4解：（1）G的圖形表示如圖十四： 圖十四（2）粗線(xiàn)表示最小的生成樹(shù)，如圖十五如圖十五最小的生成樹(shù)的權(quán)為1+1+2+3=7： 5解：（1）最優(yōu)二叉樹(shù)

11、如圖十六所示：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,31中選7,10和11,13為倒數(shù)第3層

12、結(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=5056ooooooooo1223347512解：最優(yōu)二叉樹(shù)如圖十七 如圖十七它的權(quán)為：1´3+2´3+2´2+3´2+4´2=27五、證明題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)這與定理7.1.2的推論矛盾因而u和v一定是連通的2證明：設(shè)，則是由n階無(wú)向完全圖的邊刪去E所得到的所以對(duì)于任意結(jié)點(diǎn)，u在G和中的度數(shù)之和等于u在中的度數(shù)由于n是大于等于2的奇數(shù)，從