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

电子科技大学2019年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2018年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2017年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2016年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2015年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2014年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2013年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2012年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2011年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2010年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2009年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2008年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2007年图论期末考试答案总结(不一定正确，仅供参考)

电子科技大学2013年期末考试答案，不一定完全正确，仅供参考。

题号

答案

知识点与备注

填空题

1

nk/2

握手定理

2

11

按边分类讨论

3

r*s

欧拉环游至少要走完所有的边，又因为都是偶数，因此可以只走所有的边一次，总边数是rs

4

h+1

除了根节点只有根节点，最后一层只有叶子外，其他层都是一个分支点，一个叶子节点。即为h固定时树叶最少的情况。为h+1.

注意树的高度是指v到根节点的最大距离！

5

4

画图后显然。

6

1

同胚不改变平面性。因此问题等价为K5最少删掉几条边后可平面。即1

7

α

哥尼定理：

定理2 (哥尼，1931) 在偶图中，最大匹配的边数等于最小覆盖的顶点数。

该定理的证明和Hall定理的证明很像：刚开始都是设G=(X, Y) , M*是偶图G的最大匹配。U表示X中M*非饱和点集。Z表示由M*交错路连到U的顶点的所有路上的点作成的集合。且令S=Z∩X, T=Z∩Y。

8

5

(6*5/2)/(6/2)

9

3

显然

10

3

因为有奇圈，故大于等于3.又因为存在3，故为3

选择题

1

B

A：由点独立集的定义：设G是一个图。由G中若干互不邻接的顶点作成的子集称为G的一个点独立集（如完全偶图Km,n的点独立集就是max{m,n}）.可知，A正确。

B: 显然错误，如G是K3；

C：5 mod 4为1，是0或1中的一个。所以存在。

D: 4阶图的补图一定是简单图，而4阶简单图一定是可平面图。

2

D

A,B,C:均不含奇圈。

D：偶图可以是只有两个点的空图。

3

C

A: 连通度一定大于等于2；

B: 错，如K2

C： 定理5 若|V(G)|≧3,则G是块，当且仅当G无环且任意两顶点位于同一圈上。证明很复杂。

D: 单点自环是块。

4

C

A: δ>=n/2, 则任意两个不相邻的店u和v都满足d(u)+d(v)>=n. 考虑它的闭包G’：相邻的点已经相邻，不相邻的点又有d(u)+d(v)>=n，但由闭包定义，d(u)+d(v)>=n的点必然相邻。故闭包所有点都相邻，是完全图。

B：正确，证明同A。

C：错误，如K3加上一个自环。

D: 正确。证明时必要性显然；充分性则考虑G是H图当且仅当G+为了闭包而添加的边是H图，不断以此类推即可证明。

5

B

A:正确；

B: 外平面显然不是；

C：正确，但原因未知！

D：正确，证明：由对偶图的定义知，平面图G与其对偶图G*嵌入在同一平面上，当G连通时，容易知道：G*的无界面 f **中仅含G的唯一顶点v,而除v外，G中其它顶点u均与G*的有限面形成一一对应，于是，G中顶点和G**顶点在这种自然对应方式下一一对应，且对应顶点间邻接关系保持不变，故：二者同构。

大题

三

鸽笼原理

或

反证法，dn>=n与dn=4;

又A5与与K4所有顶点都相连，故点色数>=5

经尝试，可以为5，所以点色数为5.

安排略。

八

(理想子图计数法)

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