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

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

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

3、B. 6 C. 8 D. 102. 如果連通圖G的頂點個數(shù)為8，則其生成樹中邊的個數(shù)為( )A. 7 B. 6 C. 9 D. 83. 在如下各圖中（ ）歐拉圖。4如下右圖所示，以下說法正確的是 ( )Aa, e是點割集 Be是割點 Cb, e是點割集 Dd是點割集5. 如果連通圖G的頂點個數(shù)為7，邊數(shù)為8，則其向量空間的維數(shù)為( )A. 9 B. 8 C. 7 D. 16設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( ) A3 B4 C5 D67.如果連通圖G的點連通度為2，邊連通度為3，圖的最小頂點的度數(shù)可能為（ ）A. 0 B. 1 C. 3 D28.G的一個匹配M中的頂點（ ）M飽和頂點A.

4、都不是 B. 只有一個是 C. 有些是，有些不是 D.全部是9.如果連通圖G的最大頂點的度數(shù)3，則圖G的色數(shù)不可能是（ ）A.2 B. 3 C. 4 D. 510.如果一個圖含同胚于（ ）的子圖，它可能是可平面圖A. B. C. 5階完全圖 D. 四、解答題（每小題10分，共40分）1.下圖中各圖是否可以一筆畫出？請寫明理由。（10分）2. 求下圖的完全關(guān)聯(lián)矩陣并以v1為參考點寫出關(guān)聯(lián)矩陣和一個可逆大子陣（10分）v4e2e5e3v2v3e4e1v13請回答一下問題：（1）試說明下圖是否為正則圖？請畫出該圖的一顆生成樹；（2）簡述四色定理，畫出下圖的一種頂點著色方案。4.5項工作準備分給5個人

5、去做，如圖，其中邊（fi,mj)表示fi可以從事mj ，如果每個人最多從事其中一項，且每項工作只能由一人擔任問怎樣才能使盡可能多的人安派上任務(wù)？（10分）f1f2m1f3f4f5m2m3m4m5五、證明題（10分）證明：(平面圖歐拉公式) 設(shè)G為p階q條邊f(xié)個面的連通平面圖，則 p-q+f=2. *學院20162017學年第二學期期末考試2014級本科數(shù)學與應(yīng)用數(shù)學專業(yè)圖論參考答案與評分標準A命題教師：*二、 填空題 參考答案：1，；2，鏈；3, 相同；4，錯；5, 環(huán)合；6, ；7，使得連通圖G變?yōu)椴贿B通的邊割集的最小邊數(shù)；8，完美匹配；9，色數(shù)；10,3評分標準：本部分每小題2分。凡與答案

6、一致的得2分，不一致（含空白）的不得分。三、 判斷題參考答案：1-5 ×× 6-10. ××評分標準：本部分每小題1分。凡與答案一致的得1分，不一致（含未作判斷）的不得分。三、單項選擇題參考答案：1-5 AABBB 6-10 CCDDD評分標準：本部分每小題2分。凡與答案一致的得2分，不一致（含未選）的不得分。四、 解答題參考答案：1. 解：一個圖是“一筆畫”當且僅當奇數(shù)度頂點的個數(shù)是0或2個，因此（2）（3）（4）是“一筆畫”。 （10分）2. 解：（10分）本題答案不唯一，答對即可。 3. 解：（1）不是為正則圖，因為各個頂點的度數(shù)不完全相同。該圖的

7、生成樹不唯一，只要是該圖的子圖當中含七條邊的樹即可。 （10分）（2）四色定理即在一張地圖中，給地圖的各地域著色，要使鄰接的地域具有不同的顏色，四種顏色足夠，該圖的色數(shù)為3，頂點著色方案不唯一，符合題意即可。 （10分）4. 解：這個問題即為：二部圖是否存在完美匹配。如圖所示，實線表示的即為一種分配方案 （10分）f1f2m1f3f4f5m2m3m4m5評分標準：本部分每小題10分，考生每解出一個步驟，得相應(yīng)的分數(shù)。由于某一步單純計算錯誤而導(dǎo)致其后數(shù)據(jù)錯誤，但方法正確的，可以在不超過該部分應(yīng)得分一半的范圍內(nèi)給分。五、 證明題參考答案：證明：（1）若G中無圈, 則G為無圈連通圖，是一顆樹，必有一個度數(shù)為1的頂點v, 刪除v及與它關(guān)聯(lián)的邊, 記作G ¢. G ¢連通無圈, 有p-1個頂點, 條邊和f個面. 由歸納假設(shè), (p-1)-（q-1）+f=2, 即p-q+f=2, 得證q=k+1時結(jié)論成立. （5分） (2) 若G中有圈,則刪去一個圈上的一條邊,記作G ¢. G ¢連通, 有p個頂點,q-1條邊和f-1個面. 由歸納假設(shè), p- （q-1）+（f-1）=2