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

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就是最短路。

2006研究生图论期末试题(120分钟)

一、填空题(15分，每空1分)

1、若两个图的顶点与顶点之间，边与边之间都存在_________对应，而且它们的关联关系也保持其_________关系，则这两个图同构。

2、完全图K4的生成树的数目为_________；阶为6的不同构的树有_________棵。 3、设无向图G有12条边，已知G中度为3的结点有6个，其余结点的度数均小于3，则

G中至少有_________个结点。

4、具有5个结点的自补图的个数有_________。

?0??15、已知图G的邻接矩阵A(G)??0??1?0?1010??1101?1011?，顶点集合V(G)??v1,v2,v3,v4,v5?，

?0101?1111??则由v2到v5的途径长度为2的条数为_________。

6、若Kn为欧拉图，则n=_________；若Kn仅存在欧拉迹而不存在欧拉回路，则n=_________。

7、无向完全图Kn(n为奇数)，共有_________条没有公共边的哈密尔顿圈。

8、设G是具有二分类(X,Y)的偶图，则G包含饱和X的每个顶点的匹配当且仅当

_________，对所有S?X。

9、在有6个点。12条边的简单连通平面图中，每个面均由_________条边组成。

10、彼德森图的点色数为_________；边色数为_________；点独立数为_________。 二、单选或多选题(15分，每题3分)

1,2,3,4,5?，E??(1,2),(2,3),(3,4),(4,5),(5,1)?,则图G??V,E?的补图是( ). 1、设V?? 2 3

1 5 1 1 1 5 5 2 2 4 A 3 B 4 C 4 D 3

2、在下列图中，既是欧拉图又是哈密尔顿图的是( ).

C A B

3、下列图中的( )图，V2到V4是可达的。 V1 V2

V4 V1 V4 V1 D V4 V1 V4 V3 A V2 B V3 V2 C V3 V2 D V3 4、下列图中，可1—因子分解的是( ).

(A) (C) (B) (D)

5、下列优化问题中，存在好算法的是( )

(A) 最短路问题；(B) 最小生成树问题；(C) TSP问题；(D) 最优匹配问题. 三、作图题(10分)

1、分别作出满足下列条件的图

(1)、E图但非H图；(2) H图但非E图；(3) 既非H图又非E图；(4) 既是H图又是E图 2、画出度序列为(3,2,2,1,1,1)的两个非同构的简单图。

四、求下图的最小生成树，并给出它的权值之和(10分)。

v1 1 v4 2 4 9 6 3 a 8 v2 2 v5 6 b

7 2 4 2 9 v3 v6

图G

2 五、给出一个同构函数证明G1?G2(10分)

a 1 2 i 5 f g 3 b 8 e 6 4 h d c 9 7 G1 G2

六、若图G为自补图，那么，它的阶n一定能够表示为4k或者4k?1的形式，其中k为非负整数。而且，图G的边有

n(n?1)条。(5分) 4七、设T为一棵非平凡树，度为i的顶点记为ni，则n1?2?n3?2n4???(k?2)nk。(10分)

八、证明：阶数为8的简单偶图至多有16条边(5分)

