圖論試卷A卷-14數(shù)本

1、*學(xué)院2016 2017學(xué)年第二學(xué)期期末考試2014級本科數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)圖論試卷（本試卷滿分100分，考試時(shí)間110分鐘）一、填空題（每小題2分，共20分）1. 圖G的兩個(gè)子圖G1，G2的環(huán)和表示為.2圖G中的一圈，若它通過G中的每一條邊（或?。┣『靡淮?，則稱該圈為3. 圖G的兩個(gè)不同的生成的樹T1, T2的頂點(diǎn)個(gè)數(shù).（填相同或不相同）4. K3,3是歐拉圖也是哈密頓圖”這句話是 。（填對或錯(cuò)）5. 圖G的任意頂點(diǎn)的關(guān)聯(lián)集都等于其余各頂點(diǎn)關(guān)聯(lián)集的 .6. （p,q）圖G的基本圈有 .7. 連通圖G的邊連通度定義為 .8. 設(shè)M是G的一個(gè)匹配，如果G的每一個(gè)頂點(diǎn)都是M-飽和點(diǎn)，則M為9. 使

2、圖G為n-著色的最小數(shù)值即為G的.10. 極大可平面圖的每一個(gè)面的次數(shù)都是.二、判斷題（每小題1分，共10分）1. 同構(gòu)的圖保持鄰接關(guān)系.2. 最小生成樹即G的所有生成樹中權(quán)值最小的生成樹.3. K5是歐拉圖.4. 設(shè)G是無向連通圖，則G是一筆畫 G中沒有奇數(shù)度頂點(diǎn).5. 圖的秩等于圖的完全關(guān)聯(lián)矩陣的秩，而不等于其關(guān)聯(lián)矩陣的秩.6. 圖的關(guān)聯(lián)矩陣是對稱矩陣.7. 圖的邊連通度大于最小頂點(diǎn)的度數(shù).8. 一個(gè)非完全連通圖的連通度就是使這個(gè)圖成為非連通圖所需要去掉的最小頂點(diǎn)數(shù).9. 完美匹配必定是最大匹配，但反之不然.10. 一個(gè)圖是平面圖當(dāng)且僅當(dāng)它沒有收縮到 K5或K3,3的子圖.三、單項(xiàng)選擇題（

3、每小題2分，共20分）1. 一個(gè)圖的所有頂點(diǎn)的度數(shù)之和不可能是（）A.5B. 6C. 8D. 102. 如果連通圖G的頂點(diǎn)個(gè)數(shù)為8,則其生成樹中邊的個(gè)數(shù)為（）A.7B. 6C. 9D.83. 在如下各圖中（）歐拉圖。第5頁共7頁4如下右圖所示，以下說法正確的是（）.A . a,e是點(diǎn)割集B. e是割點(diǎn)C. b, e是點(diǎn)割集D. d是點(diǎn)割集5.如果連通圖G的頂點(diǎn)個(gè)數(shù)為7,邊數(shù)為8,則其向量空間的維數(shù)為（）A. 9B.8C. 7D.16設(shè)無向圖G的鄰接:矩陣為0 11001 00111 0000 ,0 10010 1010則G的邊數(shù)為（）.A . 3B . 4C .5D. 67. 如果連通圖G的點(diǎn)

4、連通度為2,邊連通度為3,圖的最小頂點(diǎn)的度數(shù)可能為（）A. 0 B. 1 C. 3 D. 28. G的一個(gè)匹配M中的頂點(diǎn)（）M飽和頂點(diǎn)A.都不是 B.只有一個(gè)是C.有些是，有些不是D.全部是9. 如果連通圖G的最大頂點(diǎn)的度數(shù)3,則圖G的色數(shù)不可能是（）A.2 B. 3 C. 4 D. 510. 如果一個(gè)圖含同胚于（）的子圖，它可能是可平面圖A. KsB. K3,3C. 5 階完全圖D. K3四、解答題（每小題10分，共40分）1.下圖中各圖是否可以一筆畫出？請寫明理由。（10分）(1) 2. 求下圖的完全關(guān)聯(lián)矩陣并以 v1為參考點(diǎn)寫出關(guān)聯(lián)矩陣和一個(gè)可逆大子陣(10 分)3請回答一下問題：（1）

