(完整word版)離散數(shù)學(xué)圖論練習(xí)題

1、1圖論練習(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 的生成樹有 ()棵。(1) 0 (2) 1 (3) 2 (4) 不能確定5、n 階無向完全圖 Kn 的邊數(shù)是 ()，每個(gè)結(jié)點(diǎn)的度數(shù)是 ()。6、一棵無向樹的頂點(diǎn)數(shù) n 與邊數(shù) m 關(guān)系是 ( )。7

2、、一個(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) n=m+1 (4) 不能確定。13、 設(shè) T=V,E是一棵樹，若|V|1，則 T

3、 中至少存在()片樹葉。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) 16218、 設(shè)無向圖 G 有 18 條邊且每個(gè)頂點(diǎn)的度數(shù)都是 3，則圖 G 有()個(gè)頂點(diǎn)。(1) 10(2) 4(3) 8 (4

4、) 1219、任一有向圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)有 () 個(gè)。20、具有 6 個(gè)頂點(diǎn)， 12 條邊的連通簡單平面圖中，每個(gè)面都是由 ()條邊圍成？(1) 2 (2) 4 (3) 3 (4) 521、在有 n 個(gè)頂點(diǎn)的連通圖中，其邊數(shù)( )。最多有 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、

5、下列哪一種圖不一定是樹()。(1) 無簡單回路的連通圖 (2) 有 n 個(gè)頂點(diǎn) n-1 條邊的連通圖(3) 每對頂點(diǎn)間都有通路的圖 (4) 連通但刪去一條邊便不連通的圖25、連通圖 G 是一棵樹當(dāng)且僅當(dāng) G 中( )。(1) 有些邊是割邊 (2) 每條邊都是割邊(3) 所有邊都不是割邊 (4) 圖中存在一條歐拉路徑 26對于無向圖，下列說法中( )是正確的 .A 不含平行邊及環(huán)的圖稱為完全圖B 任何兩個(gè)不同結(jié)點(diǎn)都有邊相連且無平行邊及環(huán)的圖稱為完全圖C.具有經(jīng)過每條邊一次且僅一次回路的圖稱為哈密爾頓圖D .具有經(jīng)過每個(gè)結(jié)點(diǎn)一次且僅一次回路的圖稱為歐拉圖27.設(shè)圖 G 的鄰接矩陣為0010 000

6、01 11000 00100 101010則 G 的邊數(shù)為 () .A . 5B.6C.3D. 4328.設(shè)圖 G= ,則下列結(jié)論成立的是().A . deg(V)=2 EB.deg(V)= E4C.deg(v) 2 Ev V29 圖 G 如右圖所示，以下說法正確的是A . (a, d)是割邊B.(a, d)是邊割集C.(d, e)是邊割集D . (a, d) ,(a, c)是邊割集B . G 中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)C . G 連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)D.G 連通且至多有兩個(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 度

7、結(jié)點(diǎn)，則 G 的邊數(shù)是_.2.設(shè)給定圖 G(如右圖所示)，則圖 G 的點(diǎn)割集是3. 設(shè)無向圖 G= 是漢密爾頓圖，則 V 的任意非空子集 V1，都有_ V1.4._ 設(shè)有向圖 D 為歐拉圖，則圖 D 中每個(gè)結(jié)點(diǎn)的入度 _.5 .設(shè)完全圖 Kn有 n 個(gè)結(jié)點(diǎn)(n 2), m 條邊，當(dāng) _時(shí)，Kn中存在歐拉回路.合構(gòu)成前綴碼.D.deg(v) Ev V( ).30 .設(shè) G 是連通平面圖，有 v 個(gè)結(jié)點(diǎn)，A . e- v + 2B . v+ e- 231.無向圖 G 存在歐拉通路，當(dāng)且僅當(dāng)A . G 中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)e 條邊，r 個(gè)面，則 r=().C . ev2D . e+ v+26.給

8、定一個(gè)序列集合1 , 01, 10, 11, 001, 000，若去掉其中的元素_，則該序列集cd5二、計(jì)算題1 .設(shè)圖 G V, E，其中 V ai, a2, a3, a4, a5,E ai, a2, a2, a4, a3, ai, a4, a5, a5, a2(1) 試給出 G 的圖形表示；(2) 求 G 的鄰接矩陣；(3) 判斷圖 G 是強(qiáng)連通圖、單側(cè)連通圖還是弱連通圖？(d, e), (d, f), (e, f)，對應(yīng)邊的權(quán)值依次為(1)畫出 G 的圖形;(2)寫出 G 的鄰接矩陣；(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) ，對應(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)值.解：(1)最優(yōu)二叉樹如右圖所示:2.圖 G=，其中