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

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

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

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

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

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

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

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