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

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

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

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

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

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

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

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

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

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

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

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

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

题号

答案

知识点与备注

填空题

1

题目有误

自补图的定义

2

n1n2; n1m2+n2m1

积图的定义

3

2^m

生成子图的定义

4

n

邻接谱的含义与计算；

过程如下：

5

因为完全且等部，故每部顶点数为(n/l),任意两部之间的边数为(n/l)^2, 再乘上2Cl=l(l-1)/2即可

6

8

最小生成树算法

7

C1,6和C2,6

度极大非H图族的定义：n=4. 又能找到边色数=4的作色，故为4.

选择题

1

D

图序列的判定(充要条件)

2

A

强连通图的定义

3

D

Qn是n正则偶图；

n正则(n>0)偶图必存在完美匹配(证明时先证两部顶点数相同，之后X中任意集S关联边集为E1，N(S)关联边集为E2，则E1包含于E2，故E1边数=k|S|小于等于E2边数=k|N(S)|，故Hall定理有饱和X的匹配，又顶点数相同，故有完美匹配。)

4

C

由对偶图做法，AB显然；

C成立当且仅当G连通;

D是定理，证明：

通过对任意两点构造一条曲线来证明，将面边序列转换为点边序列。

大题

三

握手定理+树m=n-1

得树根度数为3

四

反证法

设e=uv为割边，则去掉e后对G1用握手定理，

得总度数和为奇数，不是2m，矛盾！

故没有割边

五

(1) 在G中删掉一点v(任意的)得图G1;

(2) 在图G1中求出一棵最小生成树T;

(3) 在v的关联边中选出两条权值最小者e1与e2.

若H是G的最优圈，则：

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

理由：见课本P88最后一段

设C为最优哈密尔顿圈，

则对任意顶点v，C-v是最优哈密尔顿路，也是G-v中的生成树

因此，若T是G-v的最小生成树，同时e和f是和v关联的两条边，并使得w(f)+w(e)尽可能小，则W(T)+W(e)+W(f)将是一个下界。

六

虽然本题和Hall定理不同，但完全可以参照Hall定理来证明。

必要性：

设M*是完美匹配，则对于V的任意子集S，由于S的顶点在M下和N(S)中的相异顶点配对，故显然有|N(S)|>=|S|.

充分性：

可通过Hall定理的证明来证明；或者直接使用Hall定理：

对X的任意子集S，因为|N(S)|>=|S|,故能够饱和X的所有顶点；|X|=|S|,故能够饱和Y的所有顶点；|Y|=6Φ

矛盾！

八

点色数

有K3，故点色数>=3

可找到，故点色数=3

分组略

九

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

过程略，建议理想子图计数法