发布时间 : 星期日 文章图论基础知识汇总（适合建模）更新完毕开始阅读
关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。
例8 对于例7所示的图，如果关联矩阵中每列对应弧的顺序为(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵表示为
1000000??1??101?10000???1?10?10? ?0?10??00?10110?1???0000?111??0?同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中
每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。
（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所示的图，邻接表表示为
这是一个5维指针数组，每一维（上面表示法中的每一行）对应于一个节点的邻接表，如第1行对应于第1个节点的邻接表（即第1个节点的所有出弧）。每个指针单元的第1个数据域表示弧的另一个端点（弧的头），后面的数据域表示对应弧上的权。如第1行中的“2”表示弧的另一个端点为2（即弧为（1,2）），“8”表示对应弧(1,2)上的
-5-
权为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）
节点号i 起始地址point(i) 记录弧信息的数组 1 2 弧编号 1 1 起点 2 3 终点 8 9 权 在数组point中，其元素个数比图的节点数多1（即n?1），且一定有point(1)?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 1 1 2 3 3 4 4 6 5 7 6 9 point(n?1)?m?1。对于节点i，其对应的出弧存放在弧信息数组的位置区间为
[point(i),point(i?1)?1]， (i)?point(i?1)，则节点i没有出弧。这种表示法与弧表表示法也非常相如果point似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中，
弧被编号后有序存放，并增加一个数组（point）记录每个节点出发的弧的起始编号。
前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形（reverse star）表示法：首先存放进入节点1的所有孤，然后接着存放进入节点2的所有弧，依此类推，最后存放进入节点n的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值等有关信息。同样，为了能够快速检索从每个节点的所有入弧，我们一般还用一个数组记录每个节点的入孤的起始地址（即弧的编号）。例如，例7所示的图，可以用反向星形表示法表示为如下形式：
节点对应的入弧的起始地址编号数组（记为rpoint）
节点号i -6-
1 2 3 4 5 6 起始地址rpoint(i) 记录弧信息的数组 1 2 弧编号 2 2 终点 3 1 起点 4 8 权 1 1 3 6 8 9 3 3 1 9 4 3 4 0 5 3 5 6 6 4 5 7 7 4 2 6 8 5 4 3 如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有入弧，则可以综合采用前向和反向星形表示法。当然，将孤信息存放两次是没有必要的，可以只用一个数组（trace）记录一条弧在两种表示法中的对应关系即可。例如，可以在采用前向星形表示法的基础上，加上上面介绍的rpoint数组和如下的trace数组即可。这相当于一种紧凑的双向星形表示法如下所示：
两种表示法中的弧的对应关系（记为trace） 1 2 3 4 5 6 7 8 反向法中弧编号j 4 1 2 5 7 8 3 6 正向法中弧编号trace(j) 对于网络图的表示法，我们作如下说明：
① 星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的优点是占用的存储空间较少，并且对那些不提供指针类型的语言（如 FORTRAN语言等）也容易实现。邻接表表示法对那些提供指针类型的语言（如C语言等）是方便的，且增加或删除一条弧所需的计算工作量很少，而这一操作在星形表示法中所需的计算工作量较大（需要花费O(m)的计算时间）。有关“计算时间”的观念是网络优化中需要考虑的一个关键因素。
② 当网络不是简单图，而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。
③ 上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素0和?1，而不含有?1，因为此时不区分边的起点和终点。又如，在邻接表和星形表示法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。
2.7 轨与连通
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是连通图。
显然有：
-7-
(i) 图P是一条轨的充要条件是P是连通的，且有两个一度的顶点，其余顶点的度为2；
(ii) 图C是一个圈的充要条件是C是各顶点的度均为2的连通图。 §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，令
v?SiSi?1?Si?{ui?1}。
(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??10 -8-
402510?01520?25??1501020???
201001025??2010055??25?25550?50?