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

PAGEPAGE1離散數(shù)學圖論部分綜合練習一、單項選擇題 1．設(shè)圖G的鄰接矩陣為 則G的邊數(shù)為()． A．6B．5C．4D． 2．已知圖G的鄰接矩陣為，則G有（）．A．5點，8邊B．6點，7邊C．6點，8邊D．5點，7邊cabecabedf圖一A．deg(V)=2EB．deg(V)=EC．D．4．圖G如圖一所示，以下說法正確的是()．A．{(a,d)}是割邊B．{(a,d)}是邊割集圖二C．{(d,e圖二D．{(a,d),(a,c)}是邊割集5．如圖二所示，以下說法正確的是()．A．e是割點B．{a,e}是點割集C．{b,e}是點割集D．ipyffi2是點割集 6．如圖三所示，以下說法正確的是()．A．{(a,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é)點(n≥2)，m條邊，當（）時，K中存在歐拉回路．A．m為奇數(shù)B．n為偶數(shù)C．n為奇數(shù)D．m為偶數(shù)9．設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r=()．A．e－v＋2B．v＋e－2C．e－v－2D．e＋v＋210．無向圖G存在歐拉通路，當且僅當()．A．G中所有結(jié)點的度數(shù)全為偶數(shù)B．G中至多有兩個奇數(shù)度結(jié)點C．G連通且所有結(jié)點的度數(shù)全為偶數(shù)D．G連通且至多有兩個奇數(shù)度結(jié)點11．設(shè)G是有n個結(jié)點，m條邊的連通圖，必須刪去G的()條邊，才能確定G的一棵生成樹．A．B．C．D．12．無向簡單圖G是棵樹，當且僅當()．A．G連通且邊數(shù)比結(jié)點數(shù)少1B．G連通且結(jié)點數(shù)比邊數(shù)少1C．G的邊數(shù)比結(jié)點數(shù)少1D．G中沒有回路．二、填空題cabedfcabedf圖四2．設(shè)給定圖G(如圖四所示)，則圖G的點割五、證明題1．若無向圖G中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定是連通的．2．設(shè)G是一個n階無向簡單圖，n是大于等于2的奇數(shù)．證明圖G與它的補圖中的奇數(shù)度頂點個數(shù)相等．3．設(shè)連通圖G有k個奇數(shù)度的結(jié)點，證明在圖G中至少要添加條邊才能使其成為歐拉圖．參考解答一、單項選擇題1．B2．D3．C4．C5．A6．D7．D8．C9．A10．D11．A12．A二、填空題1．152．{f}，{c，e}3．W|S|4．所有結(jié)點的度數(shù)全為偶數(shù)5．等于出度6．n為奇數(shù)7．v-e+r=28．39．e=v-110．411．512．313．0三、判斷說明題1．解：正確．因為圖G為連通的，且其中每個頂點的度數(shù)為偶數(shù)．2．解：（1）圖G1是歐拉圖．因為圖G1中每個結(jié)點的度數(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的歐拉回路為：（不惟一）：v5v1v2v4v6v3圖九v1(v1,v2)v2(v2,v3)v5v1v2v4v6v3圖九(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,v5的外面，就得到一個平面圖，如圖九所示．4．解：錯誤．不滿足“設(shè)G是一個有v個結(jié)點e條邊的連通簡單平面圖，若v≥3，則e≤3v-6．”四、計算題1．a(chǎn)1a2a3a4a5（3）圖G是單側(cè)連通圖，也是弱連通圖．2．v1v2v3v4vv1v2v3v4v5（2）鄰接矩陣為圖十（3）deg(v1)=2deg(v2)=3v1v2vv1v2v3v4v5deg(v4)=3deg(v5)=2（4）補圖如圖十一圖十一3．解：（1）G的圖形如圖十二（2）鄰接矩陣：圖十二（3）v1，v2，v3，v4，v5結(jié)點的度數(shù)依次為1，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)二叉樹如圖十六所示：32713551117341602910231942172453319565,19,23,29,31中選2,3為最低層結(jié)點，并從權(quán)數(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層結(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的奇數(shù)，從而的每個結(jié)點都是偶數(shù)度的（度），于是若在G