运筹学素材(1)说课讲解

1、运筹学素材(1)n图的定义图的定义在自然界和人类的实际生活中，常用点和点与点之间的联线在自然界和人类的实际生活中，常用点和点与点之间的联线所构成的图，来反映某些研究对象和对象之间的某种特定的关系。所构成的图，来反映某些研究对象和对象之间的某种特定的关系。如：如：为了反映城市之间有没有航为了反映城市之间有没有航班，我们可用右图表示。甲城与班，我们可用右图表示。甲城与乙城，乙城与丙城有飞机到达，乙城，乙城与丙城有飞机到达，而甲、丙两城没有直飞航班。而甲、丙两城没有直飞航班。对于工作分配问题，我们可对于工作分配问题，我们可能用点表示工人与需要完成的工能用点表示工人与需要完成的工作，点间连线表示每个工

2、人可以作，点间连线表示每个工人可以胜任哪些工作如右图所示。胜任哪些工作如右图所示。 甲甲乙乙丙丙甲甲乙乙丙丙工人工人ABC工作工作l 图的定义：图的定义： 所谓图，就是顶点（简称点）和一些点之间的连线（不带箭头或所谓图，就是顶点（简称点）和一些点之间的连线（不带箭头或者带箭头）所组成的集合。者带箭头）所组成的集合。 为区别起见，不带箭头的连线称为边，为区别起见，不带箭头的连线称为边， 带箭头的连线称为弧。带箭头的连线称为弧。 如果一个图是由点和边所构成的，则称之为无向图（也简称为图），如果一个图是由点和边所构成的，则称之为无向图（也简称为图），记作记作 ，其中，其中V V表示图表示图G G的非

3、空的顶点集合，的非空的顶点集合，E E表示表示G G的边的集的边的集合。连接顶点合。连接顶点 和和 的边记为的边记为 ； 如果一个图是由点和弧所构成的，则称之为有向图，记作如果一个图是由点和弧所构成的，则称之为有向图，记作 ，其中其中V V仍表示有向图仍表示有向图D D的非空的顶点集合，的非空的顶点集合，A A 表示表示D D的弧集合。一条方的弧集合。一条方向从向从 指向指向 的弧记为的弧记为 。G= V,Eivjvije=v ,vD= V,Aivjvija= v ,v 如无向图：如无向图：G= V,E1 14 43 32 2e e1 1e e5 5e e6 6e e4 4e e3 3e e2

4、 2e e7 71234V =v ,v,v,v1234567E= e ,e ,e ,e ,e ,e ,e112212323434514613744e= v,v,e = v,v,e = v ,v,e = v,v,e = v,v,e = v,v,e = v ,v如有向图：如有向图：D= V,A111221333243452464574685395410561167a = v,v,a = v,v,a = v,v,a = v,v,a = v ,v,a = v ,v,a = v ,v,a = v ,v , a = v ,v,a = v ,va = v ,v1234567V= v ,v ,v ,v ,v

5、,v ,v12311A= a ,a ,a ,a324567a1a2a3a4a6a5a7a8a9a10a11n 基本概念基本概念l 点和边的相关概念：点和边的相关概念：（1 1）顶点数和边数：给定图）顶点数和边数：给定图 ，集合，集合V V的元素的个数，称为图的元素的个数，称为图G G的顶点数，记作的顶点数，记作 ；集合；集合E E的元素的个数，称为图的元素的个数，称为图G G的边数，记的边数，记作作 。（2 2）端点和关联边：若）端点和关联边：若 ，则称顶点，则称顶点 是是 的端点，的端点， 是是 的关联边。的关联边。（3 3）相邻点和相邻边：若顶点）相邻点和相邻边：若顶点 和和 与同一条边相

6、关联，则称点与同一条边相关联，则称点 和和 为相邻点；若边为相邻点；若边 和和 有一个共同的端点，则称其为相邻边。有一个共同的端点，则称其为相邻边。（4 4）环和多重边：若边的两个端点属同一顶点，则称该边为环；若两）环和多重边：若边的两个端点属同一顶点，则称该边为环；若两个端点之间多于一条边，则称这些边为多重边。个端点之间多于一条边，则称这些边为多重边。（5 5）多重图和简单图：含多重边的图称为多重图，无环也无多重边的）多重图和简单图：含多重边的图称为多重图，无环也无多重边的图称为简单图。图称为简单图。G= V,Ep(G)q(G)ije= v ,vEijv ,veeivjvivjviejeij

7、v ,v（6 6）次和孤立点：与点关联的边的条数，称为点的次，记作）次和孤立点：与点关联的边的条数，称为点的次，记作 ；次；次数为零的点为孤立点。数为零的点为孤立点。（7 7）悬挂点和悬挂边：次为）悬挂点和悬挂边：次为1 1的点称为悬挂点；悬挂点的关联边称为的点称为悬挂点；悬挂点的关联边称为悬挂边。悬挂边。（8 8）奇点和偶点：次为奇数的点称为奇点；次为偶数的点为偶点。）奇点和偶点：次为奇数的点称为奇点；次为偶数的点为偶点。定理定理1 1 图图 中，所有顶点的次之和等于所有边数的中，所有顶点的次之和等于所有边数的2 2倍，倍， 即即l 链的概念：链的概念：（1 1）给定一个图）给定一个图 ，一

