1、.離散數學圖論局部綜合練習ooooocabedof圖一1設圖G，那么以下結論成立的是 ( )Adeg(V)=2E Bdeg(V)=EC D2圖G如圖一所示，以下說法正確的選項是 ( ) A(a, d)是割邊B(a, d)是邊割集 圖二C(d, e)是邊割集D(a, d) ,(a, c)是邊割集3如圖二所示，以下說法正確的選項是 ( )Ae是割點 Ba,e是點割集Cb, e是點割集 Dd是點割集4如圖三所示，以下說法正確的選項是 ( ) A(a, e)是割邊 B(a, e)是邊割集C(a, e) ,(b, c)是邊割集 D(d, e)是邊割集圖三5設有向圖a、b、c與d如圖四所示，那么以下結論成

2、立的是 ( )圖四 Aa是強連通的 Bb是強連通的Cc是強連通的 Dd是強連通的6設完全圖K有n個結點(n2)，m條邊，當 時，K中存在歐拉回路Am為奇數 Bn為偶數 Cn為奇數 Dm為偶數7設G是連通平面圖，有v個結點，e條邊，r個面，那么r= ( )Aev2 Bve2 Cev2 Dev28無向圖G存在歐拉通路，當且僅當( )AG中所有結點的度數全為偶數 BG中至多有兩個奇數度結點CG連通且所有結點的度數全為偶數DG連通且至多有兩個奇數度結點9設G是有n個結點，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹ABCD10無向簡單圖G是棵樹，當且僅當( )AG連通且邊數比結點數少

3、1 BG連通且結點數比邊數少1CG的邊數比結點數少1 DG中沒有回路二、填空題1圖G中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，那么G的邊數是ooooocabedof圖四2設給定圖G(如圖四所示)，那么圖G的點割集是3假設圖G=中具有一條漢密爾頓回路，那么對于結點集V的每個非空子集S，在G中刪除S中的所有結點得到的連通分支數為W，那么S中結點數|S|與W滿足的關系式為4無向圖G存在歐拉回路，當且僅當G連通且5設有向圖D為歐拉圖，那么圖D中每個結點的入度6設完全圖K有n個結點(n2)，m條邊，當時，K中存在歐拉回路7設G是連通平面圖，v, e, r分別表示G的結點數，邊數和面數，

4、那么v，e和r滿足的關系式8設連通平面圖G的結點數為5，邊數為6，那么面數為9結點數v與邊數e滿足關系的無向連通圖就是樹10設圖G是有6個結點的連通圖，結點的總度數為18，那么可從G中刪去條邊后使之變成樹11一棵無向樹T中有8個結點，4度，3度，2度的分支點各一個，T的樹葉數為 12設G是有6個結點，8條邊的連通圖，那么從G中刪去條邊，可以確定圖G的一棵生成樹13給定一個序列集合000，001，01，10，0，假設去掉其中的元素，那么該序列集合構成前綴碼三、判斷說明題1如圖六所示的圖G存在一條歐拉回路v1v2v3v5v4dbacefghn圖六2給定兩個圖G1，G2如圖七所示：1試判斷它們是否為

5、歐拉圖、漢密爾頓圖.并說明理由2假設是歐拉圖，請寫出一條歐拉回路v1v2v3v4v5v6ooooov5v1v2v4v6ov3圖八圖七3判別圖G(如圖八所示)是不是平面圖，并說明理由4設G是一個有6個結點14條邊的連通圖，那么G為平面圖四、計算題1設圖G=，其中V=a1,a2,a3,a4,a5,E=，1試給出G的圖形表示；2判斷圖G是強連通圖、單側連通圖還是弱連通圖.2設圖G=，V= v1，v2，v3，v4，v5，E= (v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試1畫出G的圖形表示； 2求出每個結點的度數；3畫出圖G的補圖的

6、圖形3設G=，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試1給出G的圖形表示；2求出每個結點的度數；3畫出其補圖的圖形4圖G=，其中V= a, b, c,d,e，E= (a, b), (a, c), (a, e), (b, d),(b, e), (c, e), (c, d), (d, e) ，對應邊的權值依次為2、1、2、3、6、1、4及5，試1畫出G的圖形； 2求出G權最小的生成樹及其權值5設有一組權為2,3,5,7,11,13,17,19,23,29,31,試1畫出相應的最優二叉樹；2計算它們

7、的權值6畫一棵帶權為1,2,2,3,4的最優二叉樹,計算它的權五、證明題1假設無向圖G中只有兩個奇數度結點，那么這兩個結點一定是連通的2設G是一個n階無向簡單圖，n是大于等于2的奇數證明圖G與它的補圖中的奇數度頂點個數相等3設連通圖G有k個奇數度的結點，證明在圖G中至少要添加條邊才能使其成為歐拉圖參考解答一、單項選擇題1C2C 3A 4D 5D 6C7A8D9A10A二、填空題1152f，c，e3W|S|4所有結點的度數全為偶數5等于出度6n為奇數7v-e+r =2839e=v-1104115123130三、判斷說明題 1解：正確 因為圖G為連通的，且其中每個頂點的度數為偶數 2解：1圖G1是

8、歐拉圖 因為圖G1中每個結點的度數都是偶數圖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的歐拉回路為：不惟一：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是平面圖因為只要把結點v2與v6的連線(v2, v6)拽到結點v1

9、的外面，把把結點v3與v6的連線(v3, v6)拽到結點v4, v5的外面，就得到一個平面圖，如圖九所示4解：錯誤 不滿足“設G是一個有v個結點e條邊的連通簡單平面圖，假設v3，那么e3v-6四、計算題1oooooa1a2a3a4a5解：1圖G是有向圖： 2圖G是單側連通圖，也是弱連通圖 2v1v2v3v4v5ooooo解：1圖G如圖十3deg(v1)=2deg(v2)=3v1v2v3v4v5ooooodeg(v3)=4deg(v4)=3deg(v5)=2 4補圖如圖十一圖十一3解：1G的圖形如圖十二圖十二2v1，v2，v3，v4，v5結點的度數依次為1，2，4，3，2 3補圖如圖十三：圖十三

10、4解：1G的圖形表示如圖十四： 圖十四2粗線表示最小的生成樹，如圖十五如圖十五最小的生成樹的權為1+1+2+3=7： 5解：1最優二叉樹如圖十六所示：ooooooooo3271355111734oo1602910ooo231942oo17o24o5331ooo9565方法Huffman：從2,3,5,7,11,13,17,19,23,29,31中選2,3為最低層結點，并從權數中刪去，再添上他們的和數，即5,5,7,11,13,17,19,23,29,31； 再從5,5,7,11,13,17,19,23,29,31中選5,5為倒數第2層結點，并從上述數列中刪去，再添上他們的和數，即7,10,11

11、,13,17,19,23,29,31；然后，從7,10,11,13,17,19,23,29,31中選7,10和11,13為倒數第3層結點，并從如圖十六上述數列中刪去，再添上他們的和數，即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=5056ooooooooo1223347512解：最優二叉樹如圖十七 如圖十七它的權為：13+23+22+32+42=27五、證明題1證明：用反證法設G中的兩個奇數度結點分別為u和v假設u和v不連通，即它們之間無任何通路，那么G至少有兩個連通分支G1，G2，且u和v分別屬于G1和G2，于是G1和G2各含有一個奇數度結點這與定理7.1.2的推論矛盾因而u和v一定是連通的2證明：設，那么是由n階無向完全圖的邊刪去E所得到的所以對于任意結點，u在G和中的度數之和等于u在中的度數由于n是大于等于2的奇數，從而的每個結點都是偶數度的度，