5、試說明下圖是否為正則圖？請畫出該圖的一顆生成樹；（2）簡述四色定理，畫出下圖的一種頂點(diǎn)著色方案。El4.5項(xiàng)工作準(zhǔn)備分給5個(gè)人去做，如圖，其中邊（fi,mj）表示fi可以從事mj , 如果每個(gè)人最多從事其中一項(xiàng)，且每項(xiàng)工作只能由一人擔(dān)任.問怎樣才能使盡可能多的人安派上任務(wù)？ （ 10分）（10 分）五、證明題證明：平面圖歐拉公式）設(shè)G為p階q條邊f(xié)個(gè)面的連通平面圖，貝U p q+f=2.* 學(xué)院 20162017 學(xué)年第二學(xué)期期末考試2014 級本科數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)圖論 參考答案與評分標(biāo)準(zhǔn) A 命題教師： *二、填空題參考答案：1， G1 G2 ；2，鏈； 3, 相同； 4，錯(cuò)； 5, 環(huán)合

6、；6, q p 1 ；7，使得連通 圖 G 變?yōu)椴贿B通的邊割集的最小邊數(shù)； 8 ，完美匹配； 9 ，色數(shù)； 10,3評分標(biāo)準(zhǔn)：本部分每小題 2 分。凡與答案一致的得 2 分，不一致（含空白）的不得分三、判斷題 參考答案：1-5WVxx6-10. xxWV評分標(biāo)準(zhǔn)： 本部分每小題 1 分。凡與答案一致的得 1 分，不一致（含未作判斷）的不 得分。三、單項(xiàng)選擇題 參考答案： 1-5 AABBB 6-10 CCDDD評分標(biāo)準(zhǔn)：本部分每小題 2 分。凡與答案一致的得 2 分，不一致（含未選）的不得分四、解答題參考答案：1.解：一個(gè)圖是“一筆畫”當(dāng)且僅當(dāng)奇數(shù)度頂點(diǎn)的個(gè)數(shù)是 0或2個(gè)，因此（2）（3）（

7、4）是“一筆畫”。 （10分）2.解：完全關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣（V1為參考點(diǎn)）100111100011000T 01101011010011000110一個(gè)可逆的大子陣ei e2 31 1 00 i i（W 分）1本題答案不唯一，答對即可。3. 解：（1）不是為正則圖，因?yàn)楦鱾€(gè)頂點(diǎn)的度數(shù)不完全相同。該圖的生成樹不唯一，只要是該圖的子圖當(dāng)中含七條邊的樹即 可。（10分）（2）四色定理即在一張地圖中，給地圖的各地域著色，要使鄰接的地域具有 不同的顏色，四種顏色足夠，該圖的色數(shù)為 3，頂點(diǎn)著色方案不唯一，符合題意即可。（10分）4解：這個(gè)問題即為：二部圖 G ：V1,V2，E是否存在V 完美匹配。如圖所

8、 示， 實(shí)線 表示 的 即 為一種 分配方 案（10分）f1f2f3f4f5m1m2m3m4m5f1f2f3f4f5評分標(biāo)準(zhǔn):本部分每小題10分，考生每解出一個(gè)步驟，得相應(yīng)的分?jǐn)?shù)。由于某一步單純計(jì)算錯(cuò)誤而導(dǎo)致其后數(shù)據(jù)錯(cuò)誤，但方法正確的，可以在不超過該部分應(yīng)得 分一半的范圍內(nèi)給分 五、證明題 參考答案: 證明：(1)若G中無圈，則G為無圈連通圖，是一顆樹，必有一個(gè)度數(shù)為 1 的頂點(diǎn)v,刪除v及與它關(guān)聯(lián)的邊，記作G . G連通無圈,有p-1個(gè)頂點(diǎn),條邊 和f個(gè)面.由歸納假設(shè)，(p-1)- (q-1) +f=2,即 p-q+f=2, 得 證 q=k+1 時(shí) 結(jié) 論 成 立. (5 分) 若G中有圈，則刪去一個(gè)圈上的一條邊，記作G . G連通，有p個(gè)頂點(diǎn),q-1 條邊和f-1個(gè)面.由歸納假設(shè)，p- (