8、个点、边的交错序列，一个点、边的交错序列， 如果满足。这样的序列称为如果满足。这样的序列称为一条联结和的链，记作一条联结和的链，记作 。d( )vG= V,Ev Vd(v)=2qG= V,E1122n -1n -1niiiiiiiv,e,v,e,v,e,vttt+1iiie =v ,v, t=1, 2,n-11ivniv12niiiv,v,v（2 2）开链和闭链：如果）开链和闭链：如果 ，则该链称为开链；如果，则该链称为开链；如果 ，则该链称为闭链（或称为圈）。则该链称为闭链（或称为圈）。（3 3）简单链和初等链：如链内所含的边均不相同，称之为简单链；如）简单链和初等链：如链内所含的边均不相同

9、，称之为简单链；如链内所含的点均不相同，称之为初等链。链内所含的点均不相同，称之为初等链。 如：如：1niivv1niiv = v12345367v ,v,v,v,v,v,v,v是简单链，是简单链，12367v ,v,v,v,v是初等链，是初等链，12341v ,v,v,v,v是初等圈，是初等圈，412357634v,v ,v,v,v,v,v,v,v是简单圈，是简单圈，1243567e1e2e3e8e4e7e6e5e9（4 4）基础图和路：若把一个有向图）基础图和路：若把一个有向图D D的方向去掉，即每一弧都用相应的方向去掉，即每一弧都用相应得无向边代替，所得到的一个无向图，称为该有向图得无向

10、边代替，所得到的一个无向图，称为该有向图D D的基础图，的基础图，记为记为G G（D D）；）； 基础图基础图G G（D D）中的链（或圈）恢复无向边的方向后，称为有向图）中的链（或圈）恢复无向边的方向后，称为有向图D D的链（或圈）。的链（或圈）。 若交替序列若交替序列 是有向图是有向图G G的一条链，的一条链，且满足且满足 ，即链中每一条弧的箭头方向都和链的方向，即链中每一条弧的箭头方向都和链的方向一致，那么该链称为有向图一致，那么该链称为有向图D D 的一条从的一条从 到到 的路，简记的路，简记 。又若。又若 ，则称，则称为图为图D D中的回中的回路。路。 对无向图对无向图G G来说，链

11、和路（闭链和回路）这两个概念是一致的。但来说，链和路（闭链和回路）这两个概念是一致的。但有向图有向图D D中的链不一定是路，因为有向图的链可能存在和链的方向中的链不一定是路，因为有向图的链可能存在和链的方向不一致的反向弧，但按定义，它们仍是有向图中的链。不一致的反向弧，但按定义，它们仍是有向图中的链。1122n-1n-1niiiiiiiv ,a ,v ,a ,v,a,vkkk+1iiia = v ,v1ivniv12n-1niiii=v ,v ,v,v1niiv =vl 连通图和网络图的概念：连通图和网络图的概念：（1 1）连通图：在一个图）连通图：在一个图G G 中，若任意两点之间至少存在一

12、条链，则称中，若任意两点之间至少存在一条链，则称该图该图G G为连通图，否则称之为不连通图。为连通图，否则称之为不连通图。 如：如：365241a2a3a1a4a5左图为不连通图。左图为不连通图。因为在顶点因为在顶点1， V2，V3，V4和和V5，V6之间不存在任何一条链将之间不存在任何一条链将它们相连接。它们相连接。12345右图为有向连通图右图为有向连通图（2 2）连通分图：若）连通分图：若G G是不连通图，那么它的每一个连通部分称为图是不连通图，那么它的每一个连通部分称为图G G的连通分图。的连通分图。（3 3）子图和支撑子图：设图）子图和支撑子图：设图 ， 若有若有 ，使，使 ，则称，

13、则称 是是 的子图；的子图；若若 ， 则称则称 是是 的支撑子图。的支撑子图。 如，以下右图是左图的支撑子图。如，以下右图是左图的支撑子图。G= V,EG = V ,EVV, EEGGV =V, EEGGv1v1v3v3v5v5v4v4e5e5v3v3v5v5v4v4v2v2e2e2e1e1e3e3e4e4e5e5e6e6e7e7e8e8v2v2e1e1e3e3e4e4v1v1e6e6（4 4）赋权图：设图）赋权图：设图 ，若对其边集，若对其边集E E定义了一个实值函定义了一个实值函数数 ，则称该图为一个赋权图。记作，则称该图为一个赋权图。记作 。 称为边称为边 的权。的权。 如某工厂内连接六

14、个车间的道路网如入所示，已知每条路长，要如某工厂内连接六个车间的道路网如入所示，已知每条路长，要求沿道路架设连接六个车间的电话线路，使电话总长最短。求沿道路架设连接六个车间的电话线路，使电话总长最短。123456652715344左图为一赋权图左图为一赋权图最优解：如红线所示，最优解：如红线所示，电话总长电话总长15个单位。个单位。红线所示为图的最小红线所示为图的最小支撑树支撑树G= V,Eijijw v ,v, v ,vEG= V,E,ijw v ,vijv ,v（5 5）网络图，若）网络图，若 为一赋权图为一赋权图 ，并在其顶点集合，并在其顶点集合V V中指中指定了起点（或称发点）和终点（

