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

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

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

3、三、單項(xiàng)選擇題（每小題2分，共20分）1. 一個(gè)圖的所有頂點(diǎn)的度數(shù)之和不可能是（）A. 5B. 6C. 8 D. 102 .如果連通圖G的頂點(diǎn)個(gè)數(shù)為8,則其生成樹(shù)中邊的個(gè)數(shù)為（）A. 7B. 6C. 9 D. 83 .在如下各圖中（）歐拉圖。4 .如下右圖所示，以下說(shuō)法正確的是 （）.A. a, e是點(diǎn)割集B. e aeb割點(diǎn)C. b, e是點(diǎn)割集D. d是點(diǎn)割集5 .如果連通圖G的頂點(diǎn)個(gè)數(shù)為7,邊數(shù)為8,則其向量空間的維數(shù)為（）A. 9 B. 8 C. 7 D. 16 .設(shè)無(wú)向圖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的一個(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. K5B. K3,3 C. 5 階完全圖D. K3四、解答題（每小題10分，共40分）1 .下圖中各圖是否可以一筆畫(huà)出請(qǐng)寫(xiě)明理由。（10分）10分）2 .求下圖的完全關(guān)聯(lián)矩陣并以v1為參考點(diǎn)寫(xiě)出關(guān)聯(lián)矩陣

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

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

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