- 相關推薦
圖論復習試題及答案
圖論是數學的一個分支，它以圖為研究對象。以下是由陽光網小編整理關于圖論復習試題的內容，希望大家喜歡!
圖論復習試題及答案
1、設G是一個哈密爾頓圖，則G一定是( )。
(1) 歐拉圖 (2) 樹 (3) 平面圖 (4) 連通圖
答：(4)(考察圖的定義)
2、一個圖的哈密爾頓路是一條通過圖中( )的路。
答：所有結點一次且恰好一次
3、在有向圖中，結點v的出度deg+(v)表示( )，入度deg-(v)表示( )。 答：以v為起點的邊的條數， 以v為終點的邊的條數
4、設G是一棵樹，則G 的生成樹有( )棵。
(1) 0 (2) 1 (3) 2 (4) 不能確定
答：1
5、n階無向完全圖Kn 的邊數是( )，每個結點的度數是( )。 n(n?1)答：, n-1 2
6、一棵無向樹的頂點數n與邊數m關系是( )。
答：m=n-1
7、一個圖的歐拉回路是一條通過圖中( )的回路。
答：所有邊一次且恰好一次
8、有n個結點的樹，其結點度數之和是( )。
答：2n-2(結點度數的定義)
9、n個結點的有向完全圖邊數是( )，每個結點的度數是( )。 答：n(n-1),2n-2
10、一個無向圖有生成樹的充分必要條件是( )。
答：它是連通圖
11、設G是一棵樹，n,m分別表示頂點數和邊數，則
(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能確定。
答：(3)
12、設T=〈V,E〉是一棵樹，若|V|>1，則T中至少存在( )片樹葉。 答：2
13、任何連通無向圖G至少有( )棵生成樹，當且僅當G 是( )，G的生成樹只有一棵。
答：1， 樹
14、設G是有n個結點m條邊的連通平面圖，且有k個面，則k等于:
(1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。
答：(1)
15、設T是一棵樹，則T是一個連通且( )圖。
答：無簡單回路
16、設無向圖G有16條邊且每個頂點的度數都是2，則圖G有( )個頂點。
(1) 10 (2) 4 (3) 8 (4) 16
答：(4)
17、設無向圖G有18條邊且每個頂點的度數都是3，則圖G有( )個頂點。
(1) 10 (2) 4 (3) 8 (4) 12
答：(4)
18、設圖G=<V，E>，V={a，b，c，d，e}，E={<a,b>,<a,c>,<b,c>,<c,d>,<d,e>},則G是有向圖還是無向圖?
答：有向圖
19、任一有向圖中，度數為奇數的結點有( )個。
答：偶數
20、具有6 個頂點，12條邊的連通簡單平面圖中，每個面都是由( )條邊圍成?
(1) 2 (2) 4 (3) 3 (4) 5
答：(3)
21、在有n個頂點的連通圖中，其邊數( )。
(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個頂點，則它( )片樹葉。
(1) n (2) 2n (3) n-1 (4) 2
答：(1)
24、下列哪一種圖不一定是樹( )。
(1) 無簡單回路的連通圖 (2) 有n個頂點n-1條邊的連通圖
(3) 每對頂點間都有通路的圖 (4) 連通但刪去一條邊便不連通的圖 答：(3)
25、連通圖G是一棵樹當且僅當G中( )。
(1) 有些邊是割邊 (2) 每條邊都是割邊
(3) 所有邊都不是割邊 (4) 圖中存在一條歐拉路徑
答：(2)
下一頁更多有關“圖論復習試題及答案”的內容
26、證明在有n個結點的樹中，其結點度數之和是2n-2。
證明：
設T=<V,E>是任一棵樹，則|V|=n，且|E|=n-1。
由歐拉握手定理，樹中所有結點的度數之和等于2|E|.
從而結點度數之和是2n-2。
27、任一圖中度數為奇數的結點是偶數個。
證明：
設G=〈V,E〉是任一圖。設|V|=n。
由歐拉握手定理可得 ?deg(v)=2|E|可得，圖中所有結點度數之和是
v?V
偶數。顯然所有偶數度結點的度數之和仍為偶數，從而所有奇數度結點的度數之和也是偶數。因此，圖中度數為奇數的結點一定為偶數個。
28、連通無向圖G的任何邊一定是G的`某棵生成樹的弦。這個斷言對嗎?若是對的請證明之，否則請舉例說明。
證明：
不對。
反例如下：若G 本身是一棵樹時，則G的每一條邊都不可能是G的任一棵生成樹(實際上只有惟一一棵)的弦。
29、設T=<V,E>是一棵樹，若|V|>1，則T中至少存在兩片樹葉。
證明：
(用反證法證明)設|V|=n。
因為T=〈V,E〉是一棵樹，所以|E|=n-1。
由歐拉握手定理可得 ?deg(v)=2|E|=2n-2。
v?V
假設T中最多只有1片樹葉，則?deg(v)?2(n-1)+1>2n-2。
v?V
得出矛盾。
30、設無向圖G=<V,E>，|E|=12。已知有6個3度頂點，其他頂點的度數均小于3。問G中至少有多少個頂點?
解：
設G中度數小于3的頂點有k個，由歐拉握手定理
24=?deg(v)
v?V
知，度數小于3 的頂點度數之和為6。故當其余的頂點度數都為2時，G的
頂點最少。即G中至少有9個頂點。
30、設圖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-nk)=(k+1)n+-nk
v?V
故nk=(k+1)-2m。
31、如下圖所示的賦權圖表示某七個城市v1,v2,?,v7及預先算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間能夠通信而且總造價最小。
解： 用庫斯克(Kruskal)算法求產生的最優樹。算法略。結果如圖：
樹權C(T)=23+1+4+9+3+17=57即為總造價。
一、填空題(每個2分，共20分)
二、選擇題(每個2分，共20分)
三、問答題(每個4分，共20分)
1、圖的同構
2、圖的連通
3、Hamilton圖
4、Euler 圖
5、樹圖
6、割邊
7、割點
8、關聯矩陣
9、鄰接矩陣
10、連通度
11、完全圖
12、二部圖
13、簡單圖
14、平面圖
15、生成樹
四、證明題(每題10分，共20分)
五、計算題(20分)
【圖論復習試題及答案】相關文章：
《國際結算》復習試題及答案11-23
電氣測量試題及答案-《電氣測量》期末復習試題及答案11-23
電子測量試題及答案-《電子測量》期末復習試題及答案11-22
電氣控制與PLC試題及答案-《電氣控制與PLC》復習試題及答案11-23
商法期末復習試題及參考答案11-23
《貨幣銀行學》復習試題及答案11-22
《建筑材料》期末復習試題及答案11-22