15、或称收点），其余的点为中间点，这样定了起点（或称发点）和终点（或称收点），其余的点为中间点，这样的赋权图称为网络图（简称网络）。记作的赋权图称为网络图（简称网络）。记作 。 网络一般是连通的赋权图。网络一般是连通的赋权图。 若一个网络图中的每条边都是有向的弧，则称之为有向网络，记作若一个网络图中的每条边都是有向的弧，则称之为有向网络，记作 G= V,E,N= V,E,N= V,A,n 图的矩阵表示图的矩阵表示l距离矩阵：设图距离矩阵：设图 ， 为边上的权，表示点为边上的权，表示点 到到 之间的距离，则可构造距离矩阵，之间的距离，则可构造距离矩阵， 其中其中如：以下无向赋权图中的权表示点与点之间

16、距离如：以下无向赋权图中的权表示点与点之间距离G= V,E,ijwijnnA =aijijijw v ,v Ea =0 ijv ,v 其他其他1234512345 v v v v vv09247v9034+A= v 23085v44806v7+5601 12 24 47 76 63 35 54 48 89 92 23 34 45 5或或 对有向赋权图，则定义时将改为。对有向赋权图，则定义时将改为。ijaij v ,v ij (v ,v )ivjvl邻接矩阵：邻接矩阵：设图设图 ，则邻接矩阵的元素可定，则邻接矩阵的元素可定义如下义如下ijn nA= aij1a=0G= V,Eij v ,v E其

17、他其他对有向赋权图，则定义时将改为对有向赋权图，则定义时将改为如如ijaij v ,v ij (v ,v )1234512345 v v v v vv01010v10110A= v00000v00001v0110012345n 树及其性质树及其性质l 树的定义：设树的定义：设 ，若，若G G连通，并且没有圈，则称连通，并且没有圈，则称G G为树，为树， 记作记作 。比如有六个顶点的树有比如有六个顶点的树有6 6种，种，p最小支撑树最小支撑树G= V,ET= V,El 定理定理2 2 以下关于树以下关于树T T的六种描述是等价的，的六种描述是等价的，（1 1）无圈连通图；）无圈连通图；（2 2）

18、无圈，）无圈， ( ( 即图有即图有 条边，条边， 是图中的顶点数是图中的顶点数) )；（3 3）连通，）连通， ；（4 4）无圈，但增加一条边可得唯一一个圈；）无圈，但增加一条边可得唯一一个圈；（5 5）连通，但舍弃一条边则不连通；）连通，但舍弃一条边则不连通；（6 6）每一对顶点之间有一条且仅有一条链。）每一对顶点之间有一条且仅有一条链。 上述六个等价命题可以使用循环证明法，即由命题（上述六个等价命题可以使用循环证明法，即由命题（1 1）推得命题）推得命题（2 2），再由命题（），再由命题（2 2）推得命题（）推得命题（3 3），），依次类推，最后由命题，依次类推，最后由命题（6 6）回推

19、到命题（）回推到命题（1 1），完成以上推导过程即证明了六个命题是等价），完成以上推导过程即证明了六个命题是等价的。的。qp1p1pqp1n 图的支撑树图的支撑树l 支撑树的定义：假设图支撑树的定义：假设图 是图是图 的支撑子图，的支撑子图，如果图如果图 是一个树，则称是一个树，则称T T是是G G的支撑树。的支撑树。 如下图中，（如下图中，（b b）图是）图是(a) (a) 图的支撑树图的支撑树l 定理定理3 3 图图G G有支撑树的充分必要条件是图有支撑树的充分必要条件是图G G是连通的是连通的T= V,ET= V,EG= V,EV1V2V3V4V5V6V2V3V4V5V6（a）（b）n

20、最小支撑树最小支撑树l 定义定义 设赋权图设赋权图 ，它的每条边，它的每条边 有非负权有非负权 ， 是是G G的一个支撑树，的一个支撑树， 中所有边的权之和中所有边的权之和 如果如果 ，则称，则称 是是G G的最小支撑树。的最小支撑树。l 定理定理4 4 设赋权图设赋权图 ，若把，若把E E分割成两个不相交的非空子集分割成两个不相交的非空子集 和和 ，那么连接这两个子集的最小边一定包含在，那么连接这两个子集的最小边一定包含在G G的最小支撑树内。的最小支撑树内。 由定理由定理4 4可以引出求最小支撑树的方法可以引出求最小支撑树的方法 G= V,E,ijv ,vijwT= V,EEijijv ,

21、vE(T)=ww*TG(T )=Min(T)ww是的支撑树*TG= V,E,wSSl 求最小支撑树的方法。求最小支撑树的方法。（1 1）避圈法。步骤如下：）避圈法。步骤如下： 从赋权图从赋权图G G中任选一点中任选一点 ，令，令 ， ； 从连接从连接 和和 的边中选择权最小的边，不妨假设为的边中选择权最小的边，不妨假设为 ，由定理由定理4 4，它必包含在最小支撑树内；，它必包含在最小支撑树内； 令令 ， ； 若若 ，则停止计算，已选出的各条边已构成最小支撑树，则停止计算，已选出的各条边已构成最小支撑树，否则回到。否则回到。例例1 1 某工厂联结六个车间的道路网如下图所示，已知每条道路长，某工厂

