2023年研究生图论试卷

电子科技大学研究生试卷。

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

课程名称图论及其应用教师学时 60 学分

教学方式讲授考核日期_2011__年___月___日成绩

考核方式学生填写）

一．填空题(每空1分，共22分)

1．若n阶单图g的最小度是，则其补图的最大度=__

2．若图，，则它们的积图的顶点数=__边数=__

3．设是图的推广邻接矩阵，则的行列元等于由中顶点到顶点的长度为___的途径数目。

4．完全图的邻接矩阵的最大特征值为___

5. 不同构的3阶单图共有___个。

6. 设阶图是具有个分支的森林，则其边数___

7.阶树()的点连通度为___边连通度为___点色数为___若其最大度为，则边色数为___

8. 图是连通的，则中任意点对间至少有___条内点不交路。

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

10. 完全图能够分解为___个边不相交的一因子之并。

11. 设连通平面图具有5个顶点，9条边，则其面数为阶极大平面图的面数等于阶极大外平面图的顶点都在外部面边界上时，其内部面共有___个。

12. 完全偶图的点独立数等于___点覆盖数等于___

13. 完全元根树有片树叶，个分支点，则其总度数为___

14．对具有条边的单图定向，能得到___个不同的定向图。

二．单项选择(每题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．下列无向图一定是树的是（）

(a) 连通图；(b)无回路但添加一条边后有回路的图；

(d) 连通且。

3.以下必为欧拉图的是( )

a) 顶点度数全为偶数的连通图；

b) 奇数顶点只有2个的图；

c) 存在欧拉迹的图；

(d) 没有回路的连通图。

4.设是()阶单图，则其最小度是为哈密尔顿图的( )

a) 必要条件；(b)充分条件；(c)充分必要条件。

5.下列说法正确的是( )

(a) 非平凡树和方体都是偶图；

(b) 任何一个3正则图都可1-因子分解；

(d) 平面图的对偶图的对偶图与是同构的。

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

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

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

六．(6分)设是赋权完全偶图g=(v,e)的可行顶点标号，若标号对应的相等子图含完美匹配，则是g的最优匹配。

七。(6分) 求证：在n阶简单平面图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。

九．(9分)求下图g的色多项式pk(g).

2023年研究生图论试卷

2023年研究生试卷图论评分细则

12年研究生试卷

2023年研究生高固试卷

其他用户还读了

2023年研究生图论试卷

2023年研究生试卷 图论评分细则

12年研究生试卷

2023年研究生高固试卷

其他用户还读了

2023年研究生试卷图论评分细则