電大離散數(shù)學(xué)圖論部分期末復(fù)習(xí)輔導(dǎo)

1、離散數(shù)學(xué)圖論部分期末復(fù)習(xí)輔導(dǎo)一、單項(xiàng)選擇題1設(shè)圖G<V, E>，vÎV，則下列結(jié)論成立的是 ( ) Adeg(v)=2½E½ Bdeg(v)=½E½C D解 根據(jù)握手定理（圖中所有結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍）知，答案C成立。答 C2設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( )A6 B5 C4 D3解 由鄰接矩陣的定義知，無向圖的鄰接矩陣是對稱的即當(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，故有10¸2=5

2、條邊。答 B3已知無向圖G的鄰接矩陣為，則G有（ ）A5點(diǎn)，8邊 B6點(diǎn)，7邊 C6點(diǎn)，8邊 D5點(diǎn)，7邊解 由鄰接矩陣的定義知，矩陣是5階方陣，所以圖G有5個(gè)結(jié)點(diǎn)，矩陣元素有14個(gè)1，14÷2=7，圖G有7條邊。答 Dooooabcd圖一oe4如圖一所示，以下說法正確的是 ( ) A(a, e)是割邊B(a, e)是邊割集C(a, e) ,(b, c)是邊割集D(d, e)是邊割集定義 設(shè)無向圖G=<V,E>為連通圖，若有邊集E1ÌE，使圖G刪除了E1的所有邊后，所得的子圖是不連通圖，而刪除了E1的任何真子集后，所得的子圖仍是連通圖，則稱E1是G的一個(gè)邊割集若

3、邊割集為單元集e，則稱邊e為割邊（或橋）解 割邊首先是一條邊，因?yàn)榇鸢窤中的是邊集，不可能是割邊，因此答案A是錯(cuò)誤的刪除答案B或C中的邊后，得到的圖是還是連通圖，因此答案B、C也是錯(cuò)誤的在圖一中，刪去(d, e)邊，圖就不連通了，所以答案D正確答 D注：如果該題只給出圖的結(jié)點(diǎn)和邊，沒有圖示，大家也應(yīng)該會(huì)做如：若圖G=<V, E>，其中V= a, b, c, d, e ，E= (a, b), (a, c) , (a, e) , (b, c) , (b, e) , (c, e) , (e, d)，則該圖中的割邊是什么？5圖G如圖二所示，以下說法正確的是 ( )oooabcd圖二oAa是

4、割點(diǎn)Bb, c是點(diǎn)割集Cb, d是點(diǎn)割集Dc是點(diǎn)割集定義 設(shè)無向圖G=<V,E>為連通圖，若有點(diǎn)集V1ÌV，使圖G刪除了V1的所有結(jié)點(diǎn)后，所得的子圖是不連通圖，而刪除了V1的任何真子集后，所得的子圖仍是連通圖，則稱V1是G的一個(gè)點(diǎn)割集若點(diǎn)割集為單元集v，則稱結(jié)點(diǎn)v為割點(diǎn)解 在圖二中，刪去結(jié)點(diǎn)a或刪去結(jié)點(diǎn)c或刪去結(jié)點(diǎn)b和d圖還是連通的，所以答案A、C、D是錯(cuò)誤的在圖二中刪除結(jié)點(diǎn)b和c，得到的子圖是不連通圖，而只刪除結(jié)點(diǎn)b或結(jié)點(diǎn)c，得到的子圖仍然是連通的，由定義可以知道，b, c是點(diǎn)割集所以答案B是正確的答 Boooabcd圖三o6圖G如圖三所示，以下說法正確的是 ( ) A

5、(a, d)是割邊B(a, d)是邊割集C(a, d) ,(b, d)是邊割集D(b, d)是邊割集解 割邊首先是一條邊，(a, d)是邊集，不可能是割邊在圖三中，刪除答案B或D中的邊后，得到的圖是還是連通圖因此答案A、B、D是錯(cuò)誤的在圖三中，刪去(a, d)邊和(b, d)邊，圖就不連通了，而只是刪除(a, d)邊或(b, d)邊，圖還是連通的，所以答案C正確7設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是( )圖四A（a）是強(qiáng)連通的 B（b）是強(qiáng)連通的C（c）是強(qiáng)連通的 D（d）是強(qiáng)連通的復(fù)習(xí)：定義 在簡單有向圖中，若在任何結(jié)點(diǎn)偶對中，至少從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可達(dá)的