22、联结六个车间的道路网如下图所示，已知每条道路长，要求沿道路架设联结六个车间的电话网，使电话线的总长最短。要求沿道路架设联结六个车间的电话网，使电话线的总长最短。iv iS= vSv/vV,vSSSijv ,v jSU vSSv/vV,vSSV V1 1V V2 2V V4 4V V3 3V V5 5V V6 66 61 15 55 57 72 23 34 44 4至此至此 ，停止计算，停止计算， V1V2V4V3V5V6615572344解：这是解：这是求最小支撑树的问题，由避圈法的步骤，在图求最小支撑树的问题，由避圈法的步骤，在图G G的六个顶的六个顶点中任选其中一点作为点中任选其中一点作为

23、S S，比如选，比如选 ，则，则， 联结联结 和和 一共有一共有3 3条边，取最短边条边，取最短边 ，并令并令 ，依次类推依次类推*(T )1234515w 3S= v12456Sv ,v ,v ,v ,vSS23v ,v23S= v ,vS=ES ，最短电话线路的总长为，最短电话线路的总长为1515个单位。个单位。（2 2）破圈法。）破圈法。 步骤是：在图中任取一个圈，从圈中除去权最大的一条边步骤是：在图中任取一个圈，从圈中除去权最大的一条边（圈中存在两条以上最大权的边，可任选其中一条），在余下的（圈中存在两条以上最大权的边，可任选其中一条），在余下的支撑子图中重复这个步骤，一直得到一个不含

24、圈的支撑子图为止，支撑子图中重复这个步骤，一直得到一个不含圈的支撑子图为止，这时的图就是原赋权图的最小支撑树。这时的图就是原赋权图的最小支撑树。例例2 2，用破圈法求例，用破圈法求例1 1中的赋权图的最小支撑树。中的赋权图的最小支撑树。V1V3V5V6615572344 ，最短电话线路的总长为，最短电话线路的总长为1515个单位。个单位。*(T )1 234515w 最短路问题表述：最短路问题表述：给定一个赋权图给定一个赋权图 ，对每一边，对每一边 相应地有权相应地有权，又有两点，又有两点 ，设是中从到的一条路，路的，设是中从到的一条路，路的权是中所有边的权之和，记为权是中所有边的权之和，记为

25、 。最短路问题就是求从到的路中一条权最小的路最短路问题就是求从到的路中一条权最小的路0 0，使，使上述定义中，若是有向赋权图，则任一边改为任一弧上述定义中，若是有向赋权图，则任一边改为任一弧，其他相同。此时从到的路应是沿弧的箭头方向首，其他相同。此时从到的路应是沿弧的箭头方向首尾相接的路。尾相接的路。ijija =(v ,v )ijije =v ,v stv ,vV pw 0pp= minpwwG= V,E,ijijewsvtvsvtvijije =v ,v svtvp最短路问题最短路问题n Dijkstra Dijkstra算法算法狄克斯拉算法是由狄克斯拉算法是由DijkstraDijkst

26、ra于于19591959年提出来，用于求解指定两点年提出来，用于求解指定两点 ，cccc之间的最短路，或从指定点之间的最短路，或从指定点 到其余各点的最短路，目前被认到其余各点的最短路，目前被认为是求为是求 情形下最短路问题的最好方法。情形下最短路问题的最好方法。l基本思路基于以下原理：基本思路基于以下原理：若是从若是从 到到 的最短路，的最短路， 是中的一个点，那么从是中的一个点，那么从 到到的最短路就是从沿到的最短路就是从沿到 的那条路。的那条路。l采用标号法：标号与标号。标号为试探性标号，为永久采用标号法：标号与标号。标号为试探性标号，为永久性标号。给性标号。给 点一个标号时，该标号表示

27、从点一个标号时，该标号表示从 到到 点的最短路权，点的最短路权，点的标号不再改变。给点的标号不再改变。给 点一个标号时，标号表示从点一个标号时，标号表示从 到到 点的点的最短路权的上界，是一种临时标号。凡没有得到标号的点都有标最短路权的上界，是一种临时标号。凡没有得到标号的点都有标号。算法每一步都把某一点的标号改为标号，当终点号。算法每一步都把某一点的标号改为标号，当终点 得到标得到标号时，全部计算结束。号时，全部计算结束。ijw0ivsvtvsvsvtvtvsvivsvivivivivivsvsvlDijkstraDijkstra算法基本步骤：算法基本步骤： 给给 以标号，其余各点均给标号，

28、以标号，其余各点均给标号， 。 若若 点为得到标号的点，考虑点为得到标号的点，考虑 且且 为标号。为标号。对的标号进行如下的更改：对的标号进行如下的更改： 比较所有具有标号的点，若比较所有具有标号的点，若则把最小值对应的点则把最小值对应的点 改为标号，即改为标号，即 当存在两个以上最小者时，可同时改为标号。当存在两个以上最小者时，可同时改为标号。若全部点均为标号则停止。否则转回。若全部点均为标号则停止。否则转回。 步骤步骤(3)(3)，当给顶点标号时，可以在图的对应顶点旁标上一个，当给顶点标号时，可以在图的对应顶点旁标上一个记号（记号（ ， ），其中），其中 为从为从 到到 的最短路上与邻接的

