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

PAGEPAGE1離散數(shù)學(xué)圖論部分綜合練習(xí)一、單項(xiàng)選擇題 1．設(shè)圖G的鄰接矩陣為 則G的邊數(shù)為()． A．6B．5C．4D． 2．已知圖G的鄰接矩陣為，則G有（）．A．5點(diǎn)，8邊B．6點(diǎn)，7邊C．6點(diǎn)，8邊D．5點(diǎn)，7邊cabecabedf圖一A．deg(V)=2EB．deg(V)=EC．D．4．圖G如圖一所示，以下說(shuō)法正確的是()．A．{(a,d)}是割邊B．{(a,d)}是邊割集圖二C．{(d,e圖二D．{(a,d),(a,c)}是邊割集5．如圖二所示，以下說(shuō)法正確的是()．A．e是割點(diǎn)B．{a,e}是點(diǎn)割集C．{b,e}是點(diǎn)割集D．k0q2asy是點(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)(n≥2)，m條邊，當(dāng)（）時(shí)，K中存在歐拉回路．A．m為奇數(shù)B．n為偶數(shù)C．n為奇數(shù)D．m為偶數(shù)9．設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r=()．A．e－v＋2B．v＋e－2C．e－v－2D．e＋v＋210．無(wú)向圖G存在歐拉通路，當(dāng)且僅當(dāng)()．A．G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)B．G中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)C．G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)D．G連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)11．設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的()條邊，才能確定G的一棵生成樹(shù)．A．B．C．D．12．無(wú)向簡(jiǎn)單圖G是棵樹(shù)，當(dāng)且僅當(dāng)()．A．G連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1B．G連通且結(jié)點(diǎn)數(shù)比邊數(shù)少1C．G的邊數(shù)比結(jié)點(diǎn)數(shù)少1D．G中沒(méi)有回路．二、填空題cabedfcabedf圖四2．設(shè)給定圖G(如圖四所示)，則圖G的點(diǎ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ǔ)圖中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等．3．設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加條邊才能使其成為歐拉圖．參考解答一、單項(xiàng)選擇題1．B2．D3．C4．C5．A6．D7．D8．C9．A10．D11．A12．A二、填空題1．152．{f}，{c，e}3．W|S|4．所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)5．等于出度6．n為奇數(shù)7．v-e+r=28．39．e=v-110．411．512．313．0三、判斷說(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的歐拉回路為：（不惟一）：v5v1v2v4v6v3圖九v1(v1,v2)v2(v2,v3)v5v1v2v4v6v3圖九(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)單平面圖，若v≥3，則e≤3v-6．”四、計(jì)算題1．a(chǎn)1a2a3a4a5（3）圖G是單側(cè)連通圖，也是弱連通圖．2．v1v2v3v4vv1v2v3v4v5（2）鄰接矩陣為圖十（3）deg(v1)=2deg(v2)=3v1v2vv1v2v3v4v5deg(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）粗線表示最小的生成樹(shù)，如圖十五如圖十五最小的生成樹(shù)的權(quán)為1+1+2+3=7：5.解：注意算法執(zhí)行過(guò)程的數(shù)據(jù)要完整的表示。6．解：（1）最優(yōu)二叉樹(shù)如圖十六所示：32713551117341602910231942172453319565,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層結(jié)點(diǎn)，并從如圖十六上述數(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中的兩個(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ù)度的（度），于是若在G