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

1、*學(xué)院 20162017學(xué)年第二學(xué)期期末考試2014級本科數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)圖論試卷 A（本試卷滿分100分，考試時間110分鐘）一、填空題（每小題2分，共20分）1 .圖G的兩個子圖G1, G2的環(huán)和表示為.2 .圖G中的一圈，若它通過G中的每一條邊（或弧）恰好一次，則稱該圈為 .3 .圖G的兩個不同的生成的樹干, T2的頂點(diǎn)個數(shù).（填相同或不相同）4 . K3,3是歐拉圖也是哈密頓圖”這句話是。（填對或錯）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的每一個頂點(diǎn)都是M-飽和點(diǎn)，則M

2、為.9 .使圖G為n-著色的最小數(shù)值即為G的.10 .極大可平面圖的每一個面的次數(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 .一個非完全連通圖的連通度就是使這個圖成為非連通圖所需要去掉的最小頂點(diǎn)數(shù).9 .完美匹配必定是最大匹配，但反之不然.10 . 一個圖是平面圖當(dāng)且僅當(dāng)它沒有收縮到 K5或K3,3的子圖.

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

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

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

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

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