29、的最短路上与邻接的顶点，为从顶点，为从 到到 的最短路长。的记号取（，）的最短路长。的记号取（，）sP v=0jijv , v ,v EjjiijT v=minT v,P v+wkkP v=T vivsviT v=+jvjvkvkjjT(v )= minT vivkP vivkP vsvsvsvsvkvkvkvkv例例3 3 用用DijkstraDijkstra算法求图中从算法求图中从 的最短路的最短路17vv122355357751解：解： 首先给以首先给以P P标号标号 给其余所有点标号给其余所有点标号 (2)(2)考察，由于考察，由于且且 是标号点，所以是标号点，所以修改标号为：修改标号

30、为：1P v=0iT v=+,i=2,3,7.(v1, 0)121314,Avvvvvv234v ,v ,v在所有标号中，在所有标号中， ，于是给标号，于是给标号令令 ，并标上（并标上（ ，）。，）。2jj=2,3,4,5,6,7T(v )=minT v=22P(v )=21v1v221123311344114T v=min T v,P v+=min,0+2 =2T v=min T v,P v+=min,0+5 =5T v=min T v,P v+=min,0+3 =3www2v1v(v1, 2)122355357751(v1, 0)在所有标号中，在所有标号中， 最小，于是给标号最小，于是给标

31、号令令 ，并标上（并标上（ ，3 3）。）。4jj=3,4,5,6,7T(v )= min T v=34v4P(v )=31v(3) (3) 考察考察 ，因因且且 是标号，故修改对应是标号，故修改对应的标号：的标号：2v 2326v ,v, v ,vA36v ,v3322366226T v=min T v,P v+=min 5,2+2 =4T v=min T v,P v+=min,2+7 =9ww(v1, 3)34567T v=5, T v=3, T v=T v=T v=(v1, 2)(4) (4) 考察考察 ，因因 且且 是标号，故是标号，故修改对应的标号为：修改对应的标号为：在所有标号中，

32、在所有标号中， 最小，于是给标号最小，于是给标号令令 ，并标上，并标上（，（，4 4）。）。1223553577512v3657T v= 4, T v= 9, T v=T v=(v1, 0)3jj=3,5,6,7T(v )= min T v=43P(v )=445v ,vA5v(v1, 3)4v55445T v=min T v,P v+=min,3+5 =8w3v(v2, 4)(v1, 2)在所有标号中，在所有标号中， 最小，于是给标号最小，于是给标号令令 ，标上（，标上（ ，7 7）。）。(5) (5) 考察考察 ，因因 且且 是标号，故修改对是标号，故修改对应的标号为：应的标号为：1223

33、55357751567T v=8, T v= 9, T v=5533566336T v=min T v,P v+=min 8,4+3 =7T v=min T v,P v+=min 9,4+5 =9ww5P(v )=7(v1, 0) 3536v ,v, v ,vA(v1, 3)3v(v2, 4)56v ,v5jj=5,6,7T(v )= minT v=75v3v(v3, 7)(v1, 2)在所有标号中，在所有标号中， 最小，于是给标号最小，于是给标号令令 ，标上（，标上（，8 8）。）。12235535775167T v=9, T v=(6) (6) 考察考察 ，因因 且且 是标号，故修改对应的

34、是标号，故修改对应的标号为：标号为：(v1, 0) 5657v ,v, v ,vA(v1, 3)(v2, 4)67v ,v5jj=6,7T(v )=minT v=86v6P(v )=85v(v3, 7)5v6655677557T v=min T v,P v+=min 9,7+1 =8T v=min T v,P v+=min,7+7 =14ww(v5, 8)(v1, 2)(7) (7) 考察考察 ，因因 且且 是标号，故修改对应的是标号，故修改对应的标号为：标号为：由于只剩最后一个标号，所以由于只剩最后一个标号，所以给标号。给标号。令令 ，标上（，标上（，1313）。）。 由于所有顶点都标上了标

35、号由于所有顶点都标上了标号所以计算结束。所以计算结束。(v,13)从到的最短路：从到的最短路：最短路长最短路长13.122355357751(v1, 0)67v ,vA(v1, 3)(v2,4)(v3, 7)7v(v5, 8)6v77667T v=min T v,P v+wmin 14,85137P(v )=137v7v1v123567vvvvvv6v(v1, 2)n 逐次逼近算法逐次逼近算法 DijkstraDijkstra算法只适用于所有算法只适用于所有 的情形，当赋权有向图中存在的情形，当赋权有向图中存在负权时，则算法失效。负权时，则算法失效。例如在右图所示的赋权有向图中，例如在右图所示

36、的赋权有向图中，用用DijkstraDijkstra算法得算法得 到到 的最短路的的最短路的权是权是5.5.但这里显然不对；但这里显然不对； 因为因为 到到 的最短路是的最短路是 ，权为，权为3 3。 当当 存在负权时，可采取逐次逼近算法来求解最短路。存在负权时，可采取逐次逼近算法来求解最短路。 不妨设从任一点不妨设从任一点 到任一点到任一点 都有一条弧，如果都有一条弧，如果则添加弧则添加弧 ，且令，且令 。 如果为同一顶点，则如果为同一顶点，则 。 ijw01v3v123vvv1v3v75-4231ivijw jvD= V,A,ijija =(v ,v )Aijija =(v ,v )ii=