九、设图G有10个4度顶点和8个5度顶点，其余顶点度数均为7。求7度顶点的最大数量，使得G保持其可平面性(10分) 十、求图G的色多项式(10分）

1

5 2 4

3

G

…………………… 效 …

… … … … 无 … … … … …

题 … … 院… 学… … 答 … … … … … 内 … … … 名… …姓以 … …… 4 … … 线 … … … … … 封 … … 号…… 学…密 ……………………

电子科技大学研究生试卷

（考试时间： 至 ，共_____小时）

课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2007__年___月____日 成绩 考核方式： （学生填写）

一．填空题(每题

2分，共12分)

1．简单图G=(n,m)中所有不同的生成子图(包括G和空图)的个数是_____个；

2．设无向图G=(n,m)中各顶点度数均为3，且2n=m+3,则n=_____;

m=_____；

3．一棵树有ni个度数为i的结点，i=2,3,…,k,则它有____个度数为1的结点；

．下边赋权图中，最小生成树的权值之和为_______;

v1167v224v635810v39v546v45、某年级学生共选修9门课。期末考试时，必须提前将这9门课先考完，每天每人只在下午考一门课，则至少需要______天才能考完这9门课。 二．单项选择(每题2分，共10分)

1．下面给出的序列中，不是某简单图的度序列的是( ) (A) (11123); (B) (22222); (C) (3333); (D) (1333). 2． 下列图中，是欧拉图的是（ ）

ABC

3． 下列图中，不是哈密尔顿图的是（ ） A B C 4． 下列图中，是可平面图的图的是（ ） A B C 5．下列图中，不是偶图的是（ ）

A B C

DD D D

三、 (8分)画出具有7个顶点的所有非同构的树

四， 用图论的方法证明：任何一个人群中至少有两个人认识的朋友数相同(10分)

五．(10分) 设G为n 阶简单无向图，n>2且n为奇数，G与G的补图G中度数为奇数的顶点个数是否相等？证明你的结论

六．(10分)设G是具有n个顶点的无向简单图，其边数

1证明(1) 证明G中任何两个不相邻顶点的度数之(n?1)(n?2)?2，

21和大于等于n。(2)给出一个图，使它具有n个顶点，m?(n?1)(n?2)?12m?条边，但不是哈密尔顿图。

七、(10分)今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学和物理两门课程。问能否安排他们5人每人只上一门自己所熟悉的课程，使得每门课程都有人教，说明理由

八、(10分)设G是具有n个顶点，m条边，p(P?2)个连通分支的平面图，G的每个面至少由k（k?3）条边所围成，则

m?k(n?p?1) k?2

九．(10分)求下图G的色多项式Pk(G).

图G

十、(10分) (1)、在一个只有2个奇度点的边赋权图中，如何构造一个最优欧拉环游？说明理由；

(2)、在一个边赋权的哈密尔顿图中，如何估计其最优哈密尔顿圈的权值之和的下界？

………以……………内……………答…… ………题……………无……………效……………………

电子科技大学研究生试卷

（考试时间： 至 ，共__2_小时）

课程名称 图论及其应用 教师 学时 50 学分 教学方式 讲授 考核日期_2008__年___月____日 成绩 考核方式： （学生填写）

一．填空题(每题

姓 名 学 院 2分，共20分)

1．若n阶单图G的最大度是?，则其补图的最小度?(G)=_____； 2．若图G1?(n1,m1)，G2?(n2,m2)，则它们的联图G?G1?G2的顶点

数=_____;边数=_____；

3．G是一个完全l部图，ni是第i部的的顶点数i=1，2,3,…,l。

则它的边数为____；

4．下边赋权图中，最小生成树的权值之和为_______;

5. 若G?Kn,则G的谱spec(G)?_______; 6. 5个顶点的不同构的树的棵数为_______; 7. 5阶度极大非哈密尔顿图族是_______;

8. G为具有二分类(X,Y)的偶图，则G包含饱和X的每个顶点的匹配的充分必要条件是______

9. 3阶以上的极大平面图每个面的次数为_______;3阶以上的极大外平面图的每个内部面的次数为_______;

10. n方体的点色数为_______;边色数为_______。 二．单项选择(每题3分，共12分)

1．下面给出的序列中，不是某图的度序列的是( ) (A) (33323); (B) (12222); (C) (5533); (D) (1333). 2．设V(G)=?1,2,3,4,5?，E(G)??(1,2),(2,3),(3,4),(4,5),(5,1)?则图G?(V,E)的补图是（ ）

5 1 2 7 1 1 2 3 3 6 2 5 1 2 4 7 3 4 2 6 1 5 2 5 1 2 1 2 4 (A) 3 4 (B) 3 4 (C) 3 4 (D) 3 3.下列图中，既是欧拉图又是哈密尔顿图的是( )

(A) (B) (C) (D) 4.下列说法中不正确的是( ) (A)每个连通图至少包含一棵生成树； (B)k正则偶图(k>0)一定存在完美匹配； (C)平面图G?(G*)*,其中G*表示G的对偶图； (D)完全图K2n可一因子分解。

三、 (10分)设图G的阶为14，边数为27，G中每个顶点的度只可能为3，4或5，且G有6个度为4的顶点。问G中有多少度为3的顶点？多少度为5的顶点？

四，(10)证明：每棵非平凡树至少有两片树叶(10分)

…………………… 密……………封……………线……………以……………内……………答…… ………题……………无……………效…………………… 电子科技大学研究生试卷

（考试时间： 至 ，共__2_小时）

课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2011__年___月____日 成绩 考核方式： （学生填写）

一．填空题(每空

学 号 姓 名 学 院 1分，共22分)

1．若n阶单图G的最小度是?，则其补图的最大度?(G)=_____。 2．若图G1?(n1,m1)，G2?(n2,m2)，则它们的积图G?G1?G2的顶点数

=_____; 边数=_____。

3．设A是图G的推广邻接矩阵，则An的i行j列元aij(n)等于由G中顶点vi到顶点vj的长度为______的途径数目。 4．完全图Kn的邻接矩阵的最大特征值为_______。 5. 不同构的3阶单图共有_______个。

6. 设n阶图G是具有k个分支的森林，则其边数m(G)?_______。 7. n阶树(n?3)的点连通度为_______；边连通度为________；点

色数为_______； 若其最大度为?，则边色数为________。 8. 图G是k连通的，则G中任意点对间至少有______条内点不交路。

9. 5阶度极大非哈密尔顿图族为______和_______。

10. 完全图K2n能够分解为_______个边不相交的一因子之并。 11. 设连通平面图G具有5个顶点，9条边，则其面数为_______；

n(n?3)阶极大平面图的面数等于__________；n(n?3)阶极大外

平面图的顶点都在外部面边界上时，其内部面共有_______个。 12. 完全偶图Km,n的点独立数等于________,点覆盖数等于______。

13. 完全m元根树有t片树叶，则其总度数为_______。 i个分支点，14．对具有m条边的单图定向，能得到______个不同的定向图。 二．单项选择(每题3分，共15分)

1．下面给出的序列中，不是某图的度序列的是( )

(A) (1,3,5,4,7); (B) (2,2,2,2,2); (C) (3,2,3,3); (D) (1,5,7,1).

2．下列无向图G?(n,m)一定是树的是（ ）

(A) 连通图；(B)无回路但添加一条边后有回路的图； (C) 每对结点间都有路的图； (D) 连通且m?n?1。 3.以下必为欧拉图的是( ) (A) 顶点度数全为偶数的连通图； (B) 奇数顶点只有2个的图； (C) 存在欧拉迹的图； (D) 没有回路的连通图。

4.设G是n(n?3)阶单图，则其最小度??( )

(A) 必要条件；(B)充分条件；(C)充分必要条件。

n是G为哈密尔顿图的25.下列说法正确的是( )

(A) 非平凡树和n(n?2)方体都是偶图； (B) 任何一个3正则图都可1-因子分解；

(C) 可1-因子分解的3正则图中一定存在哈密尔顿圈； (D) 平面图G的对偶图的对偶图与G是同构的。

三、 (10分)设无向图G有12条边，且度数为3的结点有6个，其余结点的度数小于3，求G的最少结点个数。

四，(12分) 在下面边赋权图中求：(1)每个顶点到点a的距离(只需要把距离结果标在相应顶点处，不需要写出过程); (2) 在该图中求出一棵最小生成树，并给出最小生成树权值(不需要中间过程，用波浪线在图中标出即可).

a 7 1 1 2 3 3 6 2 5 7 4 3 6 1 2 4

五．(10分) 今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学、物理两门课程。问能否安排他们都只上他们熟悉的一门课程，使得每门课程都有人教（用图论方法求解）。

六．(6分)设l是赋权完全偶图G=(V,E)的可行顶点标号，若标号对应的相等子图Gl含完美匹配M*,则M*是G的最优匹配。

七.(6分) 求证：在n阶简单平面图G中有?(G)?5，这里?(G)是G的最小度。

八、(10分)课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(GT), 统计学(S),线性代数(LA), 高等微积分(AC), 几何学(G), 和近世代数( MA )。现有10名学生(学生用Ai表示，如下所示）需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。 (要求用图论方法求解)

A1 : LA, S ; A2 : MA, LA, G ; A3: MA, G, LA ; A4: G, LA, AC ; A5: AC, LA, S ; A6: G, AC; A7: GT, MA, LA ; A8: LA,GT, S ; A9: AC, S, LA; A10: GT, S。

本文来源：https://www.bwwdw.com/article/rvlt.html