《圖論》期末考試模擬題（答案）

相關推薦

《圖論》期末考試模擬題（答案）

　　一、選擇題

《圖論》期末考試模擬題（答案）

　　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 分）