離散數(shù)學(xué)圖論答案

1、離散數(shù)學(xué)圖論答案【篇一：離散數(shù)學(xué)圖論習(xí)題】綜合練習(xí)一、單項(xiàng)選擇題1 設(shè)l是n階無向圖g上的一條通路，則下面命題為假的是()(a)l可以不是簡(jiǎn)單路徑，而是基本路徑(b)l可以既是簡(jiǎn)單路徑,又是基本路徑(c)l可以既不是簡(jiǎn)單路徑，又不是基本路徑(d)l可以是簡(jiǎn)單路徑，而不是基本路徑答案：a2 下列定義正確的是()(a)含平行邊或環(huán)的圖稱為多重圖(b)不含平行邊或環(huán)的圖稱為簡(jiǎn)單圖(c)含平行邊和環(huán)的圖稱為多重圖(d)不含平行邊和環(huán)的圖稱為簡(jiǎn)單圖答案：d3以下結(jié)論正確是()(a)僅有一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖是零圖(b)無向完全圖kn每個(gè)結(jié)點(diǎn)的度數(shù)是n(c)有n(n1)個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖是平凡圖(d)圖中的

2、基本回路都是簡(jiǎn)單回路答案：d4下列數(shù)組中，不能構(gòu)成無向圖的度數(shù)列的數(shù)組是()(a)(1,1,1,2,3)(b)(1,2,3,4,5)(c)(2,2,2,2,2)(d)(1,3,3,3)答案：b5下列數(shù)組能構(gòu)成簡(jiǎn)單圖的是()(a)(0,1,2,3)(b)(2,3,3,3)(c)(3,3,3,3)(d)(4,2,3,3)答案：c6無向完全圖k3的不同構(gòu)的生成子圖的個(gè)數(shù)為()(a)6(b)5(c)4(d)3答案：c7 n階無向完全圖kn中的邊數(shù)為()(a)n(n?1)n(n?1)(b) (c)n(d)n(n+1)22答案：b8 以下命題正確的是()(a)n(n?1)階完全圖kn都是歐拉圖(b)n(n

3、?1)階完全圖kn都是哈密頓圖(c) 連通且滿足m=n1的圖v,e(?v?=n,?e?=m)是樹(d)n(n?5)階完全圖kn都是平面圖答案：c10下列結(jié)論不正確是()(a) 無向連通圖g是歐拉圖的充分必要條件是g不含奇數(shù)度結(jié)點(diǎn)(b) 無向連通圖g有歐拉路的充分必要條件是g最多有兩個(gè)奇數(shù)度結(jié)點(diǎn)(c)有向連通圖d是歐拉圖的充分必要條件是d的每個(gè)結(jié)點(diǎn)的入度等于出度(d) 有向連通圖d有有向歐拉路的充分必要條件是除兩個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的入度等1于出度答案：d11 無向完全圖k4是()(a)歐拉圖(b)哈密頓圖(c)樹答案：b12 有4個(gè)結(jié)點(diǎn)的非同構(gòu)的無向樹有()個(gè)(a)2(b)3(c)4(d)5答案

4、：a13 設(shè)g是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去g的()條邊，才能確定g的一棵生成樹(a)m?n?1(b)n?m(c)m?n?1(d)n?m?1答案：a14 設(shè)g是有6個(gè)結(jié)點(diǎn)的完全圖，從g中刪去()條邊，則得到樹(a)6(b)9(c)10(d)15答案：c二、填空題1 數(shù)組1，2，3，4，4是一個(gè)能構(gòu)成無向簡(jiǎn)單圖的度數(shù)序列，此命題的真值是.答案：02 無向完全圖k3的所有非同構(gòu)生成子圖有個(gè)答案：43 設(shè)圖g?v,e?，其中?v?n,?e?m則圖g是樹當(dāng)且僅當(dāng)g是連通的，且m?答案：n14 連通圖g是歐拉圖的充分必要條件是答案：圖g無奇數(shù)度結(jié)點(diǎn)5 連通無向圖g有6個(gè)頂點(diǎn)9條邊，從g中刪去g的