37、 0, i=1,2,pw 由最优性原理，若令由最优性原理，若令 为从为从 到到 的最短距离，则必满足如的最短距离，则必满足如下方程：下方程： ，其中，其中P为为D的点数。的点数。 由此可得如下递推公式：由此可得如下递推公式： 其中其中 表示从表示从 走一步直接到达走一步直接到达 的最短距离，的最短距离， 表示从表示从 走走t t步到达步到达 的最短距离。为迭代步数。的最短距离。为迭代步数。 若第若第k k步，对所有步，对所有 ，有，有 则则 为为 到任一点到任一点 的最短路权。的最短路权。 sjd v ,vsvjvsjsiiji=1,2,pd v ,v= mind v ,v+ws到到j 的最短

38、路的最短路s s到到i的最短路的最短路i j 1sjsjdv ,v= , j1,2,p;w tt-1sjsiiji=1,2,pdv ,vmindv ,v +w 1sjdv ,v tsjdv ,vsvjv kk-1sjsjdv ,v=dv ,vj1,2,p ksjdv ,vsvjvsvjv解：迭代初始条件为：解：迭代初始条件为：有有 第二步迭代：第二步迭代：用表表示全部计算过程。用表表示全部计算过程。 1sjsjdv ,v=w 111112111314111516111718dv ,v= 0, dv ,v= -1,dv ,v= -2, dv ,v= 3, dv ,v=+ , dv ,v=+ ,d

39、v ,v=+ , dv ,v=+ .例例4 4 求所示赋权有向图中从求所示赋权有向图中从 到各点的最短路。到各点的最短路。11-1-1-2-3-3-56318-527212345678 21sjsiijidv ,v= min dv ,v+w, j=1,2,81-11v0-5-350-1-1710110-1-73208-2-21 1-5-50-3-5-1206003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格为表中空格为） 111111121314dv ,v= 0, dv ,v= -1,dv ,v= -2, dv

40、 ,v= 3 60-5-3-550-1-1-17101-310-1-7-73208-2-2-21 1-5-50-3-5-5-12060003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格为表中空格为）660-5-3-5-550-1-1-1-17101-3-310-1-7-7-73208-2-2-2-21 1-5-50-3-5-5-5-120600003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格为表中空格为）当时当时表明已得到从表

41、明已得到从 到各点的最短路的权，即表中最后一列数。到各点的最短路的权，即表中最后一列数。如果需要知道点到各点的最短路径，可以采用如果需要知道点到各点的最短路径，可以采用“反向追踪反向追踪”的办法。的办法。比如已知，则寻找一点，使比如已知，则寻找一点，使记下，再考察寻找一点，使记下，再考察寻找一点，使记下，直至达到为止本例中记下，直至达到为止本例中因为因为由记下由记下由记下由记下因为因为 一步可达，所以最短路径一步可达，所以最短路径 431j1jdv ,v=dv ,vj=1, 2,81iik1kd v ,vwd v ,vt=413d v ,v=2166818d v ,v+w=(-1)+7=6=d

42、 v ,v1v1368vvvv1v18d v ,v=668(v ,v )133616d v ,v+w =(-2)+1= -1 =d v ,v36(v ,v )1jd v ,vkv1kkj1jd v ,vwd v ,vkj(v ,v )1kd v ,v,iv1vik(v ,v )660-5-3-5-550-1-1-1-17101-3-310-1-7-7-7320-2-2-2-21 1-5-50-3-5-5-5-120600003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格为表中空格为）例例5 5 设备更新问题。某

43、企业使用一台设备，在每年年初，都要决定设备更新问题。某企业使用一台设备，在每年年初，都要决定是否更新。若购置新设备，要付购买费；若继续使用旧设备，则支是否更新。若购置新设备，要付购买费；若继续使用旧设备，则支付维修费用。试制定一个付维修费用。试制定一个5 5年更新计划，使总支出最少。年更新计划，使总支出最少。 若已知设备在各年的购买费及不同机器役龄时的残值和维修费，若已知设备在各年的购买费及不同机器役龄时的残值和维修费，如下表所示：如下表所示：第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 购买费购买费 11111212131314141414机器役龄机器役龄 0

44、-10-11-21-22-32-33-43-44-54-5维修费维修费 5 56 68 811111818残值残值 4 43 32 21 10 0解：把这个问题化为最短路问题解：把这个问题化为最短路问题用用 表示第表示第i i年初购进一台新设备，虚设一个点年初购进一台新设备，虚设一个点 表示第表示第5 5年底；年底； 用弧用弧 表示第表示第i i年初购的设备一直使用到第年初购的设备一直使用到第j j年年初（第年年初（第j-1j-1年年低）；弧年年低）；弧旁的数字表示第旁的数字表示第i i年初购进设备，一直使用到第年初购进设备，一直使用到第j j年初所需支付的购买、年初所需支付的购买、维修的全部

45、费用。维修的全部费用。 这样设备更新问题就变为：求从这样设备更新问题就变为：求从 到到 的最短路的最短路. .ivijv ,v1v6vijv ,v6v第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 购买费购买费 11111212131314141414机器役龄机器役龄 0-10-11-21-22-32-33-43-44-54-5维修费维修费 5 56 68 811111818残值残值 4 43 32 21 10 0第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 购买费购买费 11111212131314141414机器役龄机器役龄 0

