5**學(xué)院2016學(xué)年第二學(xué)期期末考試52014級本科數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)《圖論》試卷A一、填空題（每小題2分，共20分）1.圖的兩個子圖GG的環(huán)和表示為12.圖中的一圈它通過中的每一條邊(弧恰好一次稱該圈為___．3.圖的兩個不同的生成的樹TT的頂點個數(shù)_______相同或不相同）124．K是歐拉圖也是哈密頓圖”這句話是______。填對或錯)5.圖的任意頂點的關(guān)聯(lián)集都等于其余各頂點關(guān)聯(lián)集的_．6.(p,q)圖G基本圈有________個．7.連通圖的邊連通度定義為．8.設(shè)M是G一個匹配G的每一個頂點都是M-飽和點為_9.使圖為n-著色的最小數(shù)值即為的_________10.極大可平面圖的每一個面的次數(shù)都是_________．二、判斷題（每小題1分，共10分）1.同構(gòu)的圖保持鄰接關(guān)系．2.最小生成樹即的所有生成樹中權(quán)值最小的生成樹．3.K是歐拉圖．54.設(shè)是無向連通圖，則G是一筆畫

中沒有奇數(shù)度頂點．5.圖的秩等于圖的完全關(guān)聯(lián)矩陣的秩，而不等于其關(guān)聯(lián)矩陣的秩．6.圖的關(guān)聯(lián)矩陣是對稱矩陣．7.圖的邊連通度大于最小頂點的度數(shù)．8.一個非完全連通圖的連通度就是使這個圖成為非連通圖所需要去掉的最小頂點數(shù)．9.完美匹配必定是最大匹配，但反之不然．10一個圖是平面圖當(dāng)且僅當(dāng)它沒有收縮到K三、單項選擇題（每小題2分，共20分）第頁共頁

的子圖．3,3

1.一個圖的所有頂點的度數(shù)之和不可能是()B.6C.8D.2.如果連通圖G頂點個數(shù)為8，則其生成樹中邊的個數(shù)為()B.6C.9D.83.在如下各圖中（）歐拉圖。4．如下右圖所示，以下說法正確的是()．A．{a,e}是點割集

B．是點．{,e}是點割集D．{}點割集5.如果連通圖G頂點個數(shù)為7，邊數(shù)為8則其向量空間的維數(shù)為()B.8C.7D.16．設(shè)無向G鄰接矩陣為

01100

1001001011

，則的邊數(shù)為()．A．3B4．5D．67.如果連通圖的點連通度為2，邊連通度3，圖的最小頂點的度數(shù)可能為（）0B.1C.3D．8.的一個匹配M中的頂點（）M飽和頂點第頁共頁

都不是

B.只有一個是

C.有些是，有些不是

D.部是9.如果連通圖的最大頂點的度數(shù)3，則圖G的色數(shù)不可能是（）A.2B.3C.4D.510.如果一個圖含同胚于（）的子圖，它可能是可平面圖

B.K

3,3

C.5階完全圖

D.K

四、解答題（每小題10分，共40分）1.下圖中各圖是否可以一筆畫出？請寫明理由。（分）2.求下圖的完全關(guān)聯(lián)矩陣并以1（10分）

為參考點寫出關(guān)聯(lián)矩陣和一個可逆大子陣v2

e

2

v3e

1

e

5

e

3v1

e

4

v43．請回答一下問題）試說明下圖是否為正則圖？請畫出該圖的一顆生成樹）簡述四色定理，畫出下圖的一種頂點著色方案。第頁共頁

j112345j1123454.5項工作準(zhǔn)備分給5個人去做，如圖，其中邊f(xié),m)表示f可以從事，iji如果每個人最多從事其中一項且每項工作只能由一人擔(dān)任怎樣才能使盡可能多的人安派上任務(wù)？（10分）

f

2

f

3

4

f

5m

m

m

m

m五、證明題（10分）證明面圖歐拉公式)

為p階q條f面的連通平面圖pqf=2.第頁共頁

**學(xué)院2016—學(xué)年第二學(xué)期期末考試2014級本科數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)《圖論》參考答案與評分標(biāo)準(zhǔn)A命題教師：二、填空題參考答案：1GG；2，鏈；相同；，錯；5,環(huán)合；6,p1；，使得連通2圖G變?yōu)椴贿B通的邊割集的最小邊數(shù)；，完美匹配；9，色數(shù)；10,3評分標(biāo)準(zhǔn)：本部分每小題2分凡與答案一致的得2分不一（含空白的不得分。三、判斷題參考答案：1-5√√√××6-10.××√√√評分標(biāo)準(zhǔn)：本部分每小題1分。凡與答案一致的得1分，不一致（含未作判斷）的不得分。三、單項選擇題參考答案：1-5評分標(biāo)準(zhǔn)：

AABBB6-10CCDDD本部分每小題2分凡與答案一致的得2分不一（含未選的不得分。四、解答題參考答案：第頁共頁

1100010000111123451.解一個圖“一筆畫110001000011112345畫”。分）2.解：

………（10完全關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣(點10010→001一個可逆的大子ee123………（10

………………本題答案不唯一，答對即可。3.解）不是為正則圖，因為各個頂點的度數(shù)不完全相同。該圖的生成樹不唯一，只要是該圖的子圖當(dāng)中含七條邊的樹即可?！ǚ郑?）四色定理即在一張地圖中，給地圖的各地域著色，要使鄰接的地域具有不同的顏色，四種顏色足夠，該圖的色數(shù)3，頂點著色方案不唯一，符合題意即可?！?0分）4.解：這個問題即為：二部圖GVE是否存V―完美匹配。如圖所1示，

實

線

表

示

的

即

為

一

種

分

配

方案

…（10分）

f

2

f

3

4

f

5m

m

m

m

m評分標(biāo)準(zhǔn)：第頁共頁

本部分每小題10分，考生每解出一個步驟，得相應(yīng)的分?jǐn)?shù)。由于某一步單純計算錯誤而導(dǎo)致其后數(shù)據(jù)錯誤但方法正確的可以在不超過該部分應(yīng)得分一半的范圍內(nèi)給分。五、證明題參考答案：證明1）若G中無圈則為無圈連通圖，是一顆樹，必有一個度數(shù)為1的頂點v,刪除v與它關(guān)聯(lián)的邊,記作G圈,有p-1個頂點,條邊和f個面由歸納假設(shè)p（）+f即

pqf=2,

得

證

q=k

時

結(jié)

論

成立.

………………（分）(2)中有圈則刪去一個圈上的一條邊記Gp個點,1條邊和f-個面由歸