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