2005年研究生期末试题(120分钟)
《图论及其应用》
一、填空(15分，每空1分)
1、 已知图G有10条边，4个度数为3的顶点，其余顶点的度数均小于2，则
G中至少有___8___个顶点 .
2、 m条边的简单图G中所有不同的生成子图(包括G和空图)的个数为
__2m____.
3、 4个顶点的非同构的简单图有__11___个. 4、 图G1的最小生成树各边权值之和为__28___.
4 7 6 4 1 6 5 3 9
2 1
5 10 图G1
5、若W是图G中一条包含所有边的闭通道，则W在这样的闭通道中具有最短长度的充要条件是：
(1) 每一条边最多重复经过_1__次；
(2) 在G的每一个圈上，重复经过的边的数目不超过圈的长度的_一半___.
5,__C15___. 6、5阶度极大非哈密尔顿图族有__C27、在图G2 中，图的度序列为(44443322)，频序列为(422)，独立数为3，
团数为4，点色数为4，边色数为4，直径为3.
图G2
二、选择(15分)
(1)下列序列中，能成为某简单图的度序列的是( C )
(A) (54221) (B) (6654332) (C) (332222)
（2）已知图G有13条边，2个5度顶点，4个3度顶点，其余顶点的的度数为2，则图G有( A )个2度点。
(A) 2 ( B) 4 (C ) 8 (3) 图G如(a)所示，与G同构的图是( C )
(a) (A) (B) (C)
(4) 下列图中为欧拉图的是( B ),为H图的是( AB ),为偶图的是( BC ).
(A) (B) (C) 5．下列图中可1-因子分解的是( B )
(A) (C) (B) 三、设?和?分别是(n,m)图G的最大度与最小度，求证：??证明：n??2m?2m??(10分). nv?V(G)?d(v)?n????2m??. nn四、正整数序列(d1,d2,(10分).
证明：\?\ 结论显然
,dn)是一棵树的度序列的充分必要条件是?di?2(n?1)
i?1\?\
设正整数序列(d1,d2,,dn)满足?di?2(n?1)，易知它是度序列。
i?1n设G是这个度序列的图族中连通分支最少的一个图，知m=E(G)?n?1. 假设G不连通，则?(G)?2，且至少有一个分支G1含有圈C，否则，G是森林，
有m=E(G)?n???n?1矛盾！从C中任意取出一条边e1?u1v1。并在另一分支
G2中任意取出一条边e2?u2v2，作图
G??G??u1v1,u2v2???u1v2,u2v1?
则G?的度序列仍然为(d1,d2,以
G是连通的，G是树。即(d1,d2,,dn)一棵树的度序列。
,dn)且?(G?)??(G)?1，这与G的选取矛盾！所
五、求证：在简单连通平面图G中，至少存在一个度数小于或等于5的顶点 (10分).
证明：若不然，2m?v?V(G)?d(v)?6n?6n?12?m?3n?6,这与G是简单连通平
面图矛盾。
六、证明：(1) 若G恰有两个奇度点u与v，则u与v必连通；
(2) 一棵树至多只有一个完美匹配 (10分).
证明；(1) 因为任意一个图的奇度点个数必然为偶数个，若G恰有两个奇度点u与v，且它们不连通，那么就会得出一个连通图只有一个奇度点的矛盾结论。所以若G恰有两个奇度点u与v，则u与v必连通。
(2) 若树T有两个相异的完美匹配M1,M2，则M1?M2??且T[M1?M2]中
的每个顶点的度数为2，则T中包含圈，这与T是数矛盾！
七、求图G的色多项式Pk(G)(15分).
H1 H2 图G
G 解：图G的补图如图G，则
h(H1,x)?r1x?r2x2?r3x3?r4x4，其中，r1?N1(H1)?0，r2?N2(H1)?2
r3?N3(H1)?4，r4?N4(H1)?1；
h(H2,x)?r1x?r2x2，其中，r1?N1(H2)?1，r2?N2(H2)?1
2234Pk(G)?(x?x)(2x?4x?x)??k?6?5?k?5?6[k]4?2[k]3。
八、求图G中a到b的最短路(15分).
v1 1 v4
2 4 9 6 3 a 8 v2 2 v5 6 b
7 2 4
1 2 9 v3 v6
图G
解 1. A1= {a}，t(a) = 0，T1 = Φ 2.b1?v3
3. m1 = 1, a2 = v3 , t(v3) = t(a) + l(av3) = 1 (最小)，
T2 ={av3} 2. A2 ={a, v3}, b1(2)(2)?v1,b2?v2
?1?3. m2 = 1, a3 = v1 , t(v1) = t(a) + l(av1) = 2 (最小)，
T3 ={av3, av1} 2. A3 ={a, v3, v1}, b1(3)(3)(3)?v2,b2?v2,b3?v4
3. m3 = 3, a4 = v4 , t(v4) = t(v1) + l(v1v4) = 3 (最小)，
T4 ={av3, av1, v1v4}
2. A4 = {a, v3, v1, v4}，b1(4) = v2，b2(4) = v2，b3(4) = v2, b4(4) = v5 3. m4 = 4, a5 = v5 , t(v5) = t(v4) + l(v4v5) = 6 (最小)，
T5 ={av3, av1, v1v4, v4v5}
2. A5 = {a, v3, v1, v4, v5}，b1(5) = v2，b2(5) = v2，b3(5) = v2 , b4(5) = v2, b5(5) = v2 3. m5 = 4, t(v2) = t(v4) + l(v4v2) = 7 (最小)，
T6 ={av3, av1, v1v4, v4v5, v4v2}
2. A6 = {a, v3, v1, v4, v5, v2}, b2(6) = v6, b4(6) = b，b5(6) = v6，b6(6) = v6 3. m6 = 6, a7 = v6 , t(v6) = t(v2) + l(v2v6) = 9 (最小)，
T7 ={av3, av1, v1v4, v4v5, v4v2, v2v6}
2. A7 = {a, v3, v1, v4, v5, v2, v6}, b4(7) = b，b5(7) =b，b7(7) =b 3. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小)，
T8 ={av3, av1, v1v4, v4v5, v4v2, v2v6, v6b}
于是知a与b的距离
d(a, b) = t(b) = 11
由T8导出的树中a到b路av1v4v2v6b就是最短路。