6、，則稱圖G是單向（側(cè)）連通的；若在任何結(jié)點(diǎn)偶對中，兩結(jié)點(diǎn)對互相可達(dá)，則稱圖G是強(qiáng)連通的；若圖G的底圖，即在圖G中略去邊的方向，得到的無向圖是連通的，則稱圖G是弱連通的顯然，強(qiáng)連通的一定是單向連通和弱連通的，單向連通的一定是弱連通，但其逆均不真定理 一個(gè)有向圖是強(qiáng)連通的，當(dāng)且僅當(dāng)G中有一個(gè)回路，其至少包含每個(gè)結(jié)點(diǎn)一次單側(cè)連通圖判別法：若有向圖G中存在一條經(jīng)過每個(gè)結(jié)點(diǎn)至少一次的路，則G是單側(cè)連通的。答 A（有一條經(jīng)過每個(gè)結(jié)點(diǎn)的回路）問：上面的圖中，哪個(gè)僅為弱連通的？答：圖(d)是僅為弱連通的請大家要復(fù)習(xí)“弱連通”的概念8設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n³2)，m條邊，當(dāng)（ ）時(shí)，K中存在歐拉回路

7、Am為奇數(shù) Bn為偶數(shù)Cn為奇數(shù) Dm為偶數(shù)解 完全圖K每個(gè)結(jié)點(diǎn)都是n-1度的，由定理的推論知K中存在歐拉回路的條件是n-1是偶數(shù)，從而n為奇數(shù)。答 C提示：前面提到n階無向完全圖Kn的每個(gè)結(jié)點(diǎn)的度數(shù)是n-1，現(xiàn)在要問：無向完全圖Kn的邊數(shù)是多少？答：n(n1)/29若G是一個(gè)漢密爾頓圖，則G一定是( )A平面圖 B對偶圖C歐拉圖 D連通圖定義 給定圖G，若存在一條路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次，則該路稱為漢密爾頓路；若存在一條回路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次，則該回路稱為漢密爾頓回路；具有漢密爾頓回路的圖稱為漢密爾頓圖由定義可知，漢密爾頓圖是連通圖 答 D10若G是一個(gè)歐拉圖，則G一定是

8、( )A平面圖 B漢密爾頓圖C連通圖 D對偶圖定義4.1.1給定無孤立結(jié)點(diǎn)圖G，若存在一條路經(jīng)過圖G的每條邊一次且僅一次，則該路稱為歐拉路（即，歐拉路中沒有重復(fù)的邊，并且包含了圖中的每條邊）若存在一條回路經(jīng)過圖G的每條邊一次且僅一次，則該回路稱為歐拉回路具有歐拉回路的圖就稱為歐拉圖由定義可知，歐拉圖是連通圖 答 C11設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )Aev2 Bve2Cev2 Dev2答 A（定理：歐拉公式v-e+r = 2）問：如果連通平面圖G有4個(gè)結(jié)點(diǎn)，7條邊，那么圖G有幾個(gè)面？12無向樹T有8個(gè)結(jié)點(diǎn)，則T的邊數(shù)為( )A6 B7 C8 D9答 B13無向簡單圖

9、G是棵樹，當(dāng)且僅當(dāng)( )AG連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1BG連通且結(jié)點(diǎn)數(shù)比邊數(shù)少1CG的邊數(shù)比結(jié)點(diǎn)數(shù)少1DG中沒有回路答 A（定理（樹的等價(jià)定義）14已知一棵無向樹T中有8個(gè)頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為( )A8 B5 C4 D3解 這棵無向樹T有7條邊，所有結(jié)點(diǎn)的度數(shù)之和為14，而4度、3度、2度的分支點(diǎn)各一個(gè)共3個(gè)結(jié)點(diǎn)占用了9度，所以剩下的5個(gè)結(jié)點(diǎn)占用5度，即這5個(gè)結(jié)點(diǎn)每個(gè)都是1度結(jié)點(diǎn)，故有5片樹葉答 B15設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹A BC D答 A（n個(gè)結(jié)點(diǎn)的連通圖的生成樹有條邊，必須刪去條邊）16設(shè)無向圖G的鄰接矩