46、-10-11-21-22-32-33-43-44-54-5维修费维修费 5 56 68 811111818残值残值 4 43 32 21 10 0194059121314152130152841292220123456购买购买维修维修残值残值费用费用 计算结果表明计算结果表明 为最短路，路长为为最短路，路长为4949。即在。即在第第1 1年、第年、第3 3年初各购买一台新设备为最优决策，这时年初各购买一台新设备为最优决策，这时5 5年的总费用年的总费用为为4949。136vvv194059121314152130152841292220123456(v1,0)(v1,12)(v1,19)(v1

47、,28)(v3,40)(v3,49) V1 V2 12V3 19 19V4 28 28 28V5 40 40 40 40V6 59 53 49 49 49相邻点相邻点V1 V1 V1 V1 V3V3标号标号右图是输油管道网，为起点，右图是输油管道网，为起点， 是终点，为中转站，边上是终点，为中转站，边上的数表示该管道的最大输油能力，的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使问应如何安排各管道输油量，才能使从从 到到 的总输油量最大？的总输油量最大？ 最大流问题是网络分析中一类应用极为广泛的问题。在交最大流问题是网络分析中一类应用极为广泛的问题。在交通运输网络中有人流、车流、

48、货物流；供水网络中有水流；金通运输网络中有人流、车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流；等等。融系统中有现金流；通讯系统中有信息流；等等。2020世纪世纪5050年年代代Ford Ford ，FulkersonFulkerson建立的建立的“网络流理论网络流理论”是网络应用的重要是网络应用的重要组成部分。组成部分。p最大流问题最大流问题1234v ,v ,v ,vsvtvtvsv32442324211tn 基本概念基本概念l 网络与流：网络与流： 我们已经给出了网络图的概念，网络图是一种无向或有向赋我们已经给出了网络图的概念，网络图是一种无向或有向赋权图，在其顶

49、点集合中指定了起点和终点，其余的点为中间点。权图，在其顶点集合中指定了起点和终点，其余的点为中间点。在最大流问题中，我们所讨论的网络都是有向连通赋权图，记在最大流问题中，我们所讨论的网络都是有向连通赋权图，记作作 ，称，称V V中的起点中的起点 为发点，终点为发点，终点 为收点，其为收点，其余的点仍为中间点。对于每一个弧余的点仍为中间点。对于每一个弧 ，对应有一个，对应有一个权权 ，称为弧的容量，简记，称为弧的容量，简记 。 所谓网络上的流，是指定义在弧集合所谓网络上的流，是指定义在弧集合A A上的一个函数上的一个函数 ， 并称并称 为弧为弧 上的流量，简记作上的流量，简记作 。N= V,A,

50、Csvijv ,vAijc v ,v0ijcijf= f v ,vijf v ,vijftvijv ,vl可行流与最大流可行流与最大流满足下列条件的流成为可行流：满足下列条件的流成为可行流：容量限制条件：每一弧容量限制条件：每一弧平衡条件：对于中间点平衡条件：对于中间点 ，有，有对于发点对于发点 ，收点，收点 ，有，有并称为这个可行流的流量。并称为这个可行流的流量。可行流总是存在的，如零流，可行流总是存在的，如零流， 。所谓最大流问题，就是求一个流所谓最大流问题，就是求一个流 ，使其流量，使其流量 达到最大，达到最大，并且满足以上容量限制条件和平衡条件。并且满足以上容量限制条件和平衡条件。最大

51、流问题是一个特殊的线性规划问题最大流问题是一个特殊的线性规划问题ijijijv ,vA, 0fc .ijkiijki(v ,v )A(v,v )Af =fiv siitsiit(v ,v ) A(v ,v ) Af =f =v f v f ijf =0,v f =0 ijfsvtv v f ijfl增广链：增广链：若若 是网络中联结发点是网络中联结发点 和收点和收点 的一条链，且链的方向是从的一条链，且链的方向是从到到 ，则与链的方向一致的弧叫前向弧，则与链的方向一致的弧叫前向弧， 表示前向弧的集合；表示前向弧的集合；与链的方向相反的弧叫后向弧，与链的方向相反的弧叫后向弧， 表示后向弧的集合。

52、表示后向弧的集合。定义定义1 1 设设 是一个可行流，是一个可行流， 是从到是从到 的一条链，的一条链，若若 满足下列条件，则是可行流的一条增广链：满足下列条件，则是可行流的一条增广链： 前向弧前向弧 上，上， ，即，即 中每一弧是非饱和弧，中每一弧是非饱和弧， 后向弧后向弧 上，上， ，即，即 中每一弧是非零流弧。中每一弧是非零流弧。svtvsvtv+_ ijftv ijf+ijv ,v+_ijv ,vijij0v f*f 可行流可行流 是最大流，当且仅当不存在关于的增广链。是最大流，当且仅当不存在关于的增广链。证明：（证明：（）若中不存在关于的增广链，）若中不存在关于的增广链，则定义如下非

53、空点集，令，则定义如下非空点集，令，若，且则令，若，且则令，若，且则令，若，且则令，因为不存在关于的增广链，所以。因为不存在关于的增广链，所以。于是得到一个截集，显然必有于是得到一个截集，显然必有所以，即可行流的流量等于截集所以，即可行流的流量等于截集的截量。所以必是最大流，定理得证。的截量。所以必是最大流，定理得证。 *f*f*1v *v f*f*s1vv*i1vvij*ijfc*j1vv*i1vvji*f0*j1vv*t1vv*11V ,V*ijij11*ij*ij11cv ,vV ,Vf =0v ,vV ,V *11v f=c V ,V*f*11V ,V*fn Ford-Fulkerso

