離散數(shù)學(xué)圖論習(xí)題

1、第4章 圖論綜合練習(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(n>1)個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖

2、是平凡圖 (D) 圖中的基本回路都是簡(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)答案：C 6無向完全圖K3的不同構(gòu)的生成子圖的個(gè)數(shù)為（ ）(A) 6 (B) 5 (C) 4 (D) 3答案：C 7n階無向完全圖Kn中的邊數(shù)為（ ）(A) (B) (C) n (D)n(n+1)答案：B8以下命題正確的是(

3、)(A) n(n³1)階完全圖Kn都是歐拉圖 (B) n(n³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)的入度等于出度

4、答案：D11無向完全圖K4是（ ）（A）歐拉圖 （B）哈密頓圖 （C）樹 答案：B12有4個(gè)結(jié)點(diǎn)的非同構(gòu)的無向樹有 ( )個(gè) (A) 2 (B) 3 (C) 4 (D) 5答案：A13設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹(A) (B) (C) (D) 答案：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>

5、，其中|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的一棵生成樹T答案：46無向圖G為歐拉圖，當(dāng)且僅當(dāng)G是連通的，且G中無 結(jié)點(diǎn)答案：奇數(shù)度 · 2 2 3 · 1 · 7 9 2· 8 · 6 圖17設(shè)圖是簡(jiǎn)單圖，若圖中每對(duì)結(jié)點(diǎn)的度數(shù)之和 ，則G一定是哈密頓圖答案：8如圖1所示帶權(quán)圖中最小生成樹的權(quán)是 答案：12 v1 v2 v6 v5 v3 v4圖2三、化簡(jiǎn)解答題1設(shè)無向圖G<V,E>，

6、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) 寫出結(jié)點(diǎn)v2, v4，v6的度數(shù)；(3) 判斷圖G是簡(jiǎn)單圖還是多重圖 解：(1) 圖G的圖形如圖5所示(2) (3) 圖G是多重圖作圖如圖2. ah bh hech hd圖32設(shè)圖G<V，E>，其中 Va,b,c,d,e, E=(a,b),(b,c),(c,d), (a,e)試作出圖G的圖形，并指出圖G是簡(jiǎn)單圖還是多重圖？是連通圖嗎？說明理由. 解：圖G如圖8所示. 圖G中

7、既無環(huán)，也無平行邊，是簡(jiǎn)單圖圖G是連通圖G中任意兩點(diǎn)都連通. 所以，圖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)單無向圖圖4解：設(shè)圖G有x個(gè)結(jié)點(diǎn)，由握手定理 2´1+2´2+3´4+3´（x-2-2-3）12´2 x9故圖G有9個(gè)結(jié)點(diǎn) b · 23 1 15c· 25 ·a 4 · f 28 9 16 3 d · 15 · e 圖5滿足該條件的簡(jiǎn)單無向圖如圖4

8、所示2設(shè)圖G(如圖5表示)是6個(gè)結(jié)點(diǎn)a,b,c, d,e,f的圖，試求，圖G的最小生成樹，并計(jì)算它的權(quán)解：構(gòu)造連通無圈的圖，即最小生成樹，用克魯斯克爾算法： 第一步： 取ab1；第二步： 取af=4 第三步： 取fe3；第四步： 取ad=9 b · 23 1 c· · a 4 · f 9 3 d · · e 圖6 第五步： 取bc=23如圖6權(quán)為1+4+3+9+23=40 3一棵樹T有兩個(gè)2度頂點(diǎn)，1個(gè)3度頂點(diǎn)；3個(gè)4度頂點(diǎn)，問它有幾片樹葉？解：設(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) 由握手定理： 2·2+1·3+3·4+ (n21-3)=2(n1)解得 n=15于是T有15-6=9片樹葉 五、證明題1若無向圖G中只有兩個(gè)