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

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦圖論試卷A卷-14數(shù)本**學院2022—2022學年其次學期期末考試2022級本科數(shù)學與應用數(shù)學專業(yè)《圖論》試卷A

（本試卷滿分100分，考試時光110分鐘）

一、填空題（每小題2分，共20分）

1.圖G的兩個子圖G1，G2的環(huán)和表示為_______．

2.圖G中的一圈，若它通過G中的每一條邊(或弧)恰好一次，則稱該圈為____．

3.圖G的兩個不同的生成的樹T1，T2的頂點個數(shù)_______．（填相同或不相同）4．“3,3

K是歐拉圖也是哈密頓圖”這句話是_______。(填對或錯)

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-著色的最小數(shù)值即為G的_________．

10.極大可平面圖的每一個面的次數(shù)都是_________．

二、推斷題（每小題1分，共10分）

1.同構(gòu)的圖保持鄰接關(guān)系．

2.最小生成樹即G的全部生成樹中權(quán)值最小的生成樹．

K是歐拉圖．

3.

5

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.完善匹配必然是最大匹配，但反之不然．

K的子圖．

10．一個圖是平面圖當且僅當它沒有收縮到K5或

3,3

三、單項挑選題（每小題2分，共20分）

1.一個圖的全部頂點的度數(shù)之和不行能是()

A.5

B.6

C.8

D.10

2.假如連通圖G的頂點個數(shù)為8，則其生成樹中邊的個數(shù)為()

A.7

B.6

C.9

D.8

3.在如下各圖中（）歐拉圖。

4．如下右圖所示，以下說法正確的是()．

A．{a,e}是點割集

B．e是割點

C．{b,e}是點割集

D．hn13ftv是點割集

5.假如連通圖G的頂點個數(shù)為7，邊數(shù)為8，則其向量空間的維數(shù)為()

A.9

B.8

C.7

D.1

6．設(shè)無向圖G的鄰接矩陣為

????????????????010*******

000011100100110，則G的邊數(shù)為()．

A．3

B．4

C．5

D．6

7.假如連通圖G的點連通度為2，邊連通度為3，圖的最小頂點的度數(shù)可能為（）

A.0

B.1

C.3D．2

8.G的一個匹配M中的頂點（）M飽和頂點

A.都不是

B.惟獨一個是

C.有些是，有些不是

D.所有是

9.假如連通圖G的最大頂點的度數(shù)3，則圖G的色數(shù)不行能是（）

A.2

B.3

C.4

D.5

10.假如一個圖含同胚于（）的子圖，它可能是可平面圖

A.5K

B.3,3K

C.5階徹低圖

D.3K

四、解答題（每小題10分，共40分）

1.下圖中各圖是否可以一筆畫出？請寫明理由。（10分）

2.求下圖的徹低關(guān)聯(lián)矩陣并以v1為參考點寫出關(guān)聯(lián)矩陣和一個可逆大子陣（10分）

3．請回答一下問題：（1）試說明下圖是否為正則圖？請畫出該圖的一顆生成樹；（2）簡述四色定理，畫出下圖的一種頂點著色計劃。4

e2e5e3

v2v3

4e1v1

4.5項工作預備分給5個人去做，如圖，其中邊（fi,mj)表示fi可以從事mj，假如每個人最多從事其中一項，且每項工作只能由一人擔任．問怎樣才干使盡可能多的人安派上任務？（10分）

五、證實題（10分）

證實：(平面圖歐拉公式)設(shè)G為p階q條邊f(xié)個面的連通平面圖，則pq+f=2.

f1f2m1f3f4f5

m2m3m4m5

**學院2022—2022學年其次學期期末考試

2022級本科數(shù)學與應用數(shù)學專業(yè)《圖論》

參考答案與評分標準A

命題老師：***

二、填空題

參考答案：

1，12GG⊕；2，鏈；3,相同；4，錯；5,環(huán)合；6,1qp-+；7，使得連通圖G變?yōu)椴贿B通的邊割集的最小邊數(shù)；8，完善匹配；9，色數(shù)；10,3

評分標準：

本部分每小題2分。凡與答案全都的得2分，不全都（含空白）的不得分。

三、推斷題

參考答案：

1-5√√√××6-10.××√√√

評分標準：

本部分每小題1分。凡與答案全都的得1分，不全都（含未作推斷）的不得分。

三、單項挑選題

參考答案：1-5AABBB6-10CCDDD

評分標準：

本部分每小題2分。凡與答案全都的得2分，不全都（含未選）的不得分。

四、解答題

參考答案：

1.解：一個圖是“一筆畫”當且僅當奇數(shù)度頂點的個數(shù)是0或2個，因此（2）

（3）（4）是“一筆

畫”?！?0分）

2.解：

………………

………（10分）本題答案不唯一，答對即可。

3.解：（1）不是為正則圖，由于各個頂點的度數(shù)不徹低相同。該圖的生成樹不唯一，只要是該圖的子圖當中含七條邊的樹即可?！?0分）

（2）四色定理即在一張地圖中，給地圖的各地域著色，要使鄰接的地域具有不同的色彩，四種色彩足夠，該圖的色數(shù)為3，頂點著色計劃不唯一，符合題意即可?！?0分）

4.解：這個問題即為：二部圖12,,GVVE=是否存在1V―完善匹配。如圖所示，實線表示的即為一種分配計劃…（10分）

評分標準：

f1f2m1f3f4f5

m2m3m4m

5??????????????????????1100001101001101100110011徹低關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣(v為參考點)1001111000→01101一個可逆的大子1陣0010123eee

本部分每小題10分，考生每解出一個步驟，得相應的分數(shù)。因為某一步單純計算錯誤而導致其后數(shù)據(jù)錯誤，但辦法正確的，可以在不超過該部分應得分一半的范圍內(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-