54、n Ford-Fulkerson算法算法福特富克逊算法又称寻求最大流的标号法。前提是已有一个可行福特富克逊算法又称寻求最大流的标号法。前提是已有一个可行流，标号算法分流，标号算法分2 2步。第步。第1 1步：给顶点的标号过程。通过顶点的标号来寻步：给顶点的标号过程。通过顶点的标号来寻找增广链；第找增广链；第2 2步是调整过程，沿增广链调整以增加流量。步是调整过程，沿增广链调整以增加流量。标号过程标号过程每个顶点的标号包含两部分：第每个顶点的标号包含两部分：第1 1部分表明它的标号是从哪一个顶部分表明它的标号是从哪一个顶点得到，以便找出增广链；第点得到，以便找出增广链；第2 2部分是为确定增广链

55、的调整量用的。部分是为确定增广链的调整量用的。给发点给发点 以标号以标号 ；选择一个已标号的点选择一个已标号的点 ，对于，对于 的所有未标号的邻接点的所有未标号的邻接点 ，如果如果 ，且，且 ，令，令 ，并给并给 以标号以标号 ；如果；如果 ，且，且 ，令令 ，并给，并给 以标号以标号 。svsv ,ivivjvijv ,vAijijfcjiijijv=minv ,c -fll jvijv , (v )ljiv ,vAij0fjiijvminv , cll jvij-v , (v )l重复上述步骤，直到重复上述步骤，直到 被标上号或不再有顶点可标号为止。被标上号或不再有顶点可标号为止。如果如果

56、 得到标号，说明存在增广链，转入调整过程；如果得到标号，说明存在增广链，转入调整过程；如果未获得标号，标号过程已无法进行时，说明已是最大流。未获得标号，标号过程已无法进行时，说明已是最大流。调整过程调整过程令令其中调整量其中调整量 调整后去掉所有标号，对新的可行流调整后去掉所有标号，对新的可行流 重重新进行标号过程。新进行标号过程。调整过程为：在增广链的前向弧上加上调整量调整过程为：在增广链的前向弧上加上调整量，后向弧上减去调，后向弧上减去调整量整量，其他弧的流量不变这样可使总流量增加，其他弧的流量不变这样可使总流量增加，即，即tvtvtv*f+ijij-ijijijijijf +v ,vf

57、=f -v ,vfv ,vt=vl ijf v fv f找可行流找可行流给给S 标号标号( S， ) ) t 是否已是否已 标号标号 是否存在已标号是否存在已标号 但未检查的点但未检查的点 倒向追踪倒向追踪找出增广链找出增广链 令调整量令调整量求改进的可行流求改进的可行流+ijij-ijijijijijf +v ,vf = f -v ,vfv ,vt=vlf不存在关于不存在关于的增广链的增广链即为最大流即为最大流 i 已已 标号标号,但未检查但未检查 对对i 进行检查，并对进行检查，并对j 标号标号: 若，且，对若，且，对j 标号标号: ，ijv ,vAijijfcijv , (v )l ji

58、ijijv =minv ,c -fll 若，且，对若，且，对j 标号标号: ，jiv ,vAji0fij-v , (v )ljijivminv , cll 是是否否例例6 6 用标号法求所示网络图的最大流。弧旁的数是用标号法求所示网络图的最大流。弧旁的数是 。ijijc ,f121-v , (v )-v ,1l弧不满足标号条件弧不满足标号条件13v ,v（2，2）（2，1）（5，3）（4，3）（3，3）（5，1）（3，0）（1，1）（1，1）解：经检查，网络中的流是可行解：经检查，网络中的流是可行流，下面分析是否可以增加流量。流，下面分析是否可以增加流量。（）（） 标号过程：标号过程：先给先给

59、 标号标号 ；检查检查 ，在弧，在弧 上，上， 所以所以 则则 的标号的标号 3tsvsv ,svs1v ,vs1s1f =102121vminv,fmin 4,11ll2v（, ）（4, ）（2，2）（2，1）（5，3）（4，3）（3，3）（5，1）（3，0）（1，1）（1，1）检查检查 ，在弧，在弧 上，上， 给标号给标号 t（,+)（, 4) ) 在弧上在弧上给标号给标号32v ,v检查，在弧上，检查，在弧上， 所以所以 , ,给标号因已经标号，故进入调整过程给标号因已经标号，故进入调整过程4tv ,v（, ）2v24v ,v 422424vminv, c -fmin 1,11ll242

60、4f =3c =44v242v , (v )v ,1l（, ）4t4tf =303232vminv,fmin 1,11ll3v232-v , (v )-v ,1ltv（5，1）（4, ）（2，2）（2，1）（5，3）（4，3）（3，3）（3，0）（1，1）（1，1）t（, 4) )（, ）（, ）（2, ）（,+)（2 2） 调整过程：调整过程：取定增广链取定增广链前向弧上流量增加，后前向弧上流量增加，后向弧上流量减去，其他向弧上流量减去，其他不变，得可行流不变，得可行流在进入新的循环：在进入新的循环：给给 标号标号检查检查 给标号给标号检查，标号过程无法进检查，标号过程无法进行下去行下去所以