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、一個(gè)圖的歐拉回路是一條通過圖中( )

2、的回路。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中至少存在( )片樹葉。14、任何連通無向圖G至少有( )棵生成樹，當(dāng)且

3、僅當(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)有()個(gè)。20、具有6 個(gè)頂點(diǎn)，12條邊的連通簡單平面圖中，每個(gè)面都是由()條邊圍成？(

4、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) 無簡單回路的連通圖(2) 有n個(gè)頂點(diǎn)n-1條邊的連通圖 (3) 每對頂點(diǎn)間都有通路的圖 (4) 連通但刪去一條邊便不連通的圖25、連通圖G是一棵樹當(dāng)且

5、僅當(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的鄰接矩陣為則G的邊數(shù)為( )A5 B6 C3 D428設(shè)圖G，則下列結(jié)論成立的是 ( )Adeg(V)=2E Bdeg(V)=EC D29圖G如右圖所示，以下說法正確的是 ( ) A(a, d)是割邊B(a, d)是邊割集ooooocabedofC(

6、d, e)是邊割集D(a, d) ,(a, c)是邊割集 30設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )Aev2 Bve2 Cev2 Dev231無向圖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)二、填空題ooooocabedof1已知圖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的任意非空子集V1，都有 V14設(shè)有向圖D為歐拉圖，則圖D中每個(gè)結(jié)點(diǎn)的入度 5設(shè)完全圖K

7、有n個(gè)結(jié)點(diǎn)(n2)，m條邊，當(dāng) 時(shí)，K中存在歐拉回路6給定一個(gè)序列集合1，01，10，11，001，000，若去掉其中的元素 ，則該序列集合構(gòu)成前綴碼三、計(jì)算題1設(shè)圖G=，其中V=a1, a2, a3, a4, a5,E=，（1）試給出G的圖形表示；（2）求G的鄰接矩陣；（3）判斷圖G是強(qiáng)連通圖、單側(cè)連通圖還是弱連通圖？2圖G=，其中V=a, b, c, d, e, f ，E=(a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f)，對應(yīng)邊的權(quán)值依次為5，2，1，2，6，1，9，3及8（1）畫出G的圖形；ooooocabedof152261938（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)