《圖論》期末考試模擬題（答案）
一、選擇題
1、給定無向圖如圖所示，下面給出的頂點集子集中，是點割集的為（A,B,C,D）。
A. {b, d}
B. {d}
C. {a, c}
D. {g, e} bf
內容需要下載文檔才能查看
2、設V＝{a,b,c,d},與V能構成強連通圖的邊集E＝（ A ）。
A. {,,,,}
B. {,,,,}
C. {,,,,}
{,,,,}
3、一個連通的無向圖G，如果它的所有結點的度數都是偶數，那麼它具有一條（ B ）。
A. 哈密爾頓迴路
B. 歐拉回路
C. 哈密爾頓通路
D. 歐拉通路
4、如圖所示各圖，其中存在哈密頓迴路的圖是（ A, C ）。
內容需要下載文檔才能查看
第 1 頁 共 5 頁
圖論期末考試題目參考
《圖論》
5. 下圖中既是歐拉圖，又是哈密爾頓圖的有（D）。
5、設G是有5個頂點的完全圖，則G（ B ）。
D. 無哈密爾頓路
E. 可以一筆畫出
F. 不能一筆畫出
G. 是平面圖
6、設G是連通簡單平面圖，G中有11個頂點5個面，則G中的邊是（ D ）。
A. 10
B. 12
C. 16
D. 14
二、填空題
1、完全圖K8具有（ 28 ）條邊。
2、圖G如圖所示， ab
fc 那麼圖G的割點是（ a, f ）。
e d
3、無向圖G為歐拉圖，當且僅當G是連通的，且G中無（ 奇數度 ）結點。
第 2 頁 共 5 頁
圖論期末考試題目參考
《圖論》
4、連通有向圖D含有歐拉回路的充分必要條件是（ D中每個結點的入度＝出度 ）。
5、 n個結點、m條邊的無向連通圖是樹當且僅當m=__（3）___。
(1) n+1 (2) n (3) n-1 (4)2n-1
三、
1、設圖G=(P,E) 中有12條邊，6個度數為3的頂點，其餘頂點的度數均小於3，求G至少有多少個頂點。
解答：設G有n個頂點，由定理1，
∑d
i=1nG(vi)=2m=24 (|E|=m)
由題設 24<3×6+3(n?6)
∴ 3n>24
即 n>8
因此，G中至少有9個頂點。
2、一次學術會議的理事會共有20個人參加，他們之間有的相互認識但有的相互不認識。但對任意兩個人，他們各自認識的人的數目之和不小於20。問能否把這20個人排在圓桌旁，使得任意一個人認識其旁邊的兩個人?根據是什麼? 解答：可以把這20個人排在圓桌旁，使得任一人認識其旁邊的兩個人。 根據：構造無向簡單圖G=,其中V={v1,v2,…，V20}是以20個人為頂點的集合，E中的邊是若任兩個人vi和vj相互認識則在vi與vj之間連一條邊。 ?Vi∈V,d(vi)是與vi相互認識的人的數目，由題意知?vi,vj∈V有d(vi)+d(vj)≥20,於是G中存在哈密爾頓迴路。
設C=Vi1Vi2…Vi20Vi1是G中一條哈密爾頓迴路，按這條迴路的順序按其排座位即符合要求。
3、已知帶權圖G，如圖所示。試求圖G的最小生成樹，並計算該生成樹的權。
第 3 頁 共 5 頁
圖論期末考試題目參考
《圖論》
解答：做法如下：
①選邊1； ②選邊2；
③選邊3； ④選邊5； ⑤選邊7 最小生成樹為{1,2,3,5,7}。如圖中粗線所示。
權數為18。
四、證明題
1、設G為9個結點的無向圖，每個結點的`度數不是5就是6，試證明G中至少有5個度數為6的結點，或者至少有6個度數為5的結點。
證明：由握手定理的推論，G中度數為5的結點個數只能是0,2,4,6,8五種情況； 此時，相應的結點度數為6的結點個數分別為9，7，5，3，1個，以上五種對應情況(0,9),(2,7),(4,5),(6,3),(8,1)，每對情況，兩數之和為9，且滿足第2個數大於或等於5，或者第1個數大於或等於6，意即滿足至少有度數為6的結點5個，或者至少有度數為5的結點6個。
2、彼得森圖G如圖8.23所示。
(1)求：α(G),β(G),γ(G).
(2)證明：(2.1)χ(G)=3,
內容需要下載文檔才能查看
(2.2)它不是二分圖，也不是歐拉圖，更不是平面圖。
解 因為彼得森圖中有長度為奇數的圈，根據定理8.1可知它不是二部圖。圖中每個頂點的度數均為3，由定理8.4可知它不是歐拉圖。又因為它可以收縮成由庫拉圖斯基定理可知它也不是平面圖。 第 4 頁 共 5 頁 ，
圖論期末考試題目參考
《圖論》
3．證明或推翻下列命題：“設連通簡單平面圖G 的最小度δ(G)≥4，則G 的點色數χ(G)≥3.”
解答與評分標準：
假設χ(G)<3.（反證法分情況討論2 分）
χ(G)=1 當且僅當G 為n 階零圖，與已知矛盾。（4 分）
χ(G)=2 當且僅當G 為二分圖，因為G 為平面圖，只能為K2,s 或Kr,2（有問題）. 此時
必有δ(G)=2, 與已知矛盾。（4 分）