5、一棵生成樹t答案：46 無向圖g為歐拉圖，當(dāng)且僅當(dāng)g是連通的，且g中無答案：奇數(shù)度7 設(shè)圖g?v,e?是簡(jiǎn)單圖，若圖中每對(duì)結(jié)點(diǎn)的度數(shù)之和，則g一定是哈密頓圖答案：?8 如圖1所示帶權(quán)圖中最小生成樹的權(quán)是答案：12三、化簡(jiǎn)解答題1.設(shè)無向圖g=v,e,v=v1,v2,v3,v4,v5,v6,e=(v1,v2),(v2，v2),(v4，v5),(v3，v4),(v1，v3),(v3，v1),(v2，v4)(1)畫出圖g的圖形；2圖15圖22(2)寫出結(jié)點(diǎn)v2,v4，v6的度數(shù)；(3)判斷圖g是簡(jiǎn)單圖還是多重圖解：(1)圖g的圖形如圖5所示(2)deg(v2)?4,deg(v4)?3,deg(v6)

6、?0(3)圖g是多重圖.作圖如圖2.2.設(shè)圖g=v,e,其中v=a,b,c,d,e,e=(a,b),(b,c),(c,d),(a,e)試作出圖g的圖形，并指出圖g是簡(jiǎn)單圖還是多重圖？是連通圖嗎？說明理由.be解：圖g如圖8所示.圖g中既無環(huán)，也無平行邊，是簡(jiǎn)單圖cd圖g是連通圖g中任意兩點(diǎn)都連通.圖3所以，圖g有9個(gè)結(jié)點(diǎn)作圖如圖3四、計(jì)算題1 設(shè)簡(jiǎn)單連通無向圖g有12條邊，g中有2個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn)，其余結(jié)點(diǎn)度數(shù)為3求g中有多少個(gè)結(jié)點(diǎn)試作一個(gè)滿足該條件的簡(jiǎn)單無向圖解：設(shè)圖g有x個(gè)結(jié)點(diǎn)，由握手定理2?1+2?2+3?4+3?(x?2?2?3)=12?23x?24?21?18?

7、27x=9故圖g有9個(gè)結(jié)點(diǎn).圖4滿足該條件的簡(jiǎn)單無向圖如圖4所示2 設(shè)圖g(如圖5表示)是6個(gè)結(jié)點(diǎn)a,b,c,d,e,f的圖，試求，圖g的最小生成樹，并計(jì)算它的權(quán)c解：構(gòu)造連通無圈的圖，即最小生成樹，用克魯斯克爾算法：第一步：取ab=1;第二步：取af=4第三步：取fe=3;第四步:取ad=9圖5第五步：取bc=23如圖6權(quán)為1+4+3+9+23=403 一棵樹t有兩個(gè)2度頂點(diǎn)，1個(gè)3度頂點(diǎn)；3個(gè)4問它有幾片樹葉？解：設(shè)t有n頂點(diǎn)，則有n1條邊t中有2個(gè)2度頂點(diǎn)，1個(gè)3度頂點(diǎn)，3個(gè)4度頂點(diǎn)，其余n21-3個(gè)1度頂點(diǎn)五、證明題1若無向圖g中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定是連通的證：用反證法

