初等数学方法建模
?1,?j?V,k?(i,j)?A,? bik???1, ?j?V,k?(j,i)?A,?0,其它.?
也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为?1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元（一个?1，一个?1）。可以看出，这种表示法也非常简单、直接。但是，在关联矩阵的所有nm个元素中，只有2m个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。
例8 对于例7所示的图，如果关联矩阵中每列对应弧的顺序为(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵表示为
?11000000???101?10000????0?101?10?10? ??00?10110?1????00000?111??同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中每条弧有一个权，
我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。
（iii）弧表示法
弧表表示法将图以弧表（arc list）的形式存储在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需2m个存储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，也要对应地用额外的存储单元表示。例如，例7所示的图，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的权分别为8，9，6，4，0，3，6和7，则弧表表示如下：
1 1 2 3 4 4 5 5 起点 2 3 4 2 3 5 3 4 终点 8 9 6 4 0 3 6 7 权
为了便于检索，一般按照起点、终点的字典序顺序存储弧表，如上面的弧表就是按照这样的顺序存储
的。
（iv）邻接表表示法
邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。例如，例7所示的图，邻接表表示为
21
初等数学方法建模
这是一个5维指针数组，每一维（上面表示法中的每一行）对应于一个节点的邻接表，如第1行对应于第1个节点的邻接表（即第1个节点的所有出弧）。每个指针单元的第1个数据域表示弧的另一个端点（弧的头），后面的数据域表示对应弧上的权。如第1行中的“2”表示弧的另一个端点为2（即弧为（1,2）），“8”表示对应弧(1,2)上的权为8；“3”表示弧的另一个端点为3（即弧为(1,3)），“9”表示对应弧（1，3）上的权为9。又如，第5行说明节点5出发的弧有(5,3)、(5,4)，他们对应的权分别为6和7。
对于有向图G?(V,A)，一般用A(i)表示节点i的邻接表，即节点i的所有出弧构成的集合或链表（实际上只需要列出弧的另一个端点，即弧的头）。例如上面例子，A(1)?{2,3}，A(5)?{3,4}等。这种记法我们在本书后面将会经常用到。
（v）星形表示法
星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点n出发的所有孤。对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星形（forward star）表示法。
例如，在例7所示的图中，仍然假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的权分别为8，9，6，4，0，3，6和7。此时该网络图可以用前向星形表示法表示如下：
节点对应的出弧的起始地址编号数组（记为point）
1 2 3 4 5 6 节点号i 起始地址point(i) 1 3 4 6 7 9
记录弧信息的数组 1 2 弧编号 1 1 起点 2 3 终点 8 9 权 在数组poin中，且一定有point(1)?1，t，其元素个数比图的节点数多1（即n?1）
3 2 4 6 4 3 2 4 5 4 3 0 6 4 5 3 7 5 3 6 8 5 4 7 point(n?1)?m?1。对于节点i，其对应的出弧存放在弧信息数组的位置区间为
[point(i),point(i?1)?1]，
如果point(i)?point(i?1)，则节点i没有出弧。这种表示法与弧表表示法也非常相似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中，弧被编号后有序存放，并增加一个数组（point）记录每个节点出发的弧的起始编号。
前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形（reverse star）表示法：首先存放进入节点1的所有孤，然后接着存放进入节点2的所有弧，依此类推，最后存放进入节点n的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值等有关信息。同样，为了能够快速检索从每个节点的所有入弧，我们一般还用一个数组记录每个节点的入孤的起始地址（即弧的编号）。例如，例7所示的图，可以用反向星形表示法表示为如下形式：
22
初等数学方法建模
节点对应的入弧的起始地址编号数组（记为rpoint）
节点号i 起始地址rpoint(i)
记录弧信息的数组
1 2 弧编号 2 2 终点 3 1 起点 4 8 权 如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有入弧，则可以综合采用前
向和反向星形表示法。当然，将孤信息存放两次是没有必要的，可以只用一个数组（trace）记录一条弧在两种表示法中的对应关系即可。例如，可以在采用前向星形表示法的基础上，加上上面介绍的rpoint数组和如下的trace数组即可。这相当于一种紧凑的双向星形表示法如下所示：
两种表示法中的弧的对应关系（记为trace）
1 2 3 4 5 6 7 反向法中弧编号j 正向法中弧编号trace(j) 对于网络图的表示法，我们作如下说明：
① 星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的优点是占用的存储空间较少，并且对那些不提供指针类型的语言（如 FORTRAN语言等）也容易实现。邻接表表示法对那些提供指针类型的语言（如C语言等）是方便的，且增加或删除一条弧所需的计算工作量很少，而这一操作在星形表示法中所需的计算工作量较大（需要花费O(m)的计算时间）。有关“计算时间”的观念是网络优化中需要考虑的一个关键因素。
② 当网络不是简单图，而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。
③ 上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素0和?1，而不含有?1，因为此时不区分边的起点和终点。又如，在邻接表和星形表示法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。
2.7 轨与连通
4 1 2 5 7 8 3 3 3 1 9 4 3 4 0 5 3 5 6 6 4 5 7 7 4 2 6 8 5 4 3 1 1 2 1 3 3 4 6 5 8 6 9 8 6 W?v0e1v1e2?ekvk，其中ei?E(G)，1?i?k，vj?V(G)，0?j?k，ei与vi?1,vi关联，称W是图G的一条道路(walk)，k为路长，顶点v0和vk分别称为W的起点和终点，而v1,v2,?,vk?1称为它的内部顶点。
若道路W的边互不相同，则W称为迹(trail)。若道路W的顶点互不相同，则W称为轨(path)。 称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈(cycle)。
若图G的两个顶点u,v间存在道路，则称u和v连通(connected)。u,v间的最短轨的长叫做u,v间的距离。记作d(u,v)。若图G的任二顶点均连通，则称G是连通图。
显然有：
(i) 图P是一条轨的充要条件是P是连通的，且有两个一度的顶点，其余顶点的度为2； (ii) 图C是一个圈的充要条件是C是各顶点的度均为2的连通图。
23
初等数学方法建模
§3 应用—最短路问题
3.1 两个指定顶点之间的最短路径
问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。
以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数w(e)—直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点u0,v0间的具最小权的轨。这条轨叫做u0,v0间的最短路，它的权叫做u0,v0间的距离，亦记作d(u0,v0)。
求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0从近到远为顺序，依次求得u0到G的各顶点的最短路和距离，直至v0（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。
(i) 令l(u0)?0，对v?u0，令l(v)??，S0?{u0}，i?0。 (ii) 对每个v?Si（Si?V\\Si），用
min{l(v),l(u)?w(uv)}
u?Si代替l(v)。计算min{l(v)}，把达到这个最小值的一个顶点记为ui?1，令Si?1?Si?{ui?1}。
v?Si(iii). 若i?|V|?1，停止；若i?|V|?1，用i?1代替i，转(ii)。
算法结束时，从u0到各顶点v的距离由v的最后一次的标号l(v)给出。在v进入Si之前的标号l(v)叫T标号，v进入Si时的标号l(v)叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，u0至各项点的最短路也在图上标示出来了。
例9 某公司在六个城市c1,c2,?,c6中有分公司，从ci到cj的直接航程票价记在下述矩阵的(i,j)位置上。（?表示无直接航路），请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图。
?0?50?????40?25??1050?402510?01520?25??1501020???
201001025??2010055??25?25550?
24
初等数学方法建模
用矩阵an?n（n为顶点个数）存放各边权的邻接矩阵，行向量pb、index1、index2、d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量
?1当第i顶点已标号； pb(i)??0当第i顶点未标号?index2(i) 存放始点到第i点最短通路中第i顶点前一顶点的序号；
d(i) 存放由始点到第i点最短通路的值。
求第一个城市到其它城市的最短路径的Matlab程序如下：
clear; clc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); a=a+a';
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb) d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; index1=[index1,temp]; index=index1(find(d(index1)==d(temp)-a(temp,index1))); if length(index)>=2 index=index(1); end index2(temp)=index; end d, index1, index2 3.2 每对顶点之间的最短路径 计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为O(n)。第二种解决这一问题的方法是由Floyd R W提出的算法，称之为Floyd算法。 假设图G权的邻接矩阵为A0， 3 25