离散 图论测试答案学习资料.doc

1、对下列有向图

（1）（2分）该图是否有关联矩阵？如果有，写出关联矩阵，如果没有，说明为什么没有？没有。因为关联矩阵无法表示边的方向。

（2）（6分）写出该图的邻接矩阵；写出（不需计算）路径矩阵和可达矩阵；

A=1110 B=1111 P=B

0011 0111

0010 0111

0110 0111

（3）（4分）求出v1到v4的长度小于等于3的拟路径条数，并写出这些拟路径；

计算A、A2、A3，取1行4列元素相加

A2=1131 A3=1261

0120 0031

0010 0010

00210130

v1到v4的长度为3的拟路径条数为0+1+1=2条，分别为v1v1v2v4,v1v3v2v4

（4）（2分）对无向图的邻接矩阵，如何通过计算方法判断无向图是否连通？简单阐述判断过程。通过邻接矩阵计算出可达矩阵，判断可达矩阵是否全1。

2、有6个客人a,b,c,d,e,f围圆桌吃饭，其中a、b、c3人彼此不认识，d、e、f3人彼此不认识，而a、b、c分别都认识d、e、f，d、e、f也分别都认识a、b、c。能否把6个人排成每人都认识邻座？请简单说明如何用图表示和解决此问题。答：以点表示客人，彼此认识则连边（无向边），则可得到6个顶点的3-正则图。因为该图任意2个顶点的度数和≥6，所以是哈密顿图，存在哈密顿回路，则可以按哈密顿回路将客人排好座位。

3.设有一二叉树树叶的权为1，2，2，3，4，6，7，9，12，求相应的最优二叉树。并写出W（T）。

1

1

2

1

2

3

2

20

28

3

4

7

7

1

2

3

2

5

6

11

9

14

12

3

4

7

7

1

2

3

2

5

6

11

9

14

12

3

4

7

7

3

4

W（T）=(1+2)*5+(2+3+4)*4+(6+7)*3+(9+12)*2=132

4．已知带权图G，如图所示．试求图G的最小生成树，并计算该生成树的权．

?

192

?8?7?

4?3

?

第15题图

6

10

?

192

?8?7?

4?3

?

第15题答案图

6

10

做法如下：

=1\*GB3①选边1；=2\*GB3②选边2；

=3\*GB3③选边3；=4\*GB3④选边5；

⑤选边7

最小生成树为{1,2,3,5,7}．如第15题答案图

中粗线所示。

权数为18

5．设G为n阶无向简单图，n35，证明G或G中必含圈.