max{bi?bj?aj,bj}?max{bi?bj?ai,bi}max{?aj,?bi}?max{?ai,?bj}min{ai,bj}?min{aj,bi}即可。
算法： 1、 2、 3、 4、 例：
A B
1 3 6 2 7 2 3 4 7 4 5 3 5 7 4
加工顺序为13542。
32
第四章 网络分析 §1 图及网络
图，点集，点，边集，边，平行边，自环
C A B D (a) C A B D (b)
定义1 设V是一个非空集合，E是一个V中元素的无序对构成的多重集，有序对G＝〈V，E〉称为一个图，其中，V称为顶点集，其元素称为顶点或点，E称为边集，其元素称为边。
以上定义的图也称为无向图。
相邻，关联，度，握手定理，通路，简单通路，初级通路
33
回路，圈，
连通，连通分支，单连通，强连通 关联矩阵，邻接矩阵 子图，生成子图， 边割，割集 树，
v1 v2 e1 e2 v3 e3 v4 e4
§2 网络上的优化问题
1． 最短路问题
在实际问题当中，图的边往往与某种数量相联系，例如，在铁路交通图中，根据所讨论的问题，每条边上可以标上其代表的铁路的长度，或标上修建该铁路所需的费用等，一般地，引入如下定义．
定义1 设G是一个图，若对G中每条边e都规定一个非负实数w(e)，则称G为赋权图（或权图），w(e) 称为边e的权．G的边与非负实数的这种对应关系(用w表示)称为权函数．
例如，设G是铁路交通图，对G中每条边e规定w(e)为e所代表的铁路的长度，则得到一权图，若规定w(e)为修建e所代
34
表的铁路所需费用，则又得到另一权图．再如，设G是秘密通讯图，对边e规定w(e)为泄秘可能性则得到一权图，又若规定w(e)为维护e所需费用，则又得到另一权图．
按照通常惯例，当u，v不相邻时，规定w(uv)＝∞． 定义２ 设G是一个权图，Ｈ是G的子图，Ｈ中各边的权之和称为子图Ｈ的权，记为w(Ｈ)，即
w(Ｈ)＝
e?E(H)?w(e)．
由于权图中的权常常代表某种耗费，许多最优化问题都是要在一个权图中找出某类具有最小权的子图，其中之一就是最短路问题．
定义３ 设G是一个权图，路P的权w(P)称为P的长度，两点u，v之间最短路的长度称为u，v之间的距离，记为ｄ(u，v)，即
u?v?0,?d(u,v)??min{w(P)|P是(u,v)-路},u,v连通
??,u,v不连通?
定义４ 设G是一个权图，u0∈V(G)，S?V(G)，u0到S内各点的所有路中长度最小者，称为u0到S的最短路，其长度称为u0到S的距离，记为ｄ(u0，S)．
现在我们就来讨论在权图G中寻找最短路的问题，为此，先做几点假设．
1) 显然，只要讨论简单图的问题就够了，所以下面假设G是简单图．
2) 因为当w(uv)＝０时，我们认为u，v重合，所以我们不
35
妨假定所有边的权均为正数．
下面介绍的算法是Dijkstra在1959年提出的，这个算法可以求出G中一点u0到其余各点的最短路及距离，它至今是解最短路问题的最好算法之一．
Dijkstra算法基于如下基本原理．
假设S是V的真子集，u0∈S，令Sˉ＝V－S，若P＝u0?uv是从u0到Sˉ的最短路，则显然u?S，v?S，且P的(u0，u)节必然是最短(u0，u)路，所以
d(u0,S)?w(P)?d(u0,v)?d(u0,u)?w(uv)
?min{d(u0,u)?w(uv)}u?S,v?S
利用该公式，便可按如下过程求最短路．
首先，确定距u0最近的一个顶点．令S0＝｛u0｝，由于距u0最近的顶点必为u0的邻点，故只需求出u1使
w(u0u1)＝min｛w(u0v)|v∈S0｝，
即u0u1是与u0关联的最短边，显然，u0u1便是最短(u0，u1)-路．又令S1＝｛u0，u1｝，且用P1表示路u0u1，??，一般地，若Sk＝｛u0，u1，?，uk｝以及相应的最短路P1，P2，?，Pk已经确定，则可用(1)式来计算d(u0,Sk)，并选取顶点uk+1∈Sk使d(u0，uk+1)＝d(u0,Sk)．这时，d(u0，uk+1)＝d(u0，uj)＋w(ujuk+1)对某个ｊ≤k成立．将边uj uk+1连接到路Pj上，即得最短(u0，uk+1)-36