第七章 图（考研习题练习）

1、请回答下列关于图的问题：

1) 有n个顶点的有向强连通图最多有多少条边？最少有多少条边？

2) 表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素？是否为稀疏矩阵？

3) 对于一个有向图、不用拓扑排序、如何判断图中是否存在环？

2、带权图（权值非空，表示边连接的两个顶点的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径。现有一种解决该问题的方法：

1) 设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；

2) 选择距离u最近尚未在最短路径中的一个顶点v，加入到最短路径中，并修改当前结点u=v;

3) 重复步骤2，直到u是目标顶点时为止。

4) 请问上述方法能否求解最短路径？若该方法可行，请证明之；否则请举例说明。

3、试对下图所示的AOE网络：

1) 这个工程最早可能在什么时间结束？

2) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可以使得整个工程提前完成。

10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。 A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表

19．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学 2000 4、2（4分）】

A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径

9．有向图的邻接表存储如下：（1）．画出其邻接矩阵存储；（2）．写出图的所有强连通分量；（3）．写出顶点a到顶点i的全部简单路径。【东北大学 1997 一、5 (5分)】

15．下面的邻接表表示一个给定的无向图

（1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。【复旦大学1998六(10分))

33．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程:

世界六大城市交通里程表(单位:百公里)

PE N PA L T M

PE N PA L T M 109 82 81 21 124 109 58 55 108 32 82 58 3 97 92 81 55 3 95 89 21 108 97 95 113 124 32 92 89 113 （1）．画出这六大城市的交通网络图; （2）．画出该图的邻接表表示法; （3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 【上海海运学院1995 六（9分） 1999 五 （14分）】

36．设无向网G 如上： （1）． 设顶点a、b、c、d、e、f、h的序号分别为1、2、3、4、5、6、7，请列出网G的邻接矩阵、画出网G 的邻接表结构: （2）．写出从顶点a出发,按“深度优先搜索”和“广度优先搜索”方法遍历网G所的到的顶点序列：

按Prim算法求出网G的一棵最小生成树。【北京科技大学 2001 五 (12分)】 3 d 8 1 b 5 5 c 4 e a 6 7 h 3 2 f

48．下图是带权的有向图G的邻接表表示法，求：

（1）．以结点V1出发深度遍历图G所得的结点序列； （2）．以结点V1出发广度遍历图G所得的结点序列； （3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。

【青岛海洋大学 1999 四（10分）】

试编写算法，求解带权有向图的单目标最短路径问题。所谓但目标最短路径问题是指在一个带权有向图G中求从各个顶点到某一指定顶点v的最短路径。例如，对于图(a)所示的带权有向图，用该算法求得得从各个顶点到顶点2的最短路径如图(b)所示。