10、陣為，則G的邊數(shù)為( )A1 B6 C7 D14答 C17如圖二（下圖）所示，以下說法正確的是 ( )Ae是割點(diǎn) Ba, e是點(diǎn)割集Cb, e是點(diǎn)割集 Dd是點(diǎn)割集圖二答 A18設(shè)有向圖（a）、（b）、（c）與（d）如圖六（下圖）所示，則下列結(jié)論成立的是( )圖六A（a）只是弱連通的 B（b）只是弱連通的C（c）只是弱連通的 D（d）只是弱連通的答 D19無向完全圖K4是（ ）A歐拉圖 B漢密爾頓圖 C非平面圖 D樹答 B20以下結(jié)論正確的是( )A無向完全圖都是歐拉圖B有n個(gè)結(jié)點(diǎn)n1條邊的無向圖都是樹C無向完全圖都是平面圖D樹的每條邊都是割邊答 D二、填空題1已知圖G中有1個(gè)1度結(jié)點(diǎn)，2個(gè)2

11、度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，4個(gè)4度結(jié)點(diǎn)，則G的邊數(shù)是 解 設(shè)G有x條邊，則由握手定理，答 152設(shè)給定圖G(如右由圖所示)，則圖G的點(diǎn)割集是 解 從圖G中刪除結(jié)點(diǎn)f，得到的子圖是不連通圖，即結(jié)點(diǎn)集f是點(diǎn)割集；從圖G中刪除結(jié)點(diǎn)c和e，得到的子圖是不連通圖，而只刪除c或e，得到的子圖仍然是連通的，所以結(jié)點(diǎn)集c, e也是點(diǎn)割集而其他結(jié)點(diǎn)集都不滿足點(diǎn)割集的定義的集合，所以應(yīng)該填寫：f、c, e答 f、c,e提示：若f是圖G的割點(diǎn)，則f是圖G的點(diǎn)割集，刪除f點(diǎn)后圖G是連通嗎？3設(shè)G是一個(gè)圖，結(jié)點(diǎn)集合為V，邊集合為E，則G的結(jié)點(diǎn) 等于邊數(shù)的兩倍答 的度數(shù)之和4無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且 答 G的結(jié)

12、點(diǎn)度數(shù)都是偶數(shù)（定理4.1.1的推論）5設(shè)G=<V，E>是具有n個(gè)結(jié)點(diǎn)的簡單圖，若在G中每一對結(jié)點(diǎn)度數(shù)之和大于等于 ，則在G中存在一條漢密爾頓路答 n-1（定理）6若圖G=<V, E>中具有一條漢密爾頓回路，則對于結(jié)點(diǎn)集V的每個(gè)非空子集S，在G中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為W，則S中結(jié)點(diǎn)數(shù)|S|與W滿足的關(guān)系式為 答 W £ |S|（定理4.2.1）7設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n³2)，m條邊，當(dāng) 時(shí)，K中存在歐拉回路答 n為奇數(shù)（同一、8題）8結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足 關(guān)系的無向連通圖就是樹答 e=v-1（定理（樹的等價(jià)定義）9設(shè)圖G是有6個(gè)結(jié)點(diǎn)的

13、連通圖，結(jié)點(diǎn)的總度數(shù)為18，則可從G中刪去 條邊后使之變成樹解 由握手定理（定理3.1.1）知道圖G有18¸2=9 條邊，又由定理5.1.1中給出的圖T為樹的等價(jià)定義之一是“圖T連通且e=v-1”，可以知道圖G的生成樹有5條邊，從而要?jiǎng)h去4條邊答 410設(shè)正則5叉樹的樹葉數(shù)為17，則分支數(shù)為i = 答 4（定理：(m-1)i=t-1）三、判斷說明題（判斷下列各題，并說明理由）1如果圖G是無向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路解 錯(cuò)誤只有當(dāng)G是連通圖且其結(jié)點(diǎn)度數(shù)均為偶數(shù)時(shí)，圖G才存在一條歐拉回路2如下圖所示的圖G存在一條歐拉回路解 錯(cuò)誤因?yàn)閳DG有兩個(gè)奇數(shù)度（3度）結(jié)點(diǎn)，所

14、以不存在歐拉回路注：這是一個(gè)漢密爾頓圖，但不是歐拉圖?？梢姖h密爾頓圖不一定是歐拉圖其實(shí)，歐拉圖也不一定是漢密爾頓圖如下圖所示，圖（1）是歐拉圖又是漢密爾頓圖，圖（2）是歐拉圖但不是漢密爾頓圖，圖（3）不是歐拉圖但它是漢密爾頓圖，圖（4）不是歐拉圖也不是漢密爾頓圖。3如下圖所示的圖G不是歐拉圖而是漢密爾頓圖圖G解 正確圖G有4個(gè)3度結(jié)點(diǎn)a，b，d，f，所以圖G不是歐拉圖圖G有漢密爾頓回路abefgdca，所以圖G是漢密爾頓圖4設(shè)G是一個(gè)有7個(gè)結(jié)點(diǎn)16條邊的連通簡單圖，則G為平面圖解 錯(cuò)誤由定理知，若G有v個(gè)結(jié)點(diǎn)e條邊，且v³3，則e3v-6但本題中，163×7-6不成立5設(shè)G

