題號(hào)

答案

知識(shí)點(diǎn)與備注

填空題

1

8

凱萊遞推計(jì)數(shù)法/ 矩陣樹(shù)定理

2

n1m2+n2m1

積圖的定義

3

23

最小生成樹(shù)算法

4

8

最短路算法

5

?(n^2)/4?

托蘭定理，小于等于T2,n的邊數(shù)，即n階完全2等部圖。

選擇題

1

B

A 錯(cuò)誤，無(wú)法找到H圈(分兩種情況討論)

B 正確 去掉一個(gè)點(diǎn)(有兩種不同情況)后有H圈

C 錯(cuò)誤 彼得森圖去掉一個(gè)一因子后剩下兩個(gè)不相交的K5，故無(wú)一因子分解。

D 錯(cuò)誤， 它可以收縮到K5，故不可平面

2

C

A 錯(cuò)誤 有割點(diǎn)/有割邊 的3正則圖都有可能出現(xiàn)

B 錯(cuò)誤 同上

C 正確！去掉H圈后1個(gè)因子；H圈又能分解成2個(gè)1因子，故總共可以分解成3個(gè)一因子

D 錯(cuò)誤！ 如K4

3

B

A: 錯(cuò)誤，如C8在v1，v3 或 v1， v4連線形成的兩個(gè)圖不同構(gòu)。

B 正確，度弱的定義！

C 錯(cuò)誤，只是度序列，不一定是圖序列

D 錯(cuò)誤，不一定如(1,3,6)和(2,2,2)

4

A

A 錯(cuò)誤，如K6

B 正確， 對(duì)任意兩點(diǎn)分請(qǐng)開(kāi)給你討論可證明

C 正確 點(diǎn)獨(dú)立集的補(bǔ)圖導(dǎo)出的子圖一定是完全圖，也就是團(tuán)

D 正確，只要n(n-1)/4是整數(shù)。如C5

5

D

A: 顯然錯(cuò)誤，倒過(guò)來(lái)游

B 錯(cuò)誤 還要連通！

C 錯(cuò)誤，可以有自環(huán)！也可以是8字型閉跡。

D 正確！因?yàn)檫吋梢苑纸鉃槿Φ牟?#xff0c;所以沒(méi)有割邊。

大題

三

握手定理

5度頂點(diǎn)有7個(gè)

四

(1) 證明

k正則偶圖有完美匹配M，減去M后仍為K-1正則偶圖。依次類(lèi)推，可分解為n個(gè)邊不重的1因子之并，即1因子分解。

(2) 證明

設(shè)割邊e={uv}

G-e后取分支G1，G1仍為偶圖，不妨設(shè)u在X中，則X的總度數(shù)為nk-1; Y的總度數(shù)為mk

則nk-1=mk.因?yàn)閗大于等于2，故等式不成立，故無(wú)解，矛盾！

所以不存在割邊。

五

握手定理

樹(shù)的點(diǎn)數(shù)=邊數(shù)+1

聯(lián)立即可得證

六

(1) Cm,n=KmV(Km補(bǔ)圖+K(n-2m))

即可畫(huà)出C1，5和C2,5

(2)

取S={Km中的m個(gè)頂點(diǎn)}

則w(G-S)=m+n-2m=n-m>m

故由H圖判定的必要條件可知，不是H圖

七

2007年以來(lái)期末考試第一道最優(yōu)匹配的題！

Step1：頂點(diǎn)標(biāo)號(hào)：{15,11,16,13；0,0,0,0}

M={v1u3,v4u2}

Step2: 頂點(diǎn)標(biāo)號(hào)：{14,10,15,12;0,1,1,0}

即可找到完美匹配M={v1u4,v2u2,v3u3,v4u1}

最優(yōu)權(quán)重是53

八

設(shè)五邊形有x個(gè)，六邊形有y個(gè)，則

面的次數(shù)公式 2m =5x+6y

握手定理 2m=3n

歐拉公式n-m+x+y=2

?

聯(lián)立可解得x=12

九

點(diǎn)染色問(wèn)題。

存在奇圈: ahdbc，故點(diǎn)色數(shù)>=3;

又因?yàn)閑與所有奇圈中所有點(diǎn)都相連，故點(diǎn)色數(shù)>=4

可以找到，因此點(diǎn)色數(shù)為4

最少需要四個(gè)倉(cāng)庫(kù)

分組略