1、離散數學11春圖論部分綜合練習輔導大家好！本學期的第二次教學輔導活動現在開始，本次活動主要是針對第二單元圖論的重點學習內容進行輔導，方式同樣是通過講解一些典型的綜合練習作業題目，幫助大家進一步理解和掌握圖論的基本概念和方法圖論作為離散數學的一部分，主要介紹圖論的基本概念、理論與方法教學內容主要有圖的基本概念與結論、圖的連通性與連通度、圖的矩陣表示、最短路問題、歐拉圖與漢密爾頓圖、平面圖、對偶圖與著色、樹與生成樹、根樹及其應用等本次綜合練習主要是復習這一單元的主要概念與計算方法，與集合論一樣，也安排了五種類型，有單項選擇題、填空題，判斷說明題、計算題、證明題這樣的安排也是為了讓同學們熟悉期末考試

2、的題型，能夠較好地完成這一部分主要內容的學習下面是本學期第4，5次形考作業中的部分題目一、單項選擇題單項選擇題主要是第4次形考作業的部分題目第4次作業同樣也是由10個單項選擇題組成，每小題10分，滿分100分在每次作業在關閉之前，允許大家反復多次練習，系統將保留您的最好成績，希望大家要多練幾次，爭取好成績需要提醒大家的是每次練習的作業題目可能不一樣，請大家一定要認真閱讀題目 1設圖G<V, E>，vÎV，則下列結論成立的是 ( ) Adeg(v)=2½E½ B deg(v)=½E½ C D該題主要是檢查大家對握手定理掌握的情況復習握

3、手定理：定理3.1.1 設G是一個圖，其結點集合為V，邊集合為E，則也就是說，無向圖G的結點的度數之和等于邊數的兩倍正確答案：C 2設無向圖G的鄰接矩陣為，則G的邊數為( ) A6 B5 C4 D3主要是檢查對鄰接矩陣的概念理解是否到位大家要復習鄰接矩陣的定義，要記住當給定的簡單圖是無向圖時，鄰接矩陣為對稱的即當結點vi與vj相鄰時，結點vj與vi也相鄰，所以連接結點vi與vj的一條邊在鄰接矩陣的第i行第j列處和第j行第i列處各有一個1，題中給出的鄰接矩陣中共有10個1，故有10¸2=5條邊ooooabcdoe正確答案：B 3如右圖所示，以下說法正確的是 ( ) A(a, e)是割邊

4、 B(a, e)是邊割集C(a, e) ,(b, c)是邊割集 D(d, e)是邊割集先復習割邊、邊割集的定義： 定義3.2.9 設無向圖G=<V,E>為連通圖，若有邊集E1ÌE，使圖G刪除了E1的所有邊后，所得的子圖是不連通圖，而刪除了E1的任何真子集后，所得的子圖是連通圖，則稱E1是G的一個邊割集若某個邊構成一個邊割集，則稱該邊為割邊（或橋）因為刪除答案A或B或C中的邊后，得到的圖是還是連通圖，因此答案A、B、C是錯誤的正確答案：Doooabcdo 4圖G如由圖所示，以下說法正確的是 ( )Aa是割點 Bb, c是點割集Cb, d是點割集 Dc是點割集主要是檢查對點割

5、集、割點的概念理解的情況定義3.2.7 設無向圖G=<V, E>為連通圖，若有點集V1ÌV，使圖G刪除了V1的所有結點后，所得的子圖是不連通圖，而刪除了V1的任何真子集后，所得的子圖是連通圖，則稱V1是G的一個點割集若某個結點構成一個點割集，則稱該結點為割點從圖二中刪除結點b, c，得到的子圖是由不連通圖，而只刪除結點b或結點c，得到的子圖仍然是連通的，由定義可以知道，b, c是點割集所以正確答案：B 5設有向圖（a）、（b）、（c）與（d）如下圖所示，則下列結論成立的是( ) A（a）是強連通的 B（b）是強連通的C（c）是強連通的 D（d）是強連通的 我們先復習強連通

6、的概念：定義3.2.5 在簡單有向圖中，若在任何結點偶對中，至少從一個結點到另一個結點可達的，則稱圖G是單向（側）連通的； 若在任何結點偶對中，兩結點對互相可達，則稱圖G是強連通的正確答案：A問：上面的圖中，哪個僅為弱連通的？ 請大家要復習“弱連通”的概念 6設完全圖K有n個結點(n³2)，m條邊，當（ ）時，K中存在歐拉回路Am為奇數 Bn為偶數 Cn為奇數 Dm為偶數 我們先復習完全圖的概念： 定義3.1.6 簡單圖G=<V，E>中，若每一對結點間都有邊相連，則稱該圖為完全圖有n個結點的無向完全圖記為Kn由定義可知，完全圖Kn中的任一結點v到其它結點都有一條邊，共有n

