《运筹学图与网络分析 (2)精品文稿.ppt》由会员分享，可在线阅读，更多相关《运筹学图与网络分析 (2)精品文稿.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹学图与网络分析OR3 1第1页，本讲稿共42页OR3 2第六章 图与网络分析AB CD E引论:哥尼斯堡七桥问题 ABC DA Bc D第2页，本讲稿共42页OR3 3铁路交通图此图是我国北京此图是我国北京,上海等十个上海等十个城市间的交通图 城市间的交通图,反映了这反映了这十个城市间的铁路分布情况 十个城市间的铁路分布情况.点表示城市点表示城市,点间的连线表示点间的连线表示两个城市间的铁路线两个城市间的铁路线.诸如此类问题还有电话线分诸如此类问题还有电话线分布图或煤气管道分布图等 布图或煤气管道分布图等.北京济南徐州青岛南京上海连云港 郑州武汉天津第3页，本讲稿共42页OR3 4球队比赛
2、图 五个球队比赛,比过的两个队之间用连线相连，还没有比赛的队之间没有连线v5v4v3v2v1第4页，本讲稿共42页OR3 56.1 图的基本概念n n 图是由点和线构成的。点代表所研究的对象，线表示对象 图是由点和线构成的。点代表所研究的对象，线表示对象间的关系。间的关系。n n 1 1、图的分类：无向图，有向图、图的分类：无向图，有向图n n 无向图：由 无向图：由点 点和 和边 边所组成的图。表示为 所组成的图。表示为G=(V,E).G=(V,E).n n 有向图：由 有向图：由点 点和 和弧 弧所组成的图。表示为 所组成的图。表示为D=(V,A)D=(V,A)点的集合用 点的集合用V V
3、表示，表示，V=V=v vi i 2 2、图上的基本概念：、图上的基本概念：（1 1）边：图中不带箭头的连线叫做边 边：图中不带箭头的连线叫做边(edge)(edge)，边的集合记为，边的集合记为E=E=e ej j，一条边可以用两点，一条边可以用两点 v vi i,v,vj j 表示 表示,e,ej j=v vi i,v,vj j.弧：图中带箭头的连线叫做弧 弧：图中带箭头的连线叫做弧(arc),(arc),弧的集合记为 弧的集合记为A A，A=A=a ak k,一条弧也是用两点表示，一条弧也是用两点表示，a ak k=v vi i,v,vj j,弧有方向：弧有方向：v vi i为始点，为始
4、点，v vj j为终点 为终点第5页，本讲稿共42页OR3 6n n 例 例1.1.v 7v 1 v 2v 3v 4e 1e 2e 3e 4e 5e 6e 7a 9v 1v 2v 3v 4v 5v 6a 1a 2a 8a 4a 3a 5a 6a 7a 10环：两端点相同的边。环：两端点相同的边。多重边：若两点之间有多于一条边，则称这些边为多 多重边：若两点之间有多于一条边，则称这些边为多重边。重边。简单图：无环、无多重边的图。简单图：无环、无多重边的图。多重图：无环，但允许有多重边的图。多重图：无环，但允许有多重边的图。e7第6页，本讲稿共42页OR3 7n n（2 2）次：以点）次：以点u
5、u为端点的边的条数，叫做点 为端点的边的条数，叫做点u u的次。的次。悬挂点：次为 悬挂点：次为1 1的点叫做悬挂点；的点叫做悬挂点；孤立点：次为 孤立点：次为0 0的点叫做孤立点；的点叫做孤立点；奇点：次为奇数则称奇点；奇点：次为奇数则称奇点；偶点：次为偶数则称偶点。偶点：次为偶数则称偶点。基本定理：基本定理：1 1、图、图G=(V,E)G=(V,E)中，所有点的次之和是边数的两倍，即 中，所有点的次之和是边数的两倍，即2 2、任一图中，奇点的个数为偶数。、任一图中，奇点的个数为偶数。第7页，本讲稿共42页OR3 8（3 3）链：点边交替序列称为链；）链：点边交替序列称为链；圈：首尾相连的链
6、称为圈；圈：首尾相连的链称为圈；初等链：链中各点均不同的链；初等链：链中各点均不同的链；初等圈：圈中各点均不同的圈；初等圈：圈中各点均不同的圈；简单链：链中边均不同的链；简单链：链中边均不同的链；简单圈：圈中边均不同的圈。简单圈：圈中边均不同的圈。（4 4）连通图：任意两点之间至少有一条链的图。）连通图：任意两点之间至少有一条链的图。连通分图：对不连通的图，每一连通的部分称为一个连通 连通分图：对不连通的图，每一连通的部分称为一个连通分图。分图。支撑子图：对 支撑子图：对G=(V,E)G=(V,E)，若，若G G=(V=(V,E,E)，使，使V V V V，E E包含于 包含于E E，则，则G
7、 G是 是G G的一个支撑子图。的一个支撑子图。赋权图：在图中，如果每一条边（弧）都被赋予一个权值 赋权图：在图中，如果每一条边（弧）都被赋予一个权值w wij ij，则称图，则称图G G为赋权图。为赋权图。（5 5）路：在有向图中，如果链上每条弧的箭线方向与链行）路：在有向图中，如果链上每条弧的箭线方向与链行进方向相同，则称之为路。进方向相同，则称之为路。回路：首尾相接的路称回路 回路：首尾相接的路称回路第8页，本讲稿共42页OR3 96.2 树与最小生成树n n 1 1、树的概念与性质、树的概念与性质树：树：无圈无圈的 的连通图 连通图称为树。称为树。定理：定理：定量定量33：设图：设图G
8、=G=（V,E)V,E)是一个树，是一个树，p(G)2,p(G)2,则 则GG中至少 中至少有两个悬挂点。有两个悬挂点。定量定量44：图：图G=G=（V,E)V,E)是一个树的充要条件是是一个树的充要条件是GG不含圈，不含圈，且恰有 且恰有p p 11条边。条边。定量定量55：图：图G=G=（V,E)V,E)是一个树的充要条件是 是一个树的充要条件是GG是连通图，是连通图，并且并且q(G)=p(G)-1.q(G)=p(G)-1.定量定量6 6：图：图G=G=（V,E)V,E)是一个树的充要条件是任意两个顶是一个树的充要条件是任意两个顶点之间恰好有一条链。点之间恰好有一条链。第9页，本讲稿共42
9、页OR3 10n n22、图的支撑树、图的支撑树 支撑树：设支撑树：设T=(V,ET=(V,E)是图是图G=(V,E)G=(V,E)的支撑子图，的支撑子图，如果如果TT是一个树，则称是一个树，则称TT为为GG的支撑树。的支撑树。定理定理7 7：图：图G G有支撑树的充要条件是图有支撑树的充要条件是图GG是连通是连通的。的。n n求支撑树的方法：求支撑树的方法：破圈法：即任取一个圈，从圈中去掉一条边，对破圈法：即任取一个圈，从圈中去掉一条边，对余下的图重复这个步骤，直至图中不含圈为止。余下的图重复这个步骤，直至图中不含圈为止。避圈法：在图中每次任取一条边，与已经取得的任 避圈法：在图中每次任取一
10、条边，与已经取得的任何一些边不够成圈，重复这个过程，直到不能进行为 何一些边不够成圈，重复这个过程，直到不能进行为止。止。第10页，本讲稿共42页OR3 1133、最小支撑树、最小支撑树最小支撑树：当一个连通图的所有边都被赋权，则取不 最小支撑树：当一个连通图的所有边都被赋权，则取不同边构成的支撑树具有不同的总权数，其中总权数最 同边构成的支撑树具有不同的总权数，其中总权数最小的支撑树称为最小支撑树。小的支撑树称为最小支撑树。求最小支撑树的方法：求最小支撑树的方法：破圈法：在连通图中任取一个圈，去掉一条权数最破圈法：在连通图中任取一个圈，去掉一条权数最大的边，在余下的图中重复上述步骤，直至无圈
11、为大的边，在余下的图中重复上述步骤，直至无圈为止。止。避圈法：将连通图所有边按权数从小到大排序，避圈法：将连通图所有边按权数从小到大排序，每次从未选的边中选一条权数最小的边，并使之每次从未选的边中选一条权数最小的边，并使之与已选的边不能构成圈，直至得到最小支撑树。与已选的边不能构成圈，直至得到最小支撑树。第11页，本讲稿共42页OR3 12避圈法的基本步骤P259n n 第一步：令i1，E0空集。n n 第二步：选一条边eiE Ei-1,使ei是使（V,Ei-1e）不含圈的所有边e（e E Ei-1）中权最小的边。令EiEi-1 ei,如果这样的边不存在，则T=(V,Ei-1)是最小树。第三步
12、：把i换成i1，转入第2步。第12页，本讲稿共42页OR3 136.3 最短路问题引例引例:单行线交通网：单行线交通网：v v1 1到 到v v8 8使总费用最小的旅行路线。使总费用最小的旅行路线。最短路问题的一般描述：最短路问题的一般描述：对 对D=D=（V V，A A），），a=a=（v vi i，v vj j），），w w（a a）=w=wij ij，P P是 是v vs s到 到v vt t的路，定义路 的路，定义路P P的权是 的权是P P中所有弧的权的和，记 中所有弧的权的和，记为 为w w（P P），则最短路问题为：），则最短路问题为：V 2(v 1,6）路P0的权称为从vs到v
13、t的距离，记为：d（vs，vt）最短路：赋权有向图 最短路：赋权有向图D=D=（V V，A A）中，从始点到终点的）中，从始点到终点的权值最小的路称为最短路。权值最小的路称为最短路。第13页，本讲稿共42页OR3 14 最短路算法 最短路算法n n Dijkstra Dijkstra算法 算法：有向图：有向图，wij0 wij0n n 一般结论：一般结论：Dijkstra Dijkstra算法基本思想 算法基本思想:采用标号法 采用标号法:P:P标号和 标号和T T标号 标号 P P 标号 标号：已确定出最短路的节点：已确定出最短路的节点(永久性标号 永久性标号)。T T 标号 标号：未确定出
14、最短路的节点，但表示其距离的上限：未确定出最短路的节点，但表示其距离的上限(试探性标号 试探性标号)。算法的每一步都把某一点的 算法的每一步都把某一点的T T标号改为 标号改为P P标号直至改完为止 标号直至改完为止.S Si i：P P标号节点的集合。标号节点的集合。第14页，本讲稿共42页OR3 15Dijkstra算法的基本步骤：n n 1:1:给 给v vs s以 以P P标号 标号,P(v,P(vs s)=0,)=0,其余各点均给 其余各点均给T T标 标 号 号,T(v,T(vi i)=+)=+2:2:若 若v vj j 点为刚得到 点为刚得到P P 标号的点 标号的点,考虑这样的
15、点 考虑这样的点v vj,j,(v(vi i,v,vj j)E,E,且 且 v vj j为 为T T标号 标号.3:3:对 对v vj j的 的T T标号进行如下更改 标号进行如下更改:4:4:比较所有具有 比较所有具有T T标号的点 标号的点,把最小者改为 把最小者改为P P标号 标号.n n 当存在两个以上最小值时 当存在两个以上最小值时,可同时改为 可同时改为P P标号 标号.n n 若全部改为 若全部改为P P标号 标号,则停止 则停止.否则转回 否则转回(2).(2).第15页，本讲稿共42页OR3 16用Dijkstra算法求图中v1到v8的最短路第16页，本讲稿共42页OR3 1
16、7最短路问题的算法：Bellman算法n n适用范围：有向图，且图中有适用范围：有向图，且图中有wijwij00。n n假设前提：任意两点假设前提：任意两点vvii,v,vjj之间都有一条弧。之间都有一条弧。（若无，则添加一条虚拟的弧，且其权值为（若无，则添加一条虚拟的弧，且其权值为。）。）n n公式来源分析：公式来源分析：第17页，本讲稿共42页OR3 18n n基本思路：基本思路：用用逐次逼近逐次逼近来求网络中的最短路：每次求出从始来求网络中的最短路：每次求出从始点到网络中其余各点点到网络中其余各点有限制有限制的最短路。的最短路。若第一次逼近即得最短路，则限制其最短路只有若第一次逼近即得最
17、短路，则限制其最短路只有一条弧，其路长记为一条弧，其路长记为；若第二次逼近即得最短路，则限制其最短路不超若第二次逼近即得最短路，则限制其最短路不超过两条弧，其路长记为过两条弧，其路长记为；依此类推，第依此类推，第kk次逼近得最短路，则限制其不超过次逼近得最短路，则限制其不超过kk条弧。条弧。一般的，最多逼近一般的，最多逼近n-1n-1次即得到最短路。次即得到最短路。第18页，本讲稿共42页OR3 19n n为了求得公式的解可以运用以下公式：为了求得公式的解可以运用以下公式：n n令：令：第19页，本讲稿共42页OR3 20n n基本步骤：基本步骤：n n11、令、令，其中，若，其中，若vv11
18、与与vvjj间没弧，则记间没弧，则记ww1j1j=+=+。n n22、当计算到第当计算到第kk步时，若有步时，若有 成立，则成立，则停止计算。停止计算。即为从即为从vv11到各点的最短路。到各点的最短路。第20页，本讲稿共42页OR3 21举例：求v1到各点的最短路第21页，本讲稿共42页OR3 22计算过程见下表：0 2 5-30-2 4064 00-3 0472 03-1 0025-3020-3611020-36615020-3361410020-336910020-336910第22页，本讲稿共42页OR3 23n n 当计算到第六步时，计算结果与第五步相同，则表中第六列的数字分别表示点
19、v1到其它各点的最短路。n n 寻找最短路径的方法：反向追踪法。第23页，本讲稿共42页OR3 24第24页，本讲稿共42页OR3 256.4 最大流问题n n 1、掌握可行流、增广链、截集、截量等基本概念n n 2、掌握基本定理8及其证明n n 3、掌握求最大流的标号法第25页，本讲稿共42页OR3 26n n 引例：如下输水网络，南水北调工程，从vs s到vt t送水，弧旁数字前者为管道容量，后者为现行流量，如何调运输水最多？v sv tv 2v 1v 4v 3(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)第26页，本讲稿共42页OR3 27最大
20、流问题的基本概念n n 1、容量网络n n 如果有向连通网络图D=(V,A)的每一条弧（vi，vj）上都被赋予一个非负数，以表示通过该弧的最大通行能力，称为弧的容量，则称这样的网络为容量网络，记作D=(V,A,C)。第27页，本讲稿共42页OR3 28n n 2、流n n 在D=(V,A,C)中，如果实际通过每一弧（vi，vj）的流量是fij，则称集合f=fij为网络D=(V,A,C)上的一个流。第28页，本讲稿共42页OR3 2933、可行流、可行流 对给定的对给定的D=(V,A,C)D=(V,A,C)，把满足下列两个条件，把满足下列两个条件11），），22）的流）的流称为可行流。称为可行流
21、。11）容量限制条件）容量限制条件:对 对DD中的每一条弧（中的每一条弧（vvi i，vvjj），有，有0 f0 fij ij ccij ij;22）平衡条件）平衡条件:对中间点对中间点vvi i，流入量等于流出量，流入量等于流出量,即即;对发点 对发点vvss，有，有;对收点对收点v vtt，有，有.是可行流的流量，是发点的净输出量，是收点的净入是可行流的流量，是发点的净输出量，是收点的净入量。量。注意：任一注意：任一D=(V,A,C)D=(V,A,C)都存在可行流。如零流就是一个可行 都存在可行流。如零流就是一个可行流。如果 流。如果D=(V,A,C)D=(V,A,C)中没有给出弧上的流量
22、中没有给出弧上的流量ffijij，可认为，可认为f fijij00。第29页，本讲稿共42页OR3 30n n44、最大流、最大流 n n使得从网络发点到收点得总流量（使得从网络发点到收点得总流量（WW）达到最）达到最大得可行流大得可行流f=f=ffijij称为最大流。称为最大流。n n最大流问题就是求一个流最大流问题就是求一个流f=f=ffijij使其流量使其流量 达到最大，并且满足：达到最大，并且满足：n n注意：寻求网络中的最大流就相当于求线性规注意：寻求网络中的最大流就相当于求线性规划模型的最优解。划模型的最优解。第30页，本讲稿共42页OR3 31n n5.5.截集、截量、最小截量截
23、集、截量、最小截量n n截量：截集（截量：截集（，）中所有弧的容量之和称为）中所有弧的容量之和称为该截集的截量，记为该截集的截量，记为cc（，）.n n最小截集：在最小截集：在D=(V,A,C)D=(V,A,C)的所有截集中，截量最的所有截集中，截量最小的截集称为最小截集，记为小的截集称为最小截集，记为()()。第31页，本讲稿共42页OR3 32n n 注意：容量网络图D的截集不是唯一的，截集个数是有限的。如果在图D中把任何一个截集中的弧丢掉，那么从发点就不能通往收点。所以，截集是从发点到收点的必经之道。从而，有任何一个可行流的流量都不会超过任意截集的截量。第32页，本讲稿共42页OR3 3
24、3n n 6、增广链n n 在容量网络D=(V,A,C)中，若 为网络中从vs到vt的一条链，给链 定方向为从vs到vt，上与 同方向的弧称为前向弧，与 反方向的弧称为后向弧，前向弧和后向弧的集合分别用 和 来表示。设 是一个可行流，如果满足：则称 为从vs到vt的（关于f的）增广链。第33页，本讲稿共42页OR3 34n n 增广链的实际意义：沿着这条链从vs 到 vt输送的流，还有潜力可挖，只需按照定理证明中的调整方法，就可以把流量提高；调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。这样，就得到了一个寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的增广链，若存在，则
25、可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的增广链时就的得到了最大流。第34页，本讲稿共42页OR3 35n n 7、最大流量最小截量定理n n 定理8：可行流 是最大流的充要条件是不存在从vs到vt的关于 的增广链。n n 重要结论：任一容量网络D=(V,A,C)中，最大流的流量等于最小截集的截量。可行流f 是最大流的充分必要条件是不存在从 到 可行流f 是最大流的充分必要条件是不存在从 到 可行流f 是最大流的充分必要条件是不存在从 第35页，本讲稿共42页OR3 36定理88可行流 是最大流的充要条件是不存在从vs到vt的关于 的增广链证
26、明：先证明：若可行流 先证明：若可行流 是最大流，则 是最大流，则 中不存在关于 中不存在关于 的增广链。的增广链。若 若 是最大流，设 是最大流，设D D 是 是 的增广链。令 的增广链。令：由增广链的定义可知 由增广链的定义可知，令：，令：不难验证该流是一个可行流，且其最大流量比原流大 不难验证该流是一个可行流，且其最大流量比原流大。则，证明原可行流不是最大流，与假设矛盾。则，证明原可行流不是最大流，与假设矛盾。第36页，本讲稿共42页OR3 37再证明：若再证明：若DD中不存在关于中不存在关于 的增广链，则该流是最的增广链，则该流是最大流。大流。利用下面的方法来定义利用下面的方法来定义V
27、V1:1:第37页，本讲稿共42页OR3 38求最大流的方法：标号法n n方法很简单：首先找到一条增广链，沿此进行最大方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链可能调整，再找增广链，再调整，直到没有增广链为止。为止。如何找增广链？如何找增广链？如何调整？如何调整？n n设已有一个可行流设已有一个可行流ff（若网络中没有给定（若网络中没有给定f f，则可以设，则可以设ff是是零可行流），通过标号过程来找到增广链，通过调整零可行流），通过标号过程来找到增广链，通过调整过程来对增广链上的流量进行调整。过程来对增广链上的流量进行调整。n n第一步第一步 标
28、号过程，通过标号来寻找可增广链；标号过程，通过标号来寻找可增广链；n n 第二步 第二步 调整过程，沿可增广链调整 调整过程，沿可增广链调整f f，以增加流量。，以增加流量。第38页，本讲稿共42页OR3 39标号法的基本方法介绍1.标号过程n n 在这个过程中，网络中的每个标号点的标号由两个标号组成：n n 第一个标号表明该点的标号是从哪一点得到的，以便找到增广链；n n 第二个标号是为确定增广链上的调整量用的。第39页，本讲稿共42页OR3 40标号过程n n11）给发点以标号（）给发点以标号（00，+）。n n22）选择一个已标号的顶点）选择一个已标号的顶点vvii，对于，对于vvi i
29、的所有的所有未给标未给标号的邻接点号的邻接点按下列规则处理：按下列规则处理：n n若弧（若弧（v vii,v,vjj)上上,f,fijijccijij，则令，则令l(vl(vj j)minl(vminl(vii),c),cij-ij-ffijij，并给，并给v vjj以标号（以标号（vvii，l(vl(vj j)）。）。n n若弧（若弧（vvjj，v vii）上）上,f,fji ji0 0，则令，则令l(vl(vjj)minl(vminl(vii),f),fji ji 并给并给vvj j以标号（以标号（vvii，l(vl(vj j)）。）。n n重复第重复第22）步，直到收点被标号或不再有顶点
30、可标）步，直到收点被标号或不再有顶点可标号时为止。若收点得到标号，说明存在增广链，号时为止。若收点得到标号，说明存在增广链，转调整过程。若收点未获得标号，标号过程已无转调整过程。若收点未获得标号，标号过程已无法进行时，说明法进行时，说明ff已是最大流。已是最大流。第40页，本讲稿共42页OR3 41调整过程n n11）按上一步的第一个标号用反向追踪法找）按上一步的第一个标号用反向追踪法找出增广链。出增广链。n n22）令调整量）令调整量 l(vl(vtt)，且令：，且令：n n然后去掉所有标号，回到标号过程，对可行然后去掉所有标号，回到标号过程，对可行流流 重新标号。重新标号。第41页，本讲稿共42页OR3 42举例1：解水网最大流问题第42页，本讲稿共42页