重庆邮电大学研究生考卷
学号 姓名 考试方式 班级 2010级 考试课程名称 图论及其算法 考试时间： 年 月 日
一、解答题（每题10分，共70分）
1、(10分)画出4阶完全图所有非同构的生成子图。

请说明是否有自补图，如果有，有几个？是否有生成树，如果有，有几棵？
2、(10分)有向图G 如下图所示，计算G 的邻接矩阵的前4次幂，回答下列问题。

（1）G 中v 1到v 4的长度为4的通路有几条？ （2）G 中v 1到v 1的长度为4的回路有几条？
（3）G 中长度为4的通路总数是多少？其中有多少条是回路？
（4）G 中长度小于等于4的通路有几条？其中有多少条是回路？
（5）写出G 的可达矩阵。

1
24
3
3、 (1)判断命题“任意(3)n n ≥阶完全图n K 都是欧拉图”的真假，并说明理由。

(5分)
(2)设G 是分划为,X Y 的二分图,且X Y ≠,则G 一定不是哈密顿图。

(5分)
4、（10分）分别用普林算法和克鲁斯卡尔算法求下图最小支撑树，写出详细求解步骤。

5、（10分）通过布尔变量的运算，求下图的极大独立集。

6、（10分）已知工人12345,,,,x x x x x 做工作12345,,,,y y y y y 的效率为ij ω为下面矩阵所示,
1
2
3
4
5
1
2
3
451554322022044120110032131y y y y y x x A x x x ⎡⎤
⎢⎥⎢⎥=
⎢⎥⎢⎥⎢⎥
⎢⎥⎣⎦
给出一种工作效率最大的任务分配方案，最大工作效率是多少？
7、(1)如果两个图同构,则其对偶图必定同构,这种说法是否正确?如果正确,请证明,如果不正确,请举反例说明 (5分)。

(2)求n 阶完全图n K 的色多项式(,)n f K k ,并写出()n K χ(5分)。

二、证明题（每题10分，共30分）
8、(10分)有n 个人,任意两个人合起来认识其余的n-2个人。

证明：当n≥4时,这n 个人能站成一圈,使每一个人的两旁站着自己认识的人。

9、(10分) 设G 是带v 个顶点，e 条边的连通的平面简单图，其中v ≥3且圈的长度至少为l (如果有圈). 证明:(1) 3l ≥; (2)(2)2
l
e v l ≤--。

10、（10分） (1)证明: 任意一棵树是一个二分图。

(2)在什么条件下,完全二分图,m n K 是树？。