图论及其应用 2012年 期末考试答案总结

题号

答案

知识点与备注

填空题

1

nk/2

握手定理

2

4

按边分类讨论

3

2^m

生成子图的定义

4

n1m2+n2m1

积图的定义

5

13

最短路算法

6

6

A^2中对角线元素aii: 点i的度数；

故边数为对角线元素之和/2,即为6

7

⌊(n^2)/4⌋

由Turan定理,最大边对应的图为T2,n, 故边数不超过(n^2)/4向下取整

8

3

矩阵树定理计数/凯莱递推计数法/枚举

9

k(G)<=λ(G)<=δ(G)

惠特尼定理

10

第一行：×，√，×，√；

第二行：√，√，×，√；

第三行：×，√，√，√

一笔画：有两个奇数度顶点且连通；

H图：四个充分条件，度序列判定定理，但基本都不符合充分条件，还是画画试试吧...

偶图：不含奇圈；

可平面图：通过子图不与K3,3,K5同胚，不能收缩到K3,3,K5判定不是，通过画判定是

选择题

1

B

是偶数+图序列判定定理

2

D

A-C:显然

D: 强连通关系是等价关系，单向连通不等价。

3

D

ABC都不含奇圈(n方体本来就是n正则偶图)

D:平面图可以含有奇圈

4

C

A: 具有H圈的连通三正则图存在完美匹配；

B：无割边的三正则图一定存在完美匹配，但有割边的三正则图不一定不存在。

C：是的

D：只有阶数为奇数才可以，阶数为偶数不行。

5

B

A: 不然，2m>=6n，与m<=3n-6矛盾；

B: 外部面显然不是三角形；

C：是的，但是原因始终未知。

D：显然。

大题

三

自补图定义+一元二次方程求根公式

\frac{1+\sqrt(1+8(m_{1}+m_{2}))}{2}

四

16

最小生成树算法

五

2[k]3+4[k]4+[k]5(理想子图计数法)

min{k|Pk(G)>=1}

因此点色数3；

略

六

4天。因为去掉1个一因子后是两个点不重的5长圈，因此无1因子分解，故边色数大于等于4。

经尝试，边色数可以为4.

实际上是一个彼得森图！

具体安排略

七

不能。

由Hall定理，取

S={A,B,C,D},N(S)={d,h,t}

故不存在饱和X的匹配，故无法每个学生都得到喜欢的书。

八

用构造1个3因子的方法证明。

因为最小度大于等于n/2+1

故存在H圈，其中有1因子M1；

做G1=G-M1

则G1中最小度大于等于n/2,仍有H圈H2.

取M=M1UH2

M即为一个三因子。因此有三因子。