7、-1條邊，即每個結點的度數是n-1，當n為奇數時，n-1為偶數由定理4.1.1的推論 一個無向圖具有一條歐拉回路，當且僅當該圖是連通的，并且它的結點度數都是偶數 所以，正確答案應該是C7若G是一個漢密爾頓圖，則G一定是( ) A平面圖 B對偶圖 C歐拉圖 D連通圖 我們先復習漢密爾頓圖的概念：定義4.2.1 給定圖G，若存在一條路經過圖G的每個結點一次且僅一次，則該路稱為漢密爾頓路；若存在一條回路經過圖G的每個結點一次且僅一次，則該回路稱為漢密爾頓回路； 具有漢密爾頓回路的圖稱為漢密爾頓圖由定義可知，漢密爾頓圖是連通圖所以，正確答案應該是D問：漢密爾頓圖為什么不一定是歐拉圖嗎？8設G是連通平面

8、圖，有v個結點，e條邊，r個面，則r= ( ) Aev2 Bve2 Cev2 Dev2 本題主要檢查大家是否掌握了歐拉定理 定理4.3.2（歐拉定理） 設連通平面圖G的結點數為v，邊數為e，面數為r，則歐拉公式v-e+r =2成立 由歐拉公式v-e+r =2，得到r = e- v+2所以，答案A是正確的9無向簡單圖G是棵樹，當且僅當( )AG連通且邊數比結點數少1 BG連通且結點數比邊數少1CG的邊數比結點數少1 DG中沒有回路可以運用教材中的定理5.1.1，可以作出正確選擇因為定理5.1.1中給出的圖T為樹的等價定義之一是圖T連通且e=v-1，其中e是邊數，v是結點數也就是說：無向簡單圖G是

9、棵樹，當且僅當G連通且邊數比結點數少1正確答案：A注：由上面的樹的等價定義可知，結點數v與邊數e滿足e=v-1關系的無向連通圖就是樹10已知一棵無向樹T中有8個結點，4度，3度，2度的分支點各一個，T的樹葉數為（ ） A8 B5 C4 D3正確答案：B設無向樹T的樹葉數為x，因為樹葉是度數為1的結點那么，由定理3.1.1（握手定理） 設G是一個圖，其結點集合為V，邊集合為E，則得 4+3+2+x=2（8-1），即x=5應選擇B下面的內容主要是第5次形考作業的部分題目二、填空題1已知圖G中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，則G的邊數是 也是檢查大家對握手定理掌握的情況因為

10、圖G中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，即，根據握手定理，邊數有ooooabcdoeof 應該填寫：152設給定圖G (如右圖所示)，則圖G的點割集是 本題還是檢查大家對點割集、割點的概念理解的情況點割集、割點的定義前面已經復習了，從圖G中刪除結點f，得到的子圖是不連通圖，即結點集f是點割集；同樣，從圖G中刪除結點c，e，得到的子圖也是不連通圖，那么結點集c, e也是點割集而刪除其他結點集都沒有滿足點割集、定義的集合，所以應該填寫：f、c, e3無向圖G存在歐拉回路，當且僅當G連通且 由定理4.1.1的推論 一個無向圖具有一條歐拉回路，當且僅當該圖是連通的，并且它的結點

11、度數都是偶數應該填寫：結點度數都是偶數4設G=<V，E>是具有n個結點的簡單圖，若在G中每一對結點度數之和大于等于 ，則在G中存在一條漢密爾頓路 定理4.2.2 設G=<V，E>是具有n個結點的簡單圖，若在G中每一對結點度數之和大于等于n-1，則在G中存在一條漢密爾頓路應該填寫：n-15設圖G是有6個結點的連通圖，結點的總度數為18，則可從G中刪去 條邊后使之變成樹（邊后，可以確定圖G的一棵生成樹）由握手定理（定理3.1.1）知道圖G有18¸2=9 條邊，又由定理5.1.1中給出的圖T為樹的等價定義之一是“圖T連通且e=v-1”，可以知道：應該填寫：4 6設正

12、則5叉樹的樹葉數為17，則分支數為i = 定理5.2.1 設有正則m叉樹，其樹葉數為t，分枝數為i，則(m-1)i=t-1 其中m=5， t=17，由(5-1)i=17-1，得i =4應該填寫：4三、判斷說明題1如果圖G是無向圖，且其結點度數均為偶數，則圖G存在一條歐拉回路 分析：先復習歐拉圖的判別定理：定理4.1.1的推論：一個無向圖具有一條歐拉回路，當且僅當該圖是連通的，并且它的結點度數都是偶數 解：不正確 因為題中的圖G沒有“連通”的條件2如下圖所示的圖G存在一條歐拉回路 解：不正確 因為圖G中結點b和c的度數是奇數注：這是一個漢密爾頓圖，但不是歐拉圖，它可以作為單向選擇題7解答之后提出

