电子科技大学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<m/2
某些答案给出的也有C3,6，根据书上定义C3,6是错误的
8
4
不同的2因子分解的数目十分复杂，考试算出来不现实，书上和PPT也没有讲过，故本题应理解为1个2因子分解中有多少边不重的二因子，即为4个。
9
n-2; m=3n-6.
书上定理。
n-2:由数学归纳证明。
m=3n-6: 由
A. 2m=3Φ；
B. 欧拉公式
联立即可得证
10
3；4
点色数：
存在奇圈，故大于等于3；又能找到3故为3；
边色数：
彼得森图无1因子分解(去掉一个一因子后剩下两个5点圈，故不能1因子分解)，所以边色数>=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|<=|Y|
对Y的任意子集S，因为|N(S)|>=|S|,故能够饱和Y的所有顶点；|Y|<=|X|，|X|=|Y|
因此，存在完美匹配。
七
由握手定理+欧拉公式：
m<=3Φ-6；
反证，若deg(f)>=6
由面的次数定理得2m>=6Φ
矛盾！
八
点色数
有K3，故点色数>=3
可找到，故点色数=3
分组略
九
2[k]3+3[k]4+[k]5
过程略，建议理想子图计数法