8、設(shè)g中的兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u和v假若u和v不連通即它們之間無任何通路，則g至少有兩個(gè)連通分支g1，g2，且u和v分別屬于g1和g2，于是g1和g2各含有一個(gè)奇數(shù)度結(jié)點(diǎn)這與握手定理的推論矛盾因而u和v一定是連通的3【篇二：離散數(shù)學(xué)圖論練習(xí)題】題1 、設(shè)g是一個(gè)哈密爾頓圖，則g一定是()。(1)歐拉圖(2)樹(3)平面圖(4)連通圖2、下面給出的集合中，哪一個(gè)是前綴碼？()(1)0，10，110，101111(2)01，001，000，1(3)b，c，aa，ab，aba(4)1，11，101，001，00113、一個(gè)圖的哈密爾頓路是一條通過圖中()的路。4、設(shè)g是一棵樹，則g的生成樹有()棵。(

9、1)02 2)1(3)2(4)不能確定5、n階無向完全圖kn的邊數(shù)是()，每個(gè)結(jié)點(diǎn)的度數(shù)是()。6、一棵無向樹的頂點(diǎn)數(shù)n與邊數(shù)m關(guān)系是()。7、一個(gè)圖的歐拉回路是一條通過圖中()的回路。8、有n個(gè)結(jié)點(diǎn)的樹，其結(jié)點(diǎn)度數(shù)之和是()。9、下面給出的集合中，哪一個(gè)不是前綴碼()。(1)a，ab，110，a1b11(2)01，001，000，1(3)1，2，00，01，0210(4)12，11，101，002，001110、n個(gè)結(jié)點(diǎn)的有向完全圖邊數(shù)是()，每個(gè)結(jié)點(diǎn)的度數(shù)是()。11、一個(gè)無向圖有生成樹的充分必要條件是()。12、設(shè)g是一棵樹，n,m分別表示頂點(diǎn)數(shù)和邊數(shù)，則(1)n=m(2)m=n+1(3

10、)n=m+1(4)不能確定。13、設(shè)t=v,e是一棵樹，若|v|1，則t中至少存在()片樹葉。14、任何連通無向圖g至少有()棵生成樹，當(dāng)且僅當(dāng)g是()，g的生成樹只有一棵。15、設(shè)g是有n個(gè)結(jié)點(diǎn)m條邊的連通平面圖，且有k個(gè)面，則k等于:(1)m-n+2(2)n-m-2(3)n+m-2(4)m+n+2。16、設(shè)t是一棵樹，則t是一個(gè)連通且()圖。17、設(shè)無向圖g有16條邊且每個(gè)頂點(diǎn)的度數(shù)都是2，則圖g有()個(gè)頂點(diǎn)。(1)10(2)4(3)8(4)1618、設(shè)無向圖g有18條邊且每個(gè)頂點(diǎn)的度數(shù)都是3，則圖g有()個(gè)頂點(diǎn)。(1)10(2)4(3)8(4)1219 、任一有向圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)有

11、()個(gè)。20 、具有6個(gè)頂點(diǎn)，12條邊的連通簡(jiǎn)單平面圖中，每個(gè)面都是由()條邊圍成？(1)2(2)4(3)3(4)521 、在有n個(gè)頂點(diǎn)的連通圖中，其邊數(shù)()。(1)最多有n-1條(2)至少有n-1條(3)最多有n條(4)至少有n條22、一棵樹有2個(gè)2度頂點(diǎn)，1個(gè)3度頂點(diǎn)，3個(gè)4度頂點(diǎn)，則其1度頂點(diǎn)為(1)5(2)7(3)8(4)923、若一棵完全二元(叉)樹有2n-1個(gè)頂點(diǎn)，則它()片樹葉。(1)n(2)2n(3)n-1(4)224、下列哪一種圖不一定是樹()。(1)無簡(jiǎn)單回路的連通圖(2)有n個(gè)頂點(diǎn)n-1條邊的連通圖(3)每對(duì)頂點(diǎn)間都有通路的圖(4)連通但刪去一條邊便不連通的圖25、連通圖

12、g是一棵樹當(dāng)且僅當(dāng)g中()。(1)有些邊是割邊(2)每條邊都是割邊(3)所有邊都不是割邊(4)圖中存在一條歐拉路徑26對(duì)于無向圖，下列說法中()是正確的.a不含平行邊及環(huán)的圖稱為完全圖b任何兩個(gè)不同結(jié)點(diǎn)都有邊相連且無平行邊及環(huán)的圖稱為完全圖c具有經(jīng)過每條邊一次且僅一次回路的圖稱為哈密爾頓圖d具有經(jīng)過每個(gè)結(jié)點(diǎn)一次且僅一次回路的圖稱為歐拉圖27設(shè)圖g的鄰接矩陣為?00100?00011?10000?01001?01010?則g的邊數(shù)為()a.5b.6c.3d.428.設(shè)圖g=v,e,則下列結(jié)論成立的是().adeg(v)=2?e?bdeg(v)=?e?)。c?deg(v)?2ed?deg(v)?e

13、v?vv?v29 圖g如右圖所示，以下說法正確的是()a(a,d)是割邊b(a,d)是邊割集c(d,e)是邊割集d(a,d),(a,c)是邊割集30 設(shè)g是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r=()aev2bve2cev2dev231無向圖g存在歐拉通路，當(dāng)且僅當(dāng)()ag中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)bg中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)cg連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)dg連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)二、填空題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ù)是2 .設(shè)給定圖g(如右圖所示)，則圖g的點(diǎn)割集是.3 .設(shè)無向圖g=v,e是漢密爾頓圖，則v的任意非空子集v1,都

