題號(hào)

答案

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

填空題

1

2^m

生成子圖的定義

2

n=6;m=9

握手定理

3

2+\sum_{i=3}^{k}(i-2)ni

握手定理 + 邊數(shù)=點(diǎn)數(shù)-1

4

20

最小生成樹(shù)算法

5

9

疑似錯(cuò)題！9/1=9；或者可以理解成最小點(diǎn)覆蓋

選擇題

1

D

圖序列的判定(充要條件)

2

D

度數(shù)均為偶數(shù)且連通

3

B

必要條件：若是H圖，則w(G-S)<=S 的逆否：

若w(G-S)>S,則不是H圖

4

B

不含K5.K3,3同胚子圖

A包含K5；C包含K3,3; D包含K3,3

5

B

偶圖 當(dāng)且僅當(dāng) 不含奇圈

大題

三

11個(gè)。

長(zhǎng)度為6：1個(gè)；

長(zhǎng)度為5：2個(gè)；

長(zhǎng)度為4：5個(gè)；

長(zhǎng)度為3：2個(gè)；

長(zhǎng)度為2：1個(gè)

四

轉(zhuǎn)換為簡(jiǎn)單圖中沒(méi)有兩個(gè)度相等的點(diǎn)；

分為無(wú)孤立點(diǎn)/1個(gè)孤立點(diǎn)/2個(gè)孤立點(diǎn)+鴿籠原理討論

五

自補(bǔ)圖定義+n為奇數(shù)-->同奇同偶-->奇數(shù)頂點(diǎn)個(gè)數(shù)相同

六

(1)考慮G中除兩個(gè)不相鄰頂點(diǎn)外，邊數(shù)最多是K(n-2)的邊數(shù)，故若設(shè)不相鄰度數(shù)之和為x，則由握手定理，有：

2m<=(n-2)(n-3)+2x，結(jié)合條件即可得到x>=n;

(2)C2,5或者C1,n滿足

七

不能。轉(zhuǎn)換為匹配問(wèn)題，由Hall定理，S={孫李周}，N(S)=數(shù)理，故不存在飽和老師的匹配，故不能。

八

n-m+Φ=p+1；

2m>=kΦ

聯(lián)立即可得證

九

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

過(guò)程略，建議理想子圖計(jì)數(shù)法

十

經(jīng)常考。

?(1)、 在u與v間求出一條最短路P; (最短路算法)

(2)、 在最短路P上，給每條邊添加一條平行邊得G的歐拉母圖G*;

(3)、 在G的歐拉母圖G* 中用Fleury算法求出一條歐拉環(huán)游。

證明：設(shè)u與v是G的兩個(gè)奇度頂點(diǎn),G*是G的任意一個(gè)歐拉母圖。

考慮G*[E*-E], 顯然它只有兩個(gè)奇數(shù)頂點(diǎn)u與v, 當(dāng)然它們必須在G*[E*-E]的同一個(gè)分支中，因此，存在(u, v)路P*.?

所以歐拉環(huán)游的總權(quán)值>=w(P*)>=w(P)

證畢。

?

(1) 在G中刪掉一點(diǎn)v(任意的)得圖G1;

(2) 在圖G1中求出一棵最小生成樹(shù)T;

(3) 在v的關(guān)聯(lián)邊中選出兩條權(quán)值最小者e1與e2.

若H是G的最優(yōu)圈，則：

W(H)>=W(T)+W(e1)+W(e2)

理由：見(jiàn)課本P88最后一段

設(shè)C為最優(yōu)哈密爾頓圈，

則對(duì)任意頂點(diǎn)v，C-v是最優(yōu)哈密爾頓路，也是G-v中的生成樹(shù)

因此，若T是G-v的最小生成樹(shù)，同時(shí)e和f是和v關(guān)聯(lián)的兩條邊，并使得w(f)+w(e)盡可能小，則W(T)+W(e)+W(f)將是一個(gè)下界。