电子科大研究生图论05-14年图论期末试题

《电子科大研究生图论05-14年图论期末试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2005年研究生期末试题(120分钟)《图论及其应用》一、填空(15分，每空1分)1、已知图G有10条边，4个度数为3的顶点，其余顶点的度数均小于2，则G中至少有个顶点.2、m条边的简单图G中所有不同的生成子图(包括G和空图)的个数为3、4个顶点的非同构的简单图有个.4、图G1的最小生成树各边权值之和为5、若W是图G中一条包含所有边的闭通道，则W在这样的闭通道中具有最短长度的充要条件是：(1)每一条边最多重复经过次；(2)在G的每一个圈上，重复经过的边的数目不超过圈的长度的6、5阶度极大非哈密尔顿图族有.7、在图G2中，图的度序列为(44443322)，频序列为

2、(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)(4)下列图中为欧拉图的是(B),为H图的是(AB),为偶图的是(BC).5．下列图中可1-因子分解的是(B)三、设和分别是图G的最大度与最小度，求证：(10分).证明：四、正整数序列是一棵树

3、的度序列的充分必要条件是(10分).证明：结论显然设正整数序列满足，易知它是度序列。设G是这个度序列的图族中连通分支最少的一个图，知m=.假设G不连通，则，且至少有一个分支含有圈C，否则，G是森林，有m=矛盾！从C中任意取出一条边。并在另一分支中任意取出一条边，作图则的度序列仍然为且，这与G的选取矛盾！所以G是连通的，G是树。即一棵树的度序列。五、求证：在简单连通平面图G中，至少存在一个度数小于或等于5的顶点(10分).证明：若不然，这与G是简单连通平面图矛盾。六、证明：(1)若G恰有两个奇度点u与v，则u与v必连通；(2)一棵树至多只有一个完美匹配(10分).

4、证明；(1)因为任意一个图的奇度点个数必然为偶数个，若G恰有两个奇度点u与v，且它们不连通，那么就会得出一个连通图只有一个奇度点的矛盾结论。所以若G恰有两个奇度点u与v，则u与v必连通。(2)若树有两个相异的完美匹配，则且中的每个顶点的度数为2，则中包含圈，这与是数矛盾！七、求图G的色多项式(15分).图G解：图G的补图如图，则，其中，，，；，其中，，。八、求图G中a到b的最短路(15分).v11v463429a8v22v56b72412v3v6图G9解1.A1={a}，t(a)=0，T1=Φ2.3.m1=1,a2=v3,t(v3)=t(a)+l(av3)=1(

5、最小)，T2={av3}2.A2={a,v3},3.m2=1,a3=v1,t(v1)=t(a)+l(av1)=2(最小)，T3={av3,av1}2.A3={a,v3,v1},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)=v53.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)

6、=v2，b2(5)=v2，b3(5)=v2,b4(5)=v2,b5(5)=v23.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)=v63.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)=b3.m7=7

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路就是最短路。2006研究生图论期末试题(120分钟)一、填空题(15分，每空1分)1、若两个图的顶点与顶点之间，边与边之间都存在对应，而且它们的关联关系也保持其关系，则这两个图同构。2、完全图的生成树的数目为；阶为6的不同构的树有棵。3、设无向图有12条边，已知中度为3的结点有6个，其余结点的度数均小于3，则中至少有个结点。4、具有5个结点的自补图的个数有。5、

8、已知图的邻接矩阵，顶点集