14、有?v1?4 設(shè)有向圖d為歐拉圖，則圖d中每個(gè)結(jié)點(diǎn)的入度5 設(shè)完全圖kn有n個(gè)結(jié)點(diǎn)(n?2)，m條邊，當(dāng)時(shí)，kn中存在歐拉回路6 給定一個(gè)序列集合1，01，10，11，001，000，若去掉其中的元素合構(gòu)成前綴碼eda?dbfea?b?fc三、計(jì)算題1 .設(shè)圖g?v,e?,其中v?a1,a2,a3,a4,a5?,e?a1,a2?，?a2,a4?，?a3,a1?，?a4,a5?，?a5,a2?(1)試給出g的圖形表示；(2)求g的鄰接矩陣；(3)判斷圖g是強(qiáng)連通圖、單側(cè)連通圖還是弱連通圖？2 圖g=v,e，其中v=a,b,c,d,e,f，e=(a,b),(a,c),(a,e),(b,d),(b,

15、e),(c,e),(d,e),(d,f),(e,f)，對(duì)應(yīng)邊的權(quán)值依次為5，2，1，2，6，1，9，3及8(1)畫出g的圖形；(2)寫出g的鄰接矩陣；a2c1569b2d(3)求出g權(quán)最小的生成樹及其權(quán)值問：如果結(jié)點(diǎn)集是v=a,b,c,d,e，邊集e=(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e)，對(duì)應(yīng)邊的權(quán)值依次為5，2，1，2，6，1，9，那么會(huì)求嗎？3設(shè)有一組權(quán)為2,3,5,7,11,13,17,19,23,29,31,試(1)畫出相應(yīng)的最優(yōu)二叉樹；(2)計(jì)算它們的權(quán)值160?6595解：(1)最優(yōu)二叉樹如右圖所示：4234531724191055問：

16、如果一組權(quán)為2,3,6,9,13,15,能否畫出最優(yōu)二叉樹？【篇三：離散數(shù)學(xué)習(xí)題解答第6部分(圖論)】1從日常生活中列舉出三個(gè)例子，并由這些例子自然地導(dǎo)出兩個(gè)無向圖及一個(gè)向圖。解用v代表全國(guó)城市的集合，e代表各城市間的鐵路線的集合，則所成之圖g=(v，e)是全國(guó)鐵路交通圖。是一個(gè)無向圖。v用代表中國(guó)象棋盤中的格子點(diǎn)集，e代表任兩個(gè)相鄰小方格的對(duì)角線的集合，則所成之圖g=(v,e)是中國(guó)象棋中馬”所能走的路線圖。是一個(gè)無向圖。用v代表fortran程序的塊集合，e代表任兩個(gè)程序塊之間的調(diào)用關(guān)系，則所成之圖g+(v，e)是fortran程序的調(diào)用關(guān)系圖。是一個(gè)有向圖。2畫出下左圖的補(bǔ)圖。解左圖的補(bǔ)