15、是一個(gè)連通平面圖，且有6個(gè)結(jié)點(diǎn)11條邊，則G有7個(gè)面解 正確由歐拉定理，連通平面圖G的結(jié)點(diǎn)數(shù)為v，邊數(shù)為e，面數(shù)為r，則v-e+r=2于是有r=2-v+e=2-6+11=7問：“完全圖K6是平面圖”是否正確？答 不正確因?yàn)橥耆珗DK6有6個(gè)結(jié)點(diǎn)15條邊，且15³3´6-6=12，即e £ 3v-6對K6不成立，所以K6不是平面圖四、計(jì)算題1設(shè)G=<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)

16、 求出每個(gè)結(jié)點(diǎn)的度數(shù)； (4) 畫出其補(bǔ)圖的圖形解 （1）G的圖形為：（2）圖G的鄰接矩陣為：（3）圖G的每個(gè)結(jié)點(diǎn)的度數(shù)為：，（4）由關(guān)于補(bǔ)圖的定義3.1.9可知，先在圖G補(bǔ)充邊畫出完全圖（見下面左圖），然后去掉原圖的邊，可得圖G補(bǔ)圖（見下面右圖）：注意：補(bǔ)圖中，如果沒有標(biāo)出結(jié)點(diǎn)v3，則是錯(cuò)的2圖G=<V, E>，其中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，試（1）畫出G的圖形；（2）寫出G的鄰接矩陣；（3

17、）求出G權(quán)最小的生成樹及其權(quán)值解 （1）G的圖形如左下圖：（2）G的鄰接矩陣為：（3）圖G有5個(gè)結(jié)點(diǎn)，其生成樹有4條邊，用Kruskal算法求其權(quán)最小的生成樹T：第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)成圈”的要求。如果題目給出如解(1) 中所示賦權(quán)圖，要求用K

18、ruskal算法（避圈法）求出該賦權(quán)圖的最小生成樹，大家應(yīng)該會(huì)吧3已知帶權(quán)圖G如右圖所示(1) 求圖G的最小生成樹；(2)計(jì)算該生成樹的權(quán)值解 （1）圖G有6個(gè)結(jié)點(diǎn)，其生成樹有5條邊，用Kruskal算法求其權(quán)最小的生成樹T：第1步，取具最小權(quán)1的邊；第2步，取剩余邊中具最小權(quán)2的邊；第3步，取剩余邊中不與前2條邊構(gòu)成回路的具最小權(quán)3的邊；第4步，取剩余邊中不與前3條邊構(gòu)成回路的具最小權(quán)5的邊；第5步，取剩余邊中不與前4條邊構(gòu)成回路的具最小權(quán)7的邊所求最小生成樹T如右圖（2）該最小生成樹的權(quán)為4設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31，試畫出相應(yīng)的最優(yōu)二叉樹，計(jì)算該最優(yōu)二叉樹的權(quán)解 （Huffman算法）：首先組合2+3，求帶權(quán)5, 5, 7, 17, 31的最優(yōu)二叉樹；再組合5+5，求帶權(quán)7, 10, 17, 31的最優(yōu)二叉樹；然后組合7+10，求帶權(quán)17, 17, 31的最優(yōu)二叉樹；繼續(xù)組合17+17，求帶權(quán)31, 34的最優(yōu)二叉樹；最后組合31+34，得65，這是樹根所帶的權(quán)。可從樹根開始往下畫，即得所求最優(yōu)二叉樹T如下圖：所求最優(yōu)二叉樹T的權(quán)為：講評：作業(yè)中最優(yōu)二叉樹往往都能畫對了，但計(jì)算總權(quán)值時(shí)可能會(huì)把有些權(quán)的層數(shù)計(jì)算錯(cuò)了，導(dǎo)致總權(quán)值計(jì)算錯(cuò)誤，大家一定要細(xì)心。注意：這4個(gè)計(jì)算題的解題方法大家一定要掌