(图论B)重庆邮电大学研究生考卷

重庆邮电大学研究生考卷

学号 姓名 考试方式 班级 2010级 考试课程名称 图论及其算法(B) 考试时间： 年 月 日

题号 得分 一 二 三 四 五 六 七 八 九 十 十一 十二 总分 一、解答题（每题10分，共60分）

1、(10分)求有向图D=< V, E >的可达矩阵, 其中V={ v1,v2 ,v3 ,v4 }，E= { (v1,v2),(v2,v3), (v2,v4),(v3,v2), (v3,v4), (v3,v1), (v4,v1) }，(vi,vj)表示vi是起点，vj是终点的有向边。并判定该图的类型。（图的类型有很多种，如简单图、非简单图和多重图等，连通图与非连通图，欧拉图与非欧拉图，哈密顿图与非哈密顿图等，这样考容易产生歧义，能否考具体点）

2、（10分，每题5分）

(1)画一个无向简单欧拉图(既是简单图,又是欧拉图)，使它具有偶数个顶点，偶数条边。 (2)证明 若二部图Km,n(m,n?2)是哈密顿图，则必有m?n.(5分)

3、(10分)一个7阶简单连通图,其中一个顶点度数为6,其余顶点度数为4，试解决如下两个问题:(1)画出该图; (2)判断该图的平面性.

4、（10分）已知一颗无向树T有三个三度点，一个二度点，其余的皆为一度点。试求T中的叶片数。 5、（10分）求带权为1,2,3,3,5,7,8,11的最优二叉树。 6、（10分）通过布尔变量的运算，求下图G的极小点覆盖。

第 1 页 共 3 页

v6 v5 v1

v7 v4 v2 G

v3

二、证明题（每题10分，共40分）

7、证明在n（n≥2）个人的团体中，总有两个人在此团体中恰好有相同个数的朋友。

8、(1)证明：一个平面图G的对偶图G*是欧拉图当且仅当G的每个面均由偶数条边围成.(5分)

(2)证明:任意极大平面图是连通的.(5分)

9、(10分)Floyd算法可以用来求一个加权连通图中任意两点间的最短距离。为介绍Floyd算法，先定义矩阵的两种运算.

定义1 已知矩阵A?(aij)m?l,B?(bjk)l?n,规定

C?A?B?(cij)m?n,其中,

cij?min(ai1?b1j,ai2?b2j,???,ail?blj)。

定义2 已知矩阵中,cijA?(aij)m?n,B?(bjk)m?n,规定

C?A?B?(dij)m?n,其

?min(aij,bij)。

Floyd算法：已知

n阶加权简单图G，设

D?(dij)n?n是图G的边权矩阵，即

dij?w(i,j)（若G是有向图，则dij?w?i,j?），若结点i到结点j无边相连时，

[n][2][3]d??DDD???则ij。依次算出，，，及S，其中，

第 2 页 共 3 页

[2]D[2]?D?D?(dij)n?n

[3]D[3]?D[2]?D?(dij)n?n

???

[n?1]D[n]?D[n?1]?D?(dij)n?n

S?D?D[2]?D[3]????D[n]?(sij)n?n.

[k]d由定义可知，ij表示从结点i到j经k边的路径中的长度最短者，sij就是结点i到

j的所有路径中的长度最短者。

4O(n). 证明 Floyd算法的时间复杂性是

10、（10分）证明S是图G的极大独立集的充分必要条件是V(G)?S是G的极小点覆盖。

第 3 页 共 3 页

本文来源：https://www.bwwdw.com/article/hlhd.html