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

PAGEPAGE1離散數(shù)學圖論部分綜合練習一、單項選擇題 1．設圖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．v7jhrn7是點割集 6．如圖三所示，以下說法正確的是()．A．{(a,e)}是割邊 B．{(a,e)}是邊割集C．{(a,e),(b,c)}是邊割集D．{(d,e)}是邊割集圖三7．設有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結論成立的是()．圖四A．（a）是強連通的B．（b）是強連通的C．（c）是強連通的D．（d）是強連通的應該填寫：D 8．設完全圖K有n個結點(n≥2)，m條邊，當（）時，K中存在歐拉回路．A．m為奇數(shù)B．n為偶數(shù)C．n為奇數(shù)D．m為偶數(shù)9．設G是連通平面圖，有v個結點，e條邊，r個面，則r=()．A．e－v＋2B．v＋e－2C．e－v－2D．e＋v＋210．無向圖G存在歐拉通路，當且僅當()．A．G中所有結點的度數(shù)全為偶數(shù)B．G中至多有兩個奇數(shù)度結點C．G連通且所有結點的度數(shù)全為偶數(shù)D．G連通且至多有兩個奇數(shù)度結點11．設G是有n個結點，m條邊的連通圖，必須刪去G的()條邊，才能確定G的一棵生成樹．A．B．C．D．12．無向簡單圖G是棵樹，當且僅當()．A．G連通且邊數(shù)比結點數(shù)少1B．G連通且結點數(shù)比邊數(shù)少1C．G的邊數(shù)比結點數(shù)少1D．G中沒有回路．二、填空題cabedfcabedf圖四2．設給定圖G(如圖四所示)，則圖G的點割五、證明題1．若無向圖G中只有兩個奇數(shù)度結點，則這兩個結點一定是連通的．2．設G是一個n階無向簡單圖，n是大于等于2的奇數(shù)．證明圖G與它的補圖中的奇數(shù)度頂點個數(shù)相等．3．設連通圖G有k個奇數(shù)度的結點，證明在圖G中至少要添加條邊才能使其成為歐拉圖．參考解答一、單項選擇題1．B2．D3．C4．C5．A6．D7．D8．C9．A10．D11．A12．A二、填空題1．152．{f}，{c，e}3．W|S|4．所有結點的度數(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中每個結點的度數(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是平面圖．因為只要把結點v2與v6的連線(v2,v6)拽到結點v1的外面，把把結點v3與v6的連線(v3,v6)拽到結點v4,v5的外面，就得到一個平面圖，如圖九所示．4．解：錯誤．不滿足“設G是一個有v個結點e條邊的連通簡單平面圖，若v≥3，則e≤3v-6．”四、計算題1．a1a2a3a4a5（3）圖G是單側連通圖，也是弱連通圖．2．v1v2v3v4vv1v2v3v4v5（2）鄰接矩陣為圖十（3）deg(v1)=2deg(v2)=3v1v2vv1v2v3v4v5deg(v4)=3deg(v5)=2（4）補圖如圖十一圖十一3．解：（1）G的圖形如圖十二（2）鄰接矩陣：圖十二（3）v1，v2，v3，v4，v5結點的度數(shù)依次為1，2，4，3，2（4）補圖如圖十三：圖十三4．解：（1）G的圖形表示如圖十四：圖十四（2）鄰接矩陣：（3）粗線表示最小的生成樹，如圖十五如圖十五最小的生成樹的權為1+1+2+3=7：5.解：注意算法執(zhí)行過程的數(shù)據(jù)要完整的表示。6．解：（1）最優(yōu)二叉樹如圖十六所示：32713551117341602910231942172453319565,19,23,29,31中選2,3為最低層結點，并從權數(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層結點，并從上述數(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層結點，并從如圖十六上述數(shù)列中刪去，再添上他們的和數(shù)，即17,17,24,19,23,29,31；……（2）權值為：26+36+55+74+114+134+173+193+233+293+312=12+18+25+28+44+52+51+57+69+87+62=5057．解：ａ）前根：ａ，ｂ，ｄ，ｇ，ｅ，ｈ，ｉ，ｃ，ｆｂ）中根：ｇ，ｄ，ｂ，ｈ，ｅ，ｉ，ａ，ｃ，ｆｃ）后根：ｇ，ｄ，ｈ，ｉ，ｅ，ｂ，ｆ，ｃ，ａ五、證明題1．證明：用反證法．設G中的兩個奇數(shù)度結點分別為u和v．假設u和v不連通，即它們之間無任何通路，則G至少有兩個連通分支G1，G2，且u和v分別屬于G1和G2，于是G1和G2各含有一個奇數(shù)度結點．這與定理3.1.2的推論矛盾．因而u和v一定是連通的．2．證明：設，．則是由n階無向完全圖的邊刪去E所得到的．所以對于任意結點，u在G和中的度數(shù)之和等于u在中的度數(shù)．由于n是大于等于2的奇數(shù)，從而的每個結點都是偶數(shù)度的（度），于是若在G