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

離散數(shù)學(xué)圖論部分期末復(fù)習(xí)輔導(dǎo)一、單項選擇題１．設(shè)圖G=＜V,Ｅ>,vV,則下列結(jié)論成立的是().A．ｄｅg(v)=2ＥB．ｄeg(ｖ)=EC．Ｄ.解根據(jù)握手定理(圖中所有結(jié)點的度數(shù)之和等于邊數(shù)的兩倍）知，答案C成立。答Ｃ2．設(shè)無向圖Ｇ的鄰接矩陣為，則G的邊數(shù)為(）．A．６Ｂ．5C.4D.3解由鄰接矩陣的定義知，無向圖的鄰接矩陣是對稱的.即當(dāng)結(jié)點vｉ與vj相鄰時,結(jié)點vj與ｖi也相鄰，所以連接結(jié)點ｖi與vj的一條邊在鄰接矩陣的第ｉ行第j列處和第j行第i列處各有一個１，題中給出的鄰接矩陣中共有1０個1，故有102=5條邊。答Ｂ3．已知無向圖G的鄰接矩陣為，則G有().A．5點,8邊B．６點，7邊C．６點，8邊Ｄ.５點，7邊解由鄰接矩陣的定義知，矩陣是5階方陣，所以圖G有５個結(jié)點，矩陣元素有14個1,１４÷2=7,圖G有7條邊。答Dabcd圖一eA．{(a,e)}是割邊B.{(a，ｅ）}是邊割集C．{(a,e),(b,ｃ）}是邊割集Ｄ．{(d,e)}是邊割集定義3.2.9設(shè)無向圖G=<V,E>為連通圖,若有邊集E1ìE,使圖G刪除了E１的所有邊后，所得的子圖是不連通圖,而刪除了E1的任何真子集后,所得的子圖仍是連通圖，則稱E１是Ｇ的一個邊割集．若邊割集為單元集｛e},則稱邊e為割邊(或橋）．解割邊一方面是一條邊,由于答案A中的是邊集，不也許是割邊，因此答案Ａ是錯誤的.刪除答案B或Ｃ中的邊后，得到的圖是還是連通圖,因此答案Ｂ、C也是錯誤的.在圖一中,刪去(ｄ，ｅ)邊,圖就不連通了，所以答案Ｄ對的．答D注：假如該題只給出圖的結(jié)點和邊,沒有圖示,大家也應(yīng)當(dāng)會做．如：若圖G＝<Ｖ,E>,其中V=｛a,b,c，d,e}，E＝{(a,ｂ),(a,c),(a,ｅ),(b,c),(b,ｅ),(c,ｅ),（e，ｄ)}，則該圖中的割邊是什么?5.圖Ｇ如圖二所示,以下說法對的的是（)．a(chǎn)abcd圖二Ｂ．｛b，ｃ｝是點割集Ｃ．{b,d｝是點割集D.{c}是點割集定義3.２.7設(shè)無向圖G=<V,E>為連通圖，若有點集V1ìV,使圖Ｇ刪除了V1的所有結(jié)點后,所得的子圖是不連通圖，而刪除了V1的任何真子集后，所得的子圖仍是連通圖,則稱V1是G的一個點割集.若點割集為單元集{v},則稱結(jié)點v為割點．解在圖二中，刪去結(jié)點a或刪去結(jié)點c或刪去結(jié)點b和d圖還是連通的,所以答案A、Ｃ、D是錯誤的.在圖二中刪除結(jié)點b和ｃ,得到的子圖是不連通圖,而只刪除結(jié)點ｂ或結(jié)點c,得到的子圖仍然是連通的,由定義可以知道,｛b,c}是點割集.所以答案B是對的的.答B(yǎng)aabcd圖三A.{（a,d)}是割邊B.{（ａ,d)｝是邊割集C.{(a,d),(ｂ,d)}是邊割集Ｄ.{(b,d)}是邊割集解割邊一方面是一條邊，{(a,ｄ）}是邊集，不也許是割邊．在圖三中,刪除答案B或D中的邊后,得到的圖是還是連通圖.因此答案A、B、D是錯誤的．在圖三中，刪去(a，d）邊和（b,d)邊,圖就不連通了，而只是刪除(ａ,d)邊或(b,d)邊，圖還是連通的,所以答案Ｃ對的.7．設(shè)有向圖（a)、（b）、(c）與（d)如圖四所示，則下列結(jié)論成立的是().圖四A.（ａ）是強連通的Ｂ.(b)是強連通的C.（ｃ)是強連通的Ｄ.（d）是強連通的復(fù)習(xí)：定義3.２．5在簡樸有向圖中,若在任何結(jié)點偶對中,至少從一個結(jié)點到另一個結(jié)點可達的，則稱圖G是單向（側(cè)）連通的；若在任何結(jié)點偶對中，兩結(jié)點對互相可達，則稱圖G是強連通的；若圖G的底圖，即在圖G中略去邊的方向，得到的無向圖是連通的，則稱圖G是弱連通的.顯然,強連通的一定是單向連通和弱連通的，單向連通的一定是弱連通，但其逆均不真．定理3.2．1一個有向圖是強連通的,當(dāng)且僅當(dāng)Ｇ中有一個回路，其至少包含每個結(jié)點一次.單側(cè)連通圖判別法:若有向圖G中存在一條通過每個結(jié)點至少一次的路，則G是單側(cè)連通的。答Ａ(有一條通過每個結(jié)點的回路)問：上面的圖中，哪個僅為弱連通的?答：圖(ｄ)是僅為弱連通的請大家要復(fù)習(xí)“弱連通”的概念.８．設(shè)完全圖K有n個結(jié)點(n2)，m條邊,當(dāng)()時，Ｋ中存在歐拉回路.A．ｍ為奇數(shù)B．n為偶數(shù)Ｃ．n為奇數(shù)D.m為偶數(shù)解完全圖Ｋ每個結(jié)點都是n１度的，由定理4.１.1的推論知Ｋ中存在歐拉回路的條件是n1是偶數(shù),從而n為奇數(shù)。答C提醒:前面提到n階無向完全圖Ｋn的每個結(jié)點的度數(shù)是n-1,現(xiàn)在要問:無向完全圖Kn的邊數(shù)是多少？答：n（n–1)/29.若G是一個漢密爾頓圖，則G一定是（).Ａ．平面圖Ｂ.對偶圖Ｃ．歐拉圖D．連通圖定義４．2．1給定圖Ｇ，若存在一條路通過圖G的每個結(jié)點一次且僅一次,則該路稱為漢密爾頓路；若存在一條回路通過圖G的每個結(jié)點一次且僅一次，則該回路稱為漢密爾頓回路；具有漢密爾頓回路的圖稱為漢密爾頓圖.由定義可知,漢密爾頓圖是連通圖.答D10.若Ｇ是一個歐拉圖,則Ｇ一定是().Ａ．平面圖Ｂ．漢密爾頓圖C.連通圖D.對偶圖定義4.1.1給定無孤立結(jié)點圖G，若存在一條路通過圖G的每條邊一次且僅一次，則該路稱為歐拉路.（即，若存在一條回路通過圖G的每條邊一次且僅一次，則該回路稱為歐拉回路．具有歐拉回路的圖就稱為歐拉圖.由定義可知，歐拉圖是連通圖．答C１１．設(shè)G是連通平面圖,有v個結(jié)點，e條邊，r個面，則r=(）．A．ｅ-ｖ＋2B.v+e－２C.e-v-２Ｄ．e+v+2答A(定理4.３．2:歐拉公式v-e+ｒ2）問：假如連通平面圖Ｇ有4個結(jié)點,7條邊，那么圖G有幾個面？12．無向樹Ｔ有８個結(jié)點,則Ｔ的邊數(shù)為()．A.6B．７C.８D.９ 13.無向簡樸圖G是棵樹,當(dāng)且僅當(dāng)(）.Ａ.G連通且邊數(shù)比結(jié)點數(shù)少1Ｂ.G連通且結(jié)點數(shù)比邊數(shù)少1Ｃ．Ｇ的邊數(shù)比結(jié)點數(shù)少１D.G中沒有回路.答A（定理5.1.1（樹的等價定義)）14.已知一棵無向樹T中有8個頂點,4度、3度、2度的分支點各一個，T的樹葉數(shù)為(）．Ａ．8B．５C解這棵無向樹Ｔ有7條邊，所有結(jié)點的度數(shù)之和為1４，而4度、3度、2度的分支點各一個共3個結(jié)點占用了9度，所以剩下的５個結(jié)點占用5度,即這5個結(jié)點每個都是１度結(jié)點，故有5片樹葉．答B(yǎng)15．設(shè)G是有ｎ個結(jié)點，ｍ條邊的連通圖,必須刪去G的()條邊，才干擬定G的一棵生成樹.A.B.C．D．答A（n個結(jié)點的連通圖的生成樹有條邊,必須刪去條邊）１６.設(shè)無向圖G的鄰接矩陣為,則G的邊數(shù)為()．Ａ．1B.6C.7D.1４ ?答C１7.如圖二(下圖)所示，以下說法對的的是().Ａ．e是割點B．{a,e}是點割集C.{b,ｅ}是點割集Ｄ．｛d}是點割集圖二答A18.設(shè)有向圖（a）、（b）、(c）與（d）如圖六（下圖)所示,則下列結(jié)論成立的是()．圖六A.(a）只是弱連通的Ｂ.（b)只是弱連通的Ｃ．(c）只是弱連通的D.（d）只是弱連通的? 答Ｄ19.無向完全圖K4是（).A.歐拉圖B．漢密爾頓圖C．非平面圖Ｄ．樹???答B(yǎng)20．以下結(jié)論對的的是().Ａ.無向完全圖都是歐拉圖B.有n個結(jié)點n－1條邊的無向圖都是樹Ｃ．無向完全圖都是平面圖Ｄ．樹的每條邊都是割邊 答Ｄ二、填空題1．已知圖Ｇ中有１個1度結(jié)點，２個2度結(jié)點，3個3度結(jié)點，4個4度結(jié)點,則G的邊數(shù)是.解設(shè)Ｇ有x條邊,則由握手定理,，答15２.設(shè)給定圖G(如右由圖所示),則圖G的點割集是．解從圖G中刪除結(jié)點f,得到的子圖是不連通圖,即結(jié)點集{f}是點割集;從圖Ｇ中刪除結(jié)點ｃ和e，得到的子圖是不連通圖，而只刪除ｃ或e，得到的子圖仍然是連通的,所以結(jié)點集{c,ｅ}也是點割集.而其他結(jié)點集都不滿足點割集的定義的集合，所以應(yīng)當(dāng)填寫：{ｆ}、｛c，e}答{f｝、｛c,e}提醒:若ｆ是圖G的割點，則{ｆ}是圖Ｇ的點割集，刪除f點后圖Ｇ是連通嗎？3.設(shè)G是一個圖，結(jié)點集合為Ｖ，邊集合為E,則Ｇ的結(jié)點等于邊數(shù)的兩倍．答的度數(shù)之和4.無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且．答G的結(jié)點度數(shù)都是偶數(shù)（定理4.１.１的５．設(shè)G＝<V,E>是具有n個結(jié)點的簡樸圖，若在G中每一對結(jié)點度數(shù)之和大于等于,則在G中存在一條漢密爾頓路.答ｎ1(定理4．2.2)6.若圖G＝<V,E>中具有一條漢密爾頓回路，則對于結(jié)點集V的每個非空子集S，在G中刪除Ｓ中的所有結(jié)點得到的連通分支數(shù)為Ｗ,則S中結(jié)點數(shù)|S|與W滿足的關(guān)系式為．答W|S|(定理4.2.17．設(shè)完全圖K有n個結(jié)點(ｎ2)，m條邊,當(dāng)時,K中存在歐拉回路．答n為奇數(shù)（同一、８題）８．結(jié)點數(shù)v與邊數(shù)e滿足關(guān)系的無向連通圖就是樹．答ev1（定理5．1．1(樹的等價定義)）９．設(shè)圖G是有6個結(jié)點的連通圖,結(jié)點的總度數(shù)為18,則可從G中刪去條邊后使之變成樹.解由握手定理（定理３.1．１)知道圖Ｇ有18２=9條邊,又由定理５.1.１中給出的圖T為樹的等價定義之一是“圖Ｔ連通且ｅ=v-1”，可以知道答410.設(shè)正則5叉樹的樹葉數(shù)為17，則分支數(shù)為i=．答４（定理5.2．1:(m-1)i=t-1）三、判斷說明題（判斷下列各題，并說明理由．）1．假如圖G是無向圖，且其結(jié)點度數(shù)均為偶數(shù),則圖Ｇ存在一條歐拉回路．解錯誤．只有當(dāng)Ｇ是連通圖且其結(jié)點度數(shù)均為偶數(shù)時，圖G才存在一條歐拉回路．2.如下圖所示的圖G存在一條歐拉回路．解錯誤.由于圖Ｇ有兩個奇數(shù)度(3度)結(jié)點，所以不存在歐拉回路.注：這是一個漢密爾頓圖,但不是歐拉圖?？梢姖h密爾頓圖不一定是歐拉圖．其實,歐拉圖也不一定是漢密爾頓圖.如下圖所示,圖（1）是歐拉圖又是漢密爾頓圖，圖（２)是歐拉圖但不是漢密爾頓圖，圖(3)不是歐拉圖但它是漢密爾頓圖,圖（４)不是歐拉圖也不是漢密爾頓圖。3．如下圖所示的圖G不是歐拉圖而是漢密爾頓圖.圖G解對的．圖G有4個3度結(jié)點ａ，b，d，f,所以圖Ｇ不是歐拉圖．圖Ｇ有漢密爾頓回路ａbefgｄca，所以圖G是漢密爾頓圖．4．設(shè)G是一個有7個結(jié)點16條邊的連通簡樸圖，則Ｇ為平面圖．解錯誤．由定理4.3．3知,若Ｇ有v個結(jié)點e條邊,且v3，則e≤3v６．但本題中，16≤3×７６不成立．5．設(shè)G是一個連通平面圖,且有6個結(jié)點11條邊,則G有7個面．解對的.由歐拉定理，連通平面圖G的結(jié)點數(shù)為v，邊數(shù)為ｅ，面數(shù)為r,則ｖｅ+r=2．于是有ｒ=2v＋ｅ=2６+11=７．問：“完全圖Ｋ6是平面圖”是否對的?答不對的.由于完全圖Ｋ６有6個結(jié)點15條邊，且1536－6=1２，即e3ｖ-6對Ｋ6不成立，所以Ｋ６不是平面圖.四、計算題１.設(shè)Ｇ=＜V，E>,Ｖ＝{v１，v2，ｖ3,ｖ4,v5}，E={（ｖ1,v３),(v2，ｖ3),（ｖ2,v4),(v3,v４)，（v3,ｖ5)，(v4,v5)},試(1）給出G的圖形表達;(２)寫出其鄰接矩陣；(3)求出每個結(jié)點的度數(shù);(4)畫出其補圖的圖形.解（1）Ｇ的圖形為:(2)圖G的鄰接矩陣為:（3）圖Ｇ的每個結(jié)點的度數(shù)為：，，,,．(4)由關(guān)于補圖的定義3.1．9可知,先在圖G補充邊畫出完全圖(見下面左圖)，然后去掉原圖的邊,可得圖G補圖（見下面右注意:補圖中，假如沒有標(biāo)出結(jié)點v3,則是錯的.2.圖G=<V,E＞，其中V＝{ａ,ｂ,c,d,e}，Ｅ＝｛(a,b),（a,c),(a,e),(b,ｄ）,(ｂ，ｅ),(c,e),(c，d）,（d，ｅ)}，相應(yīng)邊的權(quán)值依次為2、１、2、3、６、1、4及5，試（1)畫出Ｇ的圖形；(2）寫出G的鄰接矩陣；（3）求出Ｇ權(quán)最小的生成樹及其權(quán)值．解(1）G的圖形如左下圖：(2）G的鄰接矩陣為:（３)圖G有5個結(jié)點，其生成樹有4條邊，用Ｋruｓｋａｌ算法求其權(quán)最小的生成樹T：第１步，取具最小權(quán)1的邊（a,c）；第２步,取剩余邊中具最小權(quán)1的邊(c，e)；第3步,取剩余邊中不與前２條邊構(gòu)成回路的具最小權(quán)２的邊（ａ,ｂ)；第4步,取剩余邊中不與前3條邊構(gòu)成回路的具最小權(quán)３的邊(b,d).所求最小生成樹T如下圖，其權(quán)為．注意：在用避圈法求最小的生成樹的關(guān)鍵是:“取圖中權(quán)數(shù)最小的邊,且與前面取到的邊不構(gòu)成圈”，很多學(xué)生只注意到取權(quán)數(shù)最小的邊了，而忽略了“不構(gòu)成圈”的規(guī)定。假如題目給出如解（1)中所示賦權(quán)圖，規(guī)定用Kruskal算法（避圈法）求出該賦權(quán)圖的最小生成樹,大家應(yīng)當(dāng)會吧．３．已知帶權(quán)圖Ｇ如右圖所示.(１)求圖G的最小生成樹;（２)計算該生成樹的權(quán)值.解（1)圖Ｇ有6個結(jié)點，其生成樹有５條邊，用Kruskａl算法求其權(quán)最小的生成樹T：第1步,取具最小權(quán)1的邊；第2步,取剩余邊中具最小權(quán)2的邊；第3步，取剩余邊中不與前2條邊構(gòu)成回路的具最小權(quán)3的邊;第４步,取剩余邊中不與前３條邊構(gòu)成回路的具最小權(quán)5的邊;第5步，取剩余邊中不與前４條邊構(gòu)成回路的具最小權(quán)7的邊.所求最小生成樹Ｔ如右圖．（２)該最小生成樹的權(quán)為.4.設(shè)有一組權(quán)為2,3,5,7,17,３1,試畫出相應(yīng)的最優(yōu)二叉樹,計算該最優(yōu)二叉樹的權(quán).解（Ｈuffman算法）:一方面組合２+3,求帶權(quán)5,5,7,１７，31的最優(yōu)二叉樹;再組合5+5,求帶權(quán)７,10,1７,31的最優(yōu)二叉樹；然后組合7+10，求帶權(quán)17,17,31的最優(yōu)二叉樹;繼續(xù)組合１７+17，求帶權(quán)31，3４的最優(yōu)二叉樹；最后組合31+3４,得65,這是樹根所帶的權(quán)。可從樹根開始往下畫，即得所求最優(yōu)二叉樹T如下圖:所求最優(yōu)二叉樹T的權(quán)為:講評：作業(yè)中最優(yōu)二叉樹往往都能畫對了,但計算總權(quán)值時也許會把有些權(quán)的層數(shù)計算錯了，導(dǎo)致總權(quán)值計算錯誤，大家一定要細心。注意：這4