重庆邮电大学研究生考卷
学号 姓名 考试方式 班级 2009级 考试课程名称 图论及其算法 考试时间： 年 月 日
题号 得分 一 二 三 四 五 六 七 八 九 十 十一 十二 总分 一、填空题（每题3分，共30分）
1、图G是简单图当且仅当 。 2、简单图G是二部图当且仅当 。 3、若简单图G满足?(G)?3，则G中存在长度至少为 的圈。 4、连通图G具有欧拉通路，而无欧拉回路的充要条件为 。 5、一颗树有两个2度分支点，一个3度分支点，三个4度分支点，则该树有 片树叶。 6、设T为高为k的二叉树，则T最多有 个顶点。 7、设图G是具有6条边、4个顶点的平面图,则图G的面数为 。 8、一个图为非平面图当且仅当 。 9、S?V，S是图G的极大独立集，则V(G)?S是图G的 。 10、带权为1，3，5，7，8，11，13的最优二叉树T的权W(T)= 。 二、解答题（每题10分，共70分）
1、（10分）求下图G1的色多项式，并指出其色数、点连通度和边连通度。
第 1 页 共 3 页
图G1
2、（10分）（1）证明自补图的阶数n?4k或者n?4k?1，k为某个自然数。 （2）找出所有4阶的自补图。
3、（10分）（1）（4分）证明：设G是有v个顶点?条边，且G是自对偶平面图，则??2v?2。 （2）（6分）已知一颗无向数T有三个3度结点，一个二度结点，其余都是1度结点。
①T有几个1度结点？
②试画出两棵满足上述度数要求的非同构的无向树。
4、（10分）用布尔运算求下图G2的所有极大独立集。
12 6 3 5 4 图G2
5、（10分）用破圈法求下图G3中的一颗最小生成树,写出具体过程，并计算生成树的权。
e1
1e3
2e4e5
2e2
13e6
5 e7
e18
3e9
4
第 2 页 共 3 页
图G3
6、（10分）设简单图G??V,E?, |V|=n, |E|=m, 若有m?Cn2?1?2，则G是哈密尔顿图。 7、（10分）已知工人x1，x2，x3，x4，x5做工作y1，y2，y3，y4，y5的效率?ij为下列矩
y1y2y3y4y5x1x2x3x4x5?3??0?0??2?1?4122??1231? ?5513?2105?4213??阵所示 ??(?ij)?给出一种工作效率最大的分配方案，并求出最大工作效率。
第 3 页 共 3 页
图论试卷09-10
