重庆邮电大学研究生考卷
学号 姓名 考试方式 班级 考试课程名称 《图论及其应用》 考试时间： 2014年 1月 日
题号 得分
1、下列各组数中，哪些能构成无向图的度序列？哪些能构成无向简单图的度序列？ （6分） （1）{1,1,1,2,3,3}; （2）{2,2,2,2,2}; （3）{1,3,3,3};
2、下图中G1与G2同构吗？若两图同构，写出结点之间的对应函数关系；若不同构，则说明理由。（6分）
gafhedicjb一 二 三 四 五 六 七 八 九 十 十一 十二 总分 17691042835
G1 G2
3、画出所有非同构的七阶无向树。（6分）
4、分别用Prim算法、破圈法、克鲁斯克尔算法求下图G的最小生成树，并分别画出生成树
1
的生成过程。（10分）
5、通过布尔变量的运算，求下图G的极大独立集。（10分）
v2v4v5v1v3
v6
6、已知工人x1,x2,x3,x4,x5做工作y1,y2,y3,y4,y5的效率为?ij为下面矩阵所示
y1x1x2x3x4x5?3?2??2??0??1y2y3y4y55541?2022?? 4410??1100?2133?? A?给出一种工作效率最大的任务分配方案，最大工作效率是多少？（10分）
7、求图G的色多项式。（10分）
2
8、求加权图的任意两点间的距离。（10分）
9、设G是n阶自补图，证明n?4k或n?4k?1，其中k为正整数。（8分）
10、设u,v为n阶无向简单图G中两个不相邻的顶点，且d?u??d?v??n，则G为哈密顿图当且仅当G??u,v?为哈密顿图（?u,v?是加的新边）。（8分）
11、证明：设图G有n个节点，m条边，且G是自对偶平面图，则m?2n?2（8分）。
12、设G是带v个顶点，e条边的连通的平面简单图，其中v?3且圈的长度至少为l(如果有圈)，证明：
(1)
l(v?2). （8分） l?3; (2)e?l?23
图论试卷14
