一、選擇題
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 分)