圖論復(fù)習(xí)題(中文)

1、1、設(shè)G是一個(gè)哈密爾頓圖，則 G一定是（）。 歐拉圖（2） 樹(shù) （3）平面圖（4） 連通圖答：（4）（考察圖的定義）2、一個(gè)圖的哈密爾頓路是一條通過(guò)圖中（） 的路。答：所有結(jié)點(diǎn)一次且恰好一次3、在有向圖中，結(jié)點(diǎn)v的出度deg+（v）表示（），入度deg-（v）表示（）。 答：以v為起點(diǎn)的邊的條數(shù)，以v為終點(diǎn)的邊的條數(shù)4、設(shè)G是一棵樹(shù)，則G的生成樹(shù)有（） 棵。0（2） 1（3） 2（4）不能確定答：15、n階無(wú)向完全圖（的邊數(shù)是（），每個(gè)結(jié)點(diǎn)的度數(shù)是（）。答：皿心，n-126、一棵無(wú)向樹(shù)的頂點(diǎn)數(shù)n與邊數(shù)m關(guān)系是（）o答：m=n-17、一個(gè)圖的歐拉回路是一條通過(guò)圖中（） 的回路。答：所有邊一次且恰

2、好一次8、有n個(gè)結(jié)點(diǎn)的樹(shù)，具結(jié)點(diǎn)度數(shù)之和是（）o答：2n-2 （結(jié)點(diǎn)度數(shù)的定義）9、n個(gè)結(jié)點(diǎn)的有向完全圖邊數(shù)是（），每個(gè)結(jié)點(diǎn)的度數(shù)是（）。答：n（n-1）,2n-210、一個(gè)無(wú)向圖有生成樹(shù)的充分必要條件是（）。答：它是連通圖11、設(shè)G是一棵樹(shù)，n,m分別表示頂點(diǎn)數(shù)和邊數(shù)，則n=m m=n+1n=m+1 （4） 不能確定。答：12、設(shè)丁=V,E是一棵樹(shù)，若|V|>1 ,則T中至少存在（） 片樹(shù)葉。答：213、任何連通無(wú)向圖G至少有（）棵生成樹(shù)，當(dāng)且僅當(dāng)G是（），G的生成樹(shù)只有一棵。答：1,樹(shù)14、設(shè)G是有n個(gè)結(jié)點(diǎn)m條邊的連通平面圖，且有k個(gè)面，則k等于:(1) m-n+2 (2) n-m-

3、2 (3) n+m-2 (4) m+n+2。答： ( 1)15、設(shè) T 是一棵樹(shù)，則 一棵樹(shù)，則 T 是一個(gè)連通且 () 圖。答：無(wú)簡(jiǎn)單回路 16、設(shè)無(wú)向圖G有16條邊且每個(gè)頂點(diǎn)的度數(shù)都是 2,則圖6有()個(gè)頂點(diǎn)(1) 10 (2) 4 (3) 8 (4) 16答：( 4)17、設(shè)無(wú)向圖G有18條邊且每個(gè)頂點(diǎn)的度數(shù)都是 3,則圖6有()個(gè)頂點(diǎn)(1) 10 (2) 4 (3) 8 (4) 12答： (4)18、 設(shè)圖G=<V， E>， V=a， b， c ， d， e ， E=<a,b>,<a,c>,<b,c>,<c,d>,<d,

