Page 207 - 数学建模算法与应用

第八章 图与网络模型及方法应用

必要的，可以只用一个数组记录一条弧在两种表示法中的对应关系即可。例如，
可以在采用前向星形表示法的基础上，加上上面介绍的 rpoint 数组和如下的 trace
数组即可。这相当于一种紧凑的双向星形表示法，如表 8-6 所示。

6. 轨与连通
关
联，称 W 是图 G 的一条道路 (walk)，k 为路长，顶点 v0 和 vk 分别称为 W 的起
点和终点，而 称为它的内部顶点。
若道路 W 的边互不相同，则 W 称为迹 (trail)。若道路 W 的顶点互不相同，

则 W 称为轨 (path)。
称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的
轨叫做圈 (cycle)。

若图 G 的两个顶点 u，v 间存在道路，则称 u 和 v 连通 (connected)。u，v 间
的最短轨的长叫做 u，v 间的距离。记作 d(u，v) 。若图 G 的任二顶点均连通，
则称 G 是连通图。
显然有图 P 是一条轨的充要条件是 P 是连通的，且有两个一度的顶点，其余
顶点的度为 2；图 C 是一个圈的充要条件是 C 是各顶点的度均为 2 的连通图。

第三节 最短路问题的解决

一、两个指定顶点之间的最短路径

问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定
城镇间，找一条最短铁路线。
以各城镇为图 G 的顶点，两城镇间的直通铁路为图 G 相应两顶点间的边，

得图 G 。对 G 的每一边 e ，赋以一个实数 w(e) —直通铁路的长度，称为 e 的权，
得到赋权图 G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图 G 中
指定的两个顶点 u0 ，v0 间的具最小权的轨。这条轨叫做 u0 ，v0 间的最短路，
它的权叫做 u0 ，v0 间的距离，亦记作 d(u0 ，v0 )。

197