2007
一．填空题(每题2分，共12分)
1．简单图g=(n,m)中所有不同的生成子图(包括g和空图)的个数是___个；
2．设无向图g=(n,m)中各顶点度数均为3，且2n=m+3,则n=__m=__
3．一棵树有个度数为i的结点，i=2,3,…,k,则它有___个度数为1的结点；
4．下边赋权图中，最小生成树的权值之和为___
5、某年级学生共选修9门课。期末考试时，必须提前将这9门课先考完，每天每人只在下午考一门课，则至少需要___天才能考完这9门课。
二．单项选择(每题2分，共10分)
1．下面给出的序列中，不是某简单图的度序列的是( )
(a) (11123); b) (22222); c) (3333); d) (1333).
2． 下列图中，是欧拉图的是（ ）
3． 下列图中，不是哈密尔顿图的是（ ）
4． 下列图中，是可平面图的图的是（ ）
5．下列图中，不是偶图的是（ ）
三、 (8分)画出具有7个顶点的所有非同构的树。
四， 用图论的方法证明：任何一个人群中至少有两个人认识的朋友数相同(10分)
五．(10分) 设g为n 阶简单无向图，n>2且n为奇数，g与g的补图中度数为奇数的顶点个数是否相等？证明你的结论
六．(10分)设g是具有n个顶点的无向简单图，其边数，证明(1) 证明g中任何两个不相邻顶点的度数之和大于等于n。(2)给出一个图，使它具有n个顶点，条边，但不是哈密尔顿图。
七、(10分)今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学和物理两门课程。问能否安排他们5人每人只上一门自己所熟悉的课程，使得每门课程都有人教，说明理由。
八、(10分)设g是具有n个顶点，m条边，p(个连通分支的平面图，g的每个面至少由k（）条边所围成，则。
九．(10分)求下图g的色多项式pk(g).
十、(10分) (1)、在一个只有2个奇度点的边赋权图中，如何构造一个最优欧拉环游？说明理由；
2)、在一个边赋权的哈密尔顿图中，如何估计其最优哈密尔顿圈的权值之和的下界？
10年研究生试卷 A4
2010 一 填空题 每题2分，共20分 1 若自补图g的顶点数是，则g的边数 2 若图，则它们的联图的顶点数 边数 3 下图g1中u与v间的最短路的长度为 4 设是图g的推广的邻接矩阵，则 k是正整数 的表示的意义为。5.设，则g的谱 6.设8阶图g中没有三角形，则g能够含有的最多边数为7.三角形...
09年研究生试卷 A4
2009 一 填空题 每题2分，共20分 1 若自补图g的顶点数是10，则g的边数 2 若图，则它们的积图的顶点数 边数 3 具有m条边的简单图的子图个数为 4 设g kn,n,则其最大特征值为 5.设g是n阶的完全l等部图，则其边数m g 6.下图g1中最小生成树的权值为 7.6阶度极大非哈密尔顿...
2019级研究生试卷 A4
电子科技大学研究生试卷。考试时间 至 共 2小时 课程名称矩阵理论教师学时 60 学分 3 教学方式课堂讲授考核日期 2009 年 1 月日成绩。考核方式学生填写 一 选择题 20分 1 设，其中i为单位矩阵，则下面正确的选项为 2 设为矩阵的一个广义逆，为的最大秩分解，则a.1 b.r c.0 d...