17、圖如右圖所示。3 證明下面兩圖同構(gòu)。v2a圖g'v3圖gv4證存在雙射函數(shù)？:v-v'及雙射函數(shù)？：e-e'?(v1)=v1'?(v2)=v2'?(v3)=v3'?(v4)=v4'?(v5)=v5(v6)=v6'?(v1，v2)=(v1；v2')?(v2v3)=(v2；v3')?(v3v4)=(v3:v4')?(v4v5)=(v4；v5)?(v5,v6)=(v5；v6')?(v6v1)=(v6:v1')?(v1,v4)=(v1；v4')?(v2v5)=(v2；v5')?(v3

18、v6)=(v3；v6')顯然使下式成立：4 證明(a)，(b)中的兩個(gè)圖都是不同構(gòu)的。圖g中有一個(gè)長(zhǎng)度為4的圈v1v2v6v5v1，其各頂點(diǎn)的度均為3點(diǎn)，而在圖g中卻沒有這樣的圈，因?yàn)樗械乃膫€(gè)度為3的頂點(diǎn)v1?,v5?，v7?，v3?不成長(zhǎng)度的4的圈。圖g中有四個(gè)二度結(jié)點(diǎn)，v6?,v8?,v4?,它們每個(gè)都和兩個(gè)三度結(jié)點(diǎn)相鄰，而g中一個(gè)區(qū)樣的結(jié)點(diǎn)都沒有。在(b)中，圖g?中有一2度結(jié)點(diǎn)v3?,它相鄰的兩個(gè)項(xiàng)點(diǎn)v2?,v4?的度均為4，而在圖g中卻沒有這樣的點(diǎn)。gg'gg'v3?v4?5 一個(gè)圖若同構(gòu)于它的外圖，則稱此圖為自補(bǔ)圖。在滿足下列條件的無向簡(jiǎn)單圖中：1)給出一

19、個(gè)五個(gè)結(jié)點(diǎn)的自補(bǔ)圖；2)有三個(gè)或一結(jié)點(diǎn)的自補(bǔ)圖嗎？為什么？3)證明：若一個(gè)圖為自補(bǔ)圖，則它對(duì)應(yīng)的完全圖的邊數(shù)不清必然為偶數(shù)。解1)五個(gè)結(jié)點(diǎn)的自補(bǔ)圖如左圖g所示同構(gòu)函數(shù)？:vfv及？:efe如下：？(a)=a?(b)=c?(c)=e?(d)=b?(e)=d?(a，b)=(a，c)?(b，c)=(c，e)?(c，d)=(e，d)?(d，e)=(b，d)(e，a)=(d，a)ggebae2)(a)沒有三個(gè)結(jié)點(diǎn)的自補(bǔ)圖。因?yàn)槿齻€(gè)結(jié)點(diǎn)的完備圖的邊數(shù)為3(3?1)=32為奇數(shù)，所以由下面3)的結(jié)論，不可能有自補(bǔ)圖。(b)有五個(gè)結(jié)點(diǎn)的自補(bǔ)圖。1)中的例子即是一個(gè)五個(gè)結(jié)點(diǎn)的自補(bǔ)圖。3)證：一個(gè)圖是一個(gè)自補(bǔ)圖，

20、則它對(duì)應(yīng)的完全圖的邊數(shù)必為偶數(shù)。實(shí)際上，n個(gè)項(xiàng)點(diǎn)(n>3)的自補(bǔ)圖g,由于其對(duì)應(yīng)的完全圖的邊數(shù)|e*尸n(n?1)n(n?1),因此有二2|e|,為偶數(shù)。這里n>4o對(duì)于所有大于或等22于4的正整數(shù)，都可表達(dá)成n=4k，4k+1，4k+2，4k+3的形式，這里k=1，2，?。其中只有n=4k,4k+1,才能使4k或4k+1形式，(kGn)n(n?1)為偶數(shù)，所以自補(bǔ)圖的項(xiàng)點(diǎn)數(shù)只能是26 證明在任何兩個(gè)或兩個(gè)以上人的組內(nèi)，總存在兩個(gè)人在組內(nèi)有相同個(gè)數(shù)的朋友。證令上述組內(nèi)的人的集合為圖g的項(xiàng)點(diǎn)集v，若兩人互相是朋友，則其間聯(lián)以一邊。所得之圖g是組內(nèi)人員的朋友關(guān)系圖。顯然圖g是簡(jiǎn)單圖，圖

21、中項(xiàng)點(diǎn)的度恰表示該人在組內(nèi)朋友的個(gè)數(shù)，利用圖g，上述問題就抽象成如下的圖認(rèn)論問題：在簡(jiǎn)單圖g中，若v|)2則在g中恒存在著兩個(gè)項(xiàng)點(diǎn)，v1,v2Gv,使得它們的度相等，即deg(v1)=deg(v2)。其證明如下：若存在著一個(gè)項(xiàng)點(diǎn)vGv,使得deg(v)=0,則圖g中各項(xiàng)點(diǎn)的度最大不超過n-2。因此n個(gè)項(xiàng)點(diǎn)的度在集合0，1，2，?，n-2里取值，而這個(gè)集合只有n-1個(gè)元素，因此，根據(jù)鴿籠原理，必有兩個(gè)項(xiàng)點(diǎn)的度相同。若不存在一個(gè)度為零的項(xiàng)點(diǎn)，則圖g中各項(xiàng)點(diǎn)的度最大不超過n-1因此n個(gè)項(xiàng)點(diǎn)的度在集合1，2，?，n-1中取值，這個(gè)集合只有n-1個(gè)元素，因此，根據(jù)鴿籠原理，必有兩具項(xiàng)點(diǎn)的度相同。7 設(shè)圖g的圖示如右所示：1)找出從a到f的所有初級(jí)路；2)找出從a到f的所有簡(jiǎn)單路；3)求由a到f的距離。解1)從a到f的初級(jí)路有7條ep1:（a