題號

答案

知識點與備注

填空題

1

11

最短路算法

2

30

鄰接矩陣的性質

求平方+求合即可

按照老師的觀點，本答案認為 vi出發到vj的途徑和vj出發到vi的途徑是兩條不同的途徑。

3

34

最小生成樹算法

4

38

兩個奇數度點的歐拉環游

最短路算法

5

62

最優二元樹權值：

哈夫曼編碼+ Σ權值*層數

選擇題

1

C

?

A:錯誤！和應為偶數

B 錯誤 只是度序列，不一定是圖序列

C 正確 由度弱的定義可以證明

D 錯誤！不一定如(1,3,6)和(2,2,2)

2

D

A：錯誤 如K2

B 錯誤，如自環或8字形閉跡

C 錯誤，如K2

D 正確！邊 e是圖G的割邊當且僅當e 不在G的任何圈中。用反證法證明：

可以假設G連通。

“必要性”：若不然。設 e 在圖G的某圈C 中，且令e = u v.考慮P= C- e,則P是一條u v路。下面證明G-e連通。對任意 x,y ? ? ∈V(G-e) ，由于G連通，所以存在x ---y路Q.若Q不含e，則x與y在G-e里連通；若Q含有e，則可選擇路：x ---u P v --- y,說明x與y在G-e里也連通。所以,若邊e在G的某圈中，則G-e連通。但這與e是G的割邊矛盾！

“充分性” ? ?如果e不是G的割邊，則G-e連通，于是在G-e中存在一條u --- v 路，顯然：該路并上邊e得到G中一個包含邊e的圈，矛盾。

3

D

A: 正確，如彼得森圖

B 正確 如兩個K6，一個頂點重合的情況，點連通度1，邊連通度4，最小度5

C 正確。設G是n階簡單圖，若δ(G)≥ [n/2], 則G必連通。且λ(G) =δ(G) ? 首先證G連通： [反證法]若G 不連通，則G至少有兩個連通分支，從而必有一個分支H 滿足 |V(H)|≤[n/2]

因G是簡單圖，從而Δ(H)<n/2

于是δ(G)≤δ(H)≤Δ(H)<[n/2]. 這與已知矛盾，所以G必連通。

再證λ(G) =δ(G)?

非常麻煩，不證了，考到認栽。

D 錯誤。連通度至少為k

4

B

A正確 找不到H圈

B 錯誤 閉包只能推出來是H圖

C 正確 為了閉包的加邊并不改變原圖的H性，因此G是H圖當且僅當閉包是H圖

D 正確。1必要4充分1充要中的充分條件。

5

A

A: 錯誤 無割邊的三正則圖一定有完美匹配，但反之不一定成立

B 正確 彼得森定理

C 正確 去掉H圖后是一個1因子；H圖是2個1因子，因此可以分解為3個一因子。

D 正確 顯然

大題

三

握手定理，度至少為2

故定點數最少為7.

度序列(4,4,3,3,2,2,2)經判定是圖序列

四

先寫出鄰接矩陣，之后求|λE-A|,通過將每一列加到第一列，然后提出第一列，然后化為對角矩陣，特征值為對角元乘積

得(-1 n-1; n-1 1)

五

方法1：反證+最長路

方法2：反證+握手定理

六

由H圖1必要4充分1充要中的必要條件證明。

當取S=Km中點集時

w(G-S)=m+1>|S|=m

故不是H圖。

七

最優匹配部分課本/PPT原題；

設M*是最優匹配，則其權重等于各點標號l(v)之和；

又設M是任意匹配，則其權重小于等于等于各點標號l(v)之和；

所以M*權重>=M的權重，故為最優匹配。

八

最大可能數量為16

握手定理+簡單可平面圖m<=3n-6

即可得到x<=16

九

理想子圖計數法

2[k]3+3[k]4+[k]5

十

點色數

有K3，故點色數>=3

可找到，故點色數=3

分組略