4、e>,則 G 是有向圖還是無(wú)向圖？答：有向圖19、任一有向圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)有() 個(gè)。答：偶數(shù)20、具有6 個(gè)頂點(diǎn)， 12 條邊的連通簡(jiǎn)單平面圖中，每個(gè)面都是由 () 條邊圍成？(1) 2(2) 4(3) 3(4) 5答： ( 3)21、在有 n 個(gè)頂點(diǎn)的連通圖中，其邊數(shù)( ) 。(1)最多有n-1 條(2)至少有n-1 條(3)最多有n 條(4)至少有n 條答： ( 2)22、一棵樹(shù)有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) 9答： ( 4)23、若一棵完全二元(叉)樹(shù)有2n-1 個(gè)頂點(diǎn)，則它( )片樹(shù)葉。(

5、1) n (2) 2n (3) n-1(4) 2答： ( 1)24、下列哪一種圖不一定是樹(shù)( ) 。(1) 無(wú)簡(jiǎn)單回路的連通圖 (2) 有 n 個(gè)頂點(diǎn) n-1 條邊的連通圖(3) 每對(duì)頂點(diǎn)間都有通路的圖 (4) 連通但刪去一條邊便不連通的圖答： ( 3)25、連通圖G是一棵樹(shù)當(dāng)且僅當(dāng)6中()。(1)有些邊是割邊(2)每條邊都是割邊(3)所有邊都不是割邊 (4)圖中存在一條歐拉路徑答：26、證明在有n個(gè)結(jié)點(diǎn)的樹(shù)中，其結(jié)點(diǎn)度數(shù)之和是 2n-2。證明：設(shè)丁=<丫上>1 任一棵樹(shù)，則 |V|=n ,且 |E|=n-1 。由歐拉握手定理，樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和等于2|E|.從而結(jié)點(diǎn)度數(shù)之和是

6、2n-2。27、任一圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)是偶數(shù)個(gè)。證明：設(shè)6= <V,E>是任一圖。設(shè)|V|二n。由歐拉握手定理可得 £ deg(v)=2|E|可得，圖中所有結(jié)點(diǎn)度數(shù)之和是v . V偶數(shù)。顯然所有偶數(shù)度結(jié)點(diǎn)的度數(shù)之和仍為偶數(shù)，從而所有奇數(shù)度結(jié)點(diǎn)的度數(shù)之和也是偶數(shù)。因此，圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)一定為偶數(shù)個(gè)。28、連通無(wú)向圖G的任何邊一定是G的某棵生成樹(shù)的弦。這個(gè)斷言對(duì)嗎？若是對(duì)的請(qǐng)證明之，否則請(qǐng)舉例說(shuō)明。證明：不對(duì)。反例如下：若G本身是一棵樹(shù)時(shí)，則G的每一條邊都不可能是 G的任 一棵生成樹(shù)(實(shí)際上只有惟一一棵)的弦。29、設(shè)T=<V,E射一棵樹(shù)，若|V|>1 ,則

7、T中至少存在兩片樹(shù)葉。證明：(用反證法證明)設(shè)|V|=n。因?yàn)門(mén)= <V,E>是一棵樹(shù)，所以|E|=n-1 。由歐拉握手定理可得 Z deg(v)=2|E|=2n-2 。vV假設(shè)T中最多只有1片樹(shù)葉，則£ deg(v) >2(n-1)+1>2n-2 。得出矛盾。30、設(shè)無(wú)向圖G=<V,E> |E|=12 0已知有6個(gè)3度頂點(diǎn)，其他頂點(diǎn)的度數(shù)均小于3。問(wèn)G中至少有多少個(gè)頂點(diǎn)？解：設(shè)G中度數(shù)小于3的頂點(diǎn)有k個(gè)，由歐拉握手定理24= 二 deg(v)v-V知，度數(shù)小于3的頂點(diǎn)度數(shù)之和為6。故當(dāng)其余的頂點(diǎn)度數(shù)都為2時(shí)，G的頂點(diǎn)最少。即G中至少有9個(gè)頂點(diǎn)。3

8、0、設(shè)圖G=<V,E> |V|=n , |E|二m。k度頂點(diǎn)有nk個(gè)，且每個(gè)頂點(diǎn)或是k度 頂點(diǎn)或是k+1度頂點(diǎn)。證明：nk=(k+1)-2m。證明：由已知可知，G中k+1度頂點(diǎn)為n-nk個(gè)。再由歐拉握手定理可知2m=" deg(v) =knk+(k+1)(n-n k)=(k+1)n+-n kv. V故 nk=(k+1)-2m 。31、如下圖所示的賦權(quán)圖表示某七個(gè)城市 V1，V2,，V7及預(yù)先算出它們之間的一些 直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造 價(jià)最小。解：用庫(kù)斯克(Kruskal )算法求產(chǎn)生的最優(yōu)樹(shù)。算法略。結(jié)果如圖:樹(shù)權(quán) C(T)=23+1+4+9+3+17=57即為總造價(jià)。一、填空題（每個(gè)2 分，共20分）二、選擇題（每個(gè)2 分，共20分）三、問(wèn)答題（每個(gè)4 分，共20