13、的問題的一個解答3設G是一個有7個結點16條邊的連通圖，則G為平面圖 分析：定理4.3.3 設G是一個有v個結點e條邊的連通簡單平面圖，若v3，則e3v-6利用該定理判斷本題解：不正確 因為題中的連通簡單平面圖有v=7個結點，e=16條邊，那么16³3´7-6=15，由定理4.3.3知道，圖G不是平面圖 4設G是一個連通平面圖，且有6個結點11條邊，則G有7個面分析：可以用平面圖中的歐拉公式：v-e+r =2來判斷，其中v為結點數，e為邊數，r為面數解：正確因為連通平面圖G有v=6個結點，e=11條邊，那么由歐拉公式計算得：r =2+ 11- 6 = 7個面四、計算題1設G

14、=<V，E>，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試(1) 給出G的圖形表示； (2) 寫出其鄰接矩陣；(3) 求出每個結點的度數； oooov1ov5v2v3v4 (4) 畫出其補圖的圖形解：(1) 因為V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，所以G的圖形表示為：(2) 分析：本題給定的簡單圖是無向圖，因此鄰接矩陣為對稱的即當結點vi與vj相鄰時，結點vj與vi也相鄰，所以連接結

15、點vi與vj的一條邊在鄰接矩陣的第i行第j列處和第j行第i列處各寫一個1；當結點vi與vj沒有邊連接時，鄰接矩陣的第i行第j列處和第j行第i列處各寫一個0鄰接矩陣： (3) 由G的圖形可知，v1，v2，v3，v4，v5結點的度數依次為1，2，4，3，2 oooov1ov5v2v3v4oooov1ov5v2v3v4(4) 由關于補圖的定義3.1.9可知，先畫出完全圖（見圖1），然后去掉原圖，可得補圖（見圖2）如下： 圖1 圖2注意：補圖中，如果沒有標出結點v3，則是錯的 2圖G=<V, E>，其中V= a, b, c, d, e，E= (a, b), (a, c), (a, e),

16、(b, d), (b, e), (c, e), (c, d), (d, e) ，對應邊的權值依次為2、1、2、3、6、1、4及5，試（1）畫出G的圖形； （2）寫出G的鄰接矩陣；（3）求出G權最小的生成樹及其權值解 （1）因為V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，所以G的圖形表示為：（2）由圖得圖G的鄰接矩陣為：（3）圖G有5個結點，其生成樹有4條邊，用Kruskal算法（避圈法）求其權最小的生成樹T：第1步，取具最小權1的邊(a, c)；第2步，取剩余邊中具最小權

17、1的邊(c, e)；第3步，取剩余邊中不與前2條邊構成回路的具最小權2的邊(a, b)；第4步，取剩余邊中不與前3條邊構成回路的具最小權3的邊(b, d)所求最小生成樹T如右下圖，其權為注意：在用避圈法求最小的生成樹的關鍵是：“取圖中權數最小的邊，且與前面取到的邊不構成圈”，很多學生只注意到取權數最小的邊了，而忽略了“不構成圈”的要求如果結點數少一個，邊數也少些，大家應該會做了吧3設有一組權為2, 3, 5, 7, 17, 31，試畫出相應的最優二叉樹，計算該最優二叉樹的權解：方法（Huffman）：從2, 3, 5, 7, 17, 31中選2, 3為最低層結點，并從權數中刪去，再添上他們的和

18、數，即5, 5, 7, 17, 31；ooooo32755173410oooo1731oo65再從5, 5, 7, 17, 31中選5, 5為倒數第2層結點，并從上述數列中刪去，再添上他們的和數，即7, 10, 17, 31； 然后，從7, 10, 17, 31中選7, 10為倒數第3層結點，并從上述數列中刪去，再添上他們的和數，即17, 17, 31； 最優二叉樹如右圖所示最優二叉樹權值為：2´5+3´5+5´4+7´3+17´2+31´1 =10+15+20+21+34+31=131講評：作業中最優二叉樹往往都能畫對了，但計算總權值時可能會把有些權的層數計算錯了，導致總權值計算錯誤，大家一定要細心注意：這3個計算題大家一定要掌握五、證明題證明題同學一般都做不好，原因是對證明題方法沒有掌握，也是對一些概念不清楚所造成的因此，希望大家認真學習教材和老師講課中的證明方法，并通過作業逐步掌握做證明題的方法1設G是一個n階無向簡單圖，n是大于等于3的奇數證明圖G與它的補圖中的奇數度頂點個數相等 證明：