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

1、離散數(shù)學(xué)圖論部分期末復(fù)習(xí)輔導(dǎo)一、單項選擇題1設(shè)圖G<V, E>，vÎV，則下列結(jié)論成立的是 ( ) Adeg(v)=2½E½ Bdeg(v)=½E½C D解 根據(jù)握手定理（圖中所有結(jié)點的度數(shù)之和等于邊數(shù)的兩倍）知，答案C成立。答 C2設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( )A6 B5 C4 D3解 由鄰接矩陣的定義知，無向圖的鄰接矩陣是對稱的即當結(jié)點vi與vj相鄰時，結(jié)點vj與vi也相鄰，所以連接結(jié)點vi與vj的一條邊在鄰接矩陣的第i行第j列處和第j行第i列處各有一個1，題中給出的鄰接矩陣中共有10個1，故有10¸2=5

2、條邊。答 B3已知無向圖G的鄰接矩陣為，則G有（ ）A5點，8邊 B6點，7邊 C6點，8邊 D5點，7邊解 由鄰接矩陣的定義知，矩陣是5階方陣，所以圖G有5個結(jié)點，矩陣元素有14個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的一個邊割集若

3、邊割集為單元集e，則稱邊e為割邊（或橋）解 割邊首先是一條邊，因為答案A中的是邊集，不可能是割邊，因此答案A是錯誤的刪除答案B或C中的邊后，得到的圖是還是連通圖，因此答案B、C也是錯誤的在圖一中，刪去(d, e)邊，圖就不連通了，所以答案D正確答 D注：如果該題只給出圖的結(jié)點和邊，沒有圖示，大家也應(yīng)該會做如：若圖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、割點Bb, c是點割集Cb, d是點割集Dc是點割集定義 設(shè)無向圖G=<V,E>為連通圖，若有點集V1ÌV，使圖G刪除了V1的所有結(jié)點后，所得的子圖是不連通圖，而刪除了V1的任何真子集后，所得的子圖仍是連通圖，則稱V1是G的一個點割集若點割集為單元集v，則稱結(jié)點v為割點解 在圖二中，刪去結(jié)點a或刪去結(jié)點c或刪去結(jié)點b和d圖還是連通的，所以答案A、C、D是錯誤的在圖二中刪除結(jié)點b和c，得到的子圖是不連通圖，而只刪除結(jié)點b或結(jié)點c，得到的子圖仍然是連通的，由定義可以知道，b, c是點割集所以答案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是錯誤的在圖三中，刪去(a, d)邊和(b, d)邊，圖就不連通了，而只是刪除(a, d)邊或(b, d)邊，圖還是連通的，所以答案C正確7設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是( )圖四A（a）是強連通的 B（b）是強連通的C（c）是強連通的 D（d）是強連通的復(fù)習(xí)：定義 在簡單有向圖中，若在任何結(jié)點偶對中，至少從一個結(jié)點到另一個結(jié)點可達的

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

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

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

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

10、陣為，則G的邊數(shù)為( )A1 B6 C7 D14答 C17如圖二（下圖）所示，以下說法正確的是 ( )Ae是割點 Ba, e是點割集Cb, e是點割集 Dd是點割集圖二答 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個結(jié)點n1條邊的無向圖都是樹C無向完全圖都是平面圖D樹的每條邊都是割邊答 D二、填空題1已知圖G中有1個1度結(jié)點，2個2

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

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

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

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

15、是一個連通平面圖，且有6個結(jié)點11條邊，則G有7個面解 正確由歐拉定理，連通平面圖G的結(jié)點數(shù)為v，邊數(shù)為e，面數(shù)為r，則v-e+r=2于是有r=2-v+e=2-6+11=7問：“完全圖K6是平面圖”是否正確？答 不正確因為完全圖K6有6個結(jié)點15條邊，且15³3´6-6=12，即e £ 3v-6對K6不成立，所以K6不是平面圖四、計算題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、 求出每個結(jié)點的度數(shù)； (4) 畫出其補圖的圖形解 （1）G的圖形為：（2）圖G的鄰接矩陣為：（3）圖G的每個結(jié)點的度數(shù)為：，（4）由關(guān)于補圖的定義3.1.9可知，先在圖G補充邊畫出完全圖（見下面左圖），然后去掉原圖的邊，可得圖G補圖（見下面右圖）：注意：補圖中，如果沒有標出結(jié)點v3，則是錯的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個結(jié)點，其生成樹有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)該會吧3已知帶權(quán)圖G如右圖所示(1) 求圖G的最小生成樹；(2)計算該生成樹的權(quán)值解 （1）圖G有6個結(jié)點，其生成樹有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)二叉樹，計算該最優(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)二叉樹往往都能畫對了，但計算總權(quán)值時可能會把有些權(quán)的層數(shù)計算錯了，導(dǎo)致總權(quán)值計算錯誤，大家一定要細心。注意：這4個計算題的解題方法大家一定要掌