離散數(shù)學(xué)2014春學(xué)期圖論綜合練習(xí)輔導(dǎo).doc

離散數(shù)學(xué)2014春學(xué)期圖論部分綜合練習(xí)輔導(dǎo)大家好！本學(xué)期的第二次教學(xué)輔導(dǎo)活動(dòng)現(xiàn)在開始，本次活動(dòng)主要是針對第二單元圖論的重點(diǎn)學(xué)習(xí)內(nèi)容進(jìn)行輔導(dǎo)，方式同樣是通過講解一些典型的綜合練習(xí)作業(yè)題目，幫助大家進(jìn)一步理解和掌握圖論的基本概念和方法圖論作為離散數(shù)學(xué)的一部分，主要介紹圖論的基本概念、理論與方法教學(xué)內(nèi)容主要有圖的基本概念與結(jié)論、圖的連通性與連通度、圖的矩陣表示、最短路問題、歐拉圖與漢密爾頓圖、平面圖、對偶圖與著色、樹與生成樹、根樹及其應(yīng)用等本次綜合練習(xí)主要是復(fù)習(xí)這一單元的主要概念與計(jì)算方法，與集合論一樣，也安排了五種類型，有單項(xiàng)選擇題、填空題，判斷說明題、計(jì)算題、證明題這樣的安排也是為了讓同學(xué)們熟悉期末考試的題型，能夠較好地完成這一部分主要內(nèi)容的學(xué)習(xí)一、單項(xiàng)選擇題單項(xiàng)選擇題主要是第4次形考作業(yè)的部分題目第4次作業(yè)同樣也是由10個(gè)單項(xiàng)選擇題組成，每小題10分，滿分100分在每次作業(yè)在關(guān)閉之前，允許大家反復(fù)多次練習(xí)，系統(tǒng)將保留您的最好成績，希望大家要多練幾次，爭取好成績需要提醒大家的是每次練習(xí)的作業(yè)題目可能不一樣，請大家一定要認(rèn)真閱讀題目 1設(shè)圖G，vV，則下列結(jié)論成立的是 ( ) Adeg(v)=2E B deg(v)=E C D該題主要是檢查大家對握手定理掌握的情況復(fù)習(xí)握手定理：定理3.1.1 設(shè)G是一個(gè)圖，其結(jié)點(diǎn)集合為V，邊集合為E，則也就是說，無向圖G的結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍正確答案：C 2設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( ) A6 B5 C4 D3主要是檢查對鄰接矩陣的概念理解是否到位大家要復(fù)習(xí)鄰接矩陣的定義，要記住當(dāng)給定的簡單圖是無向圖時(shí)，鄰接矩陣為對稱的即當(dāng)結(jié)點(diǎn)vi與vj相鄰時(shí)，結(jié)點(diǎn)vj與vi也相鄰，所以連接結(jié)點(diǎn)vi與vj的一條邊在鄰接矩陣的第i行第j列處和第j行第i列處各有一個(gè)1，題中給出的鄰接矩陣中共有10個(gè)1，故有102=5條邊ooooabcdoe正確答案：B 3如右圖所示，以下說法正確的是 ( ) A(a, e)是割邊 B(a, e)是邊割集C(a, e) ,(b, c)是邊割集 D(d, e)是邊割集先復(fù)習(xí)割邊、邊割集的定義： 定義3.2.9 設(shè)無向圖G=為連通圖，若有邊集E1E，使圖G刪除了E1的所有邊后，所得的子圖是不連通圖，而刪除了E1的任何真子集后，所得的子圖是連通圖，則稱E1是G的一個(gè)邊割集若某個(gè)邊構(gòu)成一個(gè)邊割集，則稱該邊為割邊（或橋）因?yàn)閯h除答案A或B或C中的邊后，得到的圖是還是連通圖，因此答案A、B、C是錯(cuò)誤的正確答案：D 注：如果第3題只給出圖的結(jié)點(diǎn)和邊，沒有圖示，大家也應(yīng)該會(huì)做如： 若圖G=，其中V= a, b, c, d, e ，E= (a, b), (a, c) , (a, e) , (b, c) , (b, e) , (c, e) , (e, d)，則該圖中的割邊是什么？ 4設(shè)有向圖（a）、（b）、（c）與（d）如下圖所示，則下列結(jié)論成立的是( ) A（a）是強(qiáng)連通的 B（b）是強(qiáng)連通的C（c）是強(qiáng)連通的 D（d）是強(qiáng)連通的 我們先復(fù)習(xí)強(qiáng)連通的概念：定義3.2.5 在簡單有向圖中，若在任何結(jié)點(diǎn)偶對中，至少從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可達(dá)的，則稱圖G是單向（側(cè)）連通的； 若在任何結(jié)點(diǎn)偶對中，兩結(jié)點(diǎn)對互相可達(dá)，則稱圖G是強(qiáng)連通的正確答案：A問：上面的圖中，哪個(gè)僅為弱連通的？ 請大家要復(fù)習(xí)“弱連通”的概念 5設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n2)，m條邊，當(dāng)（ ）時(shí)，K中存在歐拉回路Am為奇數(shù) Bn為偶數(shù) Cn為奇數(shù) Dm為偶數(shù) 我們先復(fù)習(xí)完全圖的概念： 定義3.1.6 簡單圖G=中，若每一對結(jié)點(diǎn)間都有邊相連，則稱該圖為完全圖有n個(gè)結(jié)點(diǎn)的無向完全圖記為Kn由定義可知，無向完全圖Kn中的任一結(jié)點(diǎn)v到其它結(jié)點(diǎn)都有一條邊，共有n-1條邊，即每個(gè)結(jié)點(diǎn)的度數(shù)是n-1，當(dāng)n為奇數(shù)時(shí)，n-1為偶數(shù)由定理4.1.1的推論 一個(gè)無向圖具有一條歐拉回路，當(dāng)且僅當(dāng)該圖是連通的，并且它的結(jié)點(diǎn)度數(shù)都是偶數(shù) 所以，正確答案應(yīng)該是C 提示：前面提到n階無向完全圖Kn的每個(gè)結(jié)點(diǎn)的度數(shù)是n-1，現(xiàn)在要問：無向完全圖Kn的邊數(shù)是多少？ 如2013年7月份試卷中：3n階無向完全圖Kn的邊數(shù)及每個(gè)結(jié)點(diǎn)的度數(shù)分別是（ ） An(n-1)/2，n-1 Bn-1，n Cn(n-1), n-1 Dn(n-1), n6設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( ) Aev2 Bve2 Cev2 Dev2 本題主要檢查大家是否掌握了歐拉定理 定理4.3.2（歐拉定理） 設(shè)連通平面圖G的結(jié)點(diǎn)數(shù)為v，邊數(shù)為e，面數(shù)為r，則歐拉公式v-e+r =2成立 由歐拉公式v-e+r =2，得到r = e- v+2所以，答案A是正確的問：如果連通平面圖G有4個(gè)結(jié)點(diǎn)，7條邊，那么圖G有幾個(gè)面？7無向簡單圖G是棵樹，當(dāng)且僅當(dāng)( )AG連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1 BG連通且結(jié)點(diǎn)數(shù)比邊數(shù)少1CG的邊數(shù)比結(jié)點(diǎn)數(shù)少1 DG中沒有回路可以運(yùn)用教材中的定理5.1.1，可以作出正確選擇因?yàn)槎ɡ?.1.1中給出的圖T為樹的等價(jià)定義之一是圖T連通且e=v-1，其中e是邊數(shù)，v是結(jié)點(diǎn)數(shù)也就是說：無向簡單圖G是棵樹，當(dāng)且僅當(dāng)G連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1正確答案：A注：由上面的樹的等價(jià)定義可知，結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足e=v-1關(guān)系的無向連通圖就是樹問當(dāng)樹T有6個(gè)結(jié)點(diǎn)，那么它有多少條邊？8已知一棵無向樹T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為（ ） A8 B5 C4 D3設(shè)無向樹T的樹葉數(shù)為x，因?yàn)闃淙~是度數(shù)為1的結(jié)點(diǎn)那么，由定理3.1.1（握手定理） 設(shè)G是一個(gè)圖，其結(jié)點(diǎn)集合為V，邊集合為E，則，得 4+3+2+x=2（8-1），即x=5正確答案：B下面的內(nèi)容主要是第5次形考作業(yè)的部分題目 二、填空題1已知圖G中有1個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，4個(gè)4度結(jié)點(diǎn)，則G的邊數(shù)是 也是檢查大家對握手定理掌握的情況因?yàn)閳DG中有1個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，4個(gè)4度結(jié)點(diǎn)，即，根據(jù)握手定理，邊數(shù)有 應(yīng)該填寫：15ooooabcdoeof討論： 已知圖G中有15條邊，3個(gè)3度結(jié)點(diǎn)，4個(gè)4度結(jié)點(diǎn)，其它結(jié)點(diǎn)的度數(shù)小于等于2，討論圖G可能的結(jié)點(diǎn)數(shù)2設(shè)給定圖G (如右圖所示)，則圖G的點(diǎn)割集是 本題主要是檢查大家對點(diǎn)割集、割點(diǎn)的概念理解的情況定義3.2.7 設(shè)無向圖G=為連通圖，若有點(diǎn)集V1V，使圖G刪除了V1的所有結(jié)點(diǎn)后，所得的子圖是不連通圖，而刪除了V1的任何真子集后，所得的子圖是連通圖，則稱V1是G的一個(gè)點(diǎn)割集若某個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集，則稱該結(jié)點(diǎn)為割點(diǎn)從圖G中刪除結(jié)點(diǎn)f，得到的子圖是不連通圖，即結(jié)點(diǎn)集f是點(diǎn)割集；同樣，從圖G中刪除結(jié)點(diǎn)c，e，得到的子圖也是不連通圖，那么結(jié)點(diǎn)集c, e也是點(diǎn)割集而刪除其他結(jié)點(diǎn)集都沒有滿足點(diǎn)割集、定義的集合，所以應(yīng)該填寫：f、c, e提示：若f是圖G的割點(diǎn)，則f是圖G的點(diǎn)割集，刪除f點(diǎn)后圖G是連通嗎？3無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且 由定理4.1.1的推論 一個(gè)無向圖具有一條歐拉回路，當(dāng)且僅當(dāng)該圖是連通的，并且它的結(jié)點(diǎn)度數(shù)都是偶數(shù)應(yīng)該填寫：結(jié)點(diǎn)度數(shù)都是偶數(shù) 444若圖G=中具有一條漢密爾頓回路，則對于結(jié)點(diǎn)集V的每個(gè)非空子集S，在G中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為W，則S中結(jié)點(diǎn)數(shù)|S|與W滿足的關(guān)系式為 定理4.2.1 若圖G=中具有一條漢密爾頓回路，則對于結(jié)點(diǎn)集V的每個(gè)非空子集S均有W(G-S) |S|成立，其中W(G-S)是（G-S）中連通分支數(shù)應(yīng)該填寫：W(G-S) |S|5設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18，則可從G中刪去 條邊后使之變成樹（邊后，可以確定圖G的一棵生成樹）由握手定理（定理3.1.1）知道圖G有182=9 條邊，又由定理5.1.1中給出的圖T為樹的等價(jià)定義之一是“圖T連通且e=v-1”，可以知道：應(yīng)該填寫：4 注意：選擇題和填空題講完后還要強(qiáng)調(diào)考核說明中第3章的第1個(gè)考核要求：1理解圖的基本概念：結(jié)點(diǎn)、邊、有向圖，無向圖、簡單圖、完全圖、結(jié)點(diǎn)的度數(shù)、圖的同構(gòu)、子圖等，理解握手定理 三、判斷說明題1如果圖G是無向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路 分析：先復(fù)習(xí)歐拉圖的判別定理：定理4.1.1的推論：一個(gè)無向圖具有一條歐拉回路，當(dāng)且僅當(dāng)該圖是連通的，并且它的結(jié)點(diǎn)度數(shù)都是偶數(shù) 解：不正確 因?yàn)轭}中的圖G沒有“連通”的條件ooooabcdoeofog圖G問：“如果圖G是無向連通圖，則圖G存在一條歐拉回路”是否正確？2如右圖所示的圖G不是歐拉圖而是漢密爾頓圖解：正確圖G有4個(gè)3度結(jié)點(diǎn)a，b，d，f，所以圖G不是歐拉圖圖G有漢密爾頓回路abefgdca，所以圖G是漢密爾頓圖注意：漢密爾頓圖不一定是歐拉圖，為什么？3設(shè)G是一個(gè)有7個(gè)結(jié)點(diǎn)16條邊的連通圖，則G為平面圖 分析：定理4.3.3 設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡單平面圖，若v3，則e3v-6利用該定理判斷本題解：不正確 因?yàn)轭}中的連通簡單平面圖有v=7個(gè)結(jié)點(diǎn)，e=16條邊，那么1637-6=15，由定理4.3.3知道，圖G不是平面圖問：“完全圖K6是平面圖”是否正確？答：不正確因?yàn)橥耆珗DK6有6個(gè)結(jié)點(diǎn)15條邊，且1536-6=12，即e 3v-6對K6不成立，所以K6不是平面圖 四、計(jì)算題1設(shè)G=，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試(1) 給出G的圖形表示； (2) 寫出其鄰接矩陣；(3) 求出每個(gè)結(jié)點(diǎn)的度數(shù)； (4) 畫出其補(bǔ)圖的圖形oooov1ov5v2v3v4 解：(1) 因?yàn)閂= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，所以G的圖形表示為：(2) 分析：本題給定的簡單圖是無向圖，因此鄰接矩陣為對稱的即當(dāng)結(jié)點(diǎn)vi與vj相鄰時(shí)，結(jié)點(diǎn)vj與vi也相鄰，所以連接結(jié)點(diǎn)vi與vj的一條邊在鄰接矩陣的第i行第j列處和第j行第i列處各寫一個(gè)1；當(dāng)結(jié)點(diǎn)vi與vj沒有邊連接時(shí)，鄰接矩陣的第i行第j列處和第j行第i列處各寫一個(gè)0鄰接矩陣： (3) 由G的圖形可知，v1，v2，v3，v4，v5結(jié)點(diǎn)的度數(shù)依次為1，2，4，3，2 oooov1ov5v2v3v4oooov1ov5v2v3v4(4) 由關(guān)于補(bǔ)圖的定義3.1.9可知，先畫出完全圖（見圖1），然后去掉原圖，可得補(bǔ)圖（見圖2）如下： 圖1 圖2注意：補(bǔ)圖中，如果沒有標(biāo)出結(jié)點(diǎn)v3，則是錯(cuò)的 2圖G=，其中V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，對應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5，試cabedooooo12216435（1）畫出G的圖形； （2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹及其權(quán)值解 （1）因?yàn)閂= 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個(gè)結(jié)點(diǎn)，其生成樹有4條邊，用Kruskal算法（避圈法）求其權(quán)最小的生成樹T：cabedooooo1213第1步，取具最小權(quán)1的邊(a, c)；第2步，取剩余邊中具最小權(quán)1的邊(c, e)；第3步，取剩余邊中不與前2條邊構(gòu)成回路的具最小權(quán)2的邊(a, b)；第4步，取剩余邊中不與前3條邊構(gòu)成回路的具最小權(quán)3的邊(b, d)所求最小生成樹T如右下圖，其權(quán)為 注意：在用避圈法求最小的生成樹的關(guān)鍵是：“取圖中權(quán)數(shù)最小的邊，且與前面取到的邊不構(gòu)成圈”，很多學(xué)生只注意到取權(quán)數(shù)最小的邊了，而忽略了“不構(gòu)成圈”的要求如果題目給出如計(jì)算題2的解(1) 中所示賦權(quán)圖，要求出該賦權(quán)圖的最小生成樹，大家應(yīng)該會(huì)吧如2013年7月份試卷中第17題：17試求出如圖一所示賦權(quán)圖中的最小生成樹（要求寫出求解步驟），并求此最小生成樹的權(quán) 圖一3設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31，試畫出相應(yīng)的最優(yōu)二叉樹，計(jì)算該最優(yōu)二叉樹的權(quán)ooooo32755173410oooo1731oo65解：方法（Huffman）：從2, 3, 5, 7, 17, 31中選2, 3為最低層結(jié)點(diǎn)，并從權(quán)數(shù)中刪去，再添上他們的和數(shù)，即5, 5, 7, 17, 31；再從5, 5, 7, 17, 31中選5, 5為倒數(shù)第2層結(jié)點(diǎn)，并從上述數(shù)列中刪去，再添上他們的和數(shù)，即7, 10, 17, 31； 然后，從7, 10, 17, 31中選7, 10為倒數(shù)第3層結(jié)點(diǎn)，并從上述數(shù)列中刪去，再添上他們的和數(shù)，即17, 17, 31； 最優(yōu)二叉樹如右圖所示最優(yōu)二叉樹權(quán)值為：25+35+54+73+172+311 =10+15+20+21+34+31=131 補(bǔ)充： 教材第101頁 例3 給定如圖3.3.3所示有向圖，其鄰接矩陣以及鄰接矩陣的乘積如下：oooov1ov5v2v3v4圖3.3.3 例3圖， ，從上面的矩陣中可以得到一些結(jié)論，如： （1）從A2中第1行第3列的為1可知，結(jié)點(diǎn)v1與v3之間有一條長度為2的路