运筹学第六章图与网络分析(新)a管理精品资料.ppt

作业：P170171 6.3 6.4(c) 6.5 6.7(b) 第六章 图与网络分析,哥尼斯堡七桥问题 德国古城哥尼斯堡普雷格尔河七 桥问题：从任一桥头出发，依次走过每座 桥，每座桥只走一次，最后回到出发点。 一笔画问题,2. 中国邮递员问题 邮递员送信送报要走完全部所负责的街道，最后回到邮局，如何走路程最短？,第一节 图的基本概念 一、图的概念 1. 图（无向图） 图是由点与边组成的集合，记为：G=(V,E)，其中V，表示图G中点的集合，E表示图G中边的集合。图中点的个数记为p，称为图的阶；图中边的条数记为q。,2. 端点、关联边、相邻 若边e可以表示为e=（vi，vj)，则称vi和vj是边e的端点；边e称为点vi和vj的关联边。 若点vi、vj与同一条边关联，称点vi和vj相邻。 若边ei、ej有公共的端点，称边ei和ej相邻。,3. 环，多重边，简单图 如果边e的两个端点相重，称该边为环。 如果两个端点之间的边多于一条，称为多重边。无环、无多重边的图称为简单图。 4. 次，奇点，偶点，孤立点，悬挂点 与某一个点vi相关联的边的数目称为点vi的次。记为d(vi)。 次为奇数的点称为奇点，次为偶数的点称为偶点。 次为0的点称为孤立点。 次为1的点称为悬挂点。,.v6,5. 链，圈，连通图 图中由相邻的点和互不相同的边组成的交替序列称为链。 若链中的所有顶点也不相同，则该链称为路。 起点与终点重合的链称为圈。起点与终点重合的路称为回路。 若图中任意两个顶点之间都至少存在一条链，则称该图为连通图。,6. 完全图，偶图 若一个简单图中任意两点之间均有边相连，则称该图为完全图。 对含有n个顶点的完全图，其边数有 条。,如果图的顶点能分成两个互不相交的非空集合V1和V2 ，使在同一集合中任意两个顶点都不相邻，则称该图为偶图（或二分图）。 若偶图的顶点集合V1、V2之间的每一对不同顶点之间都有一条边相连，则称该图为完全偶图。在完全偶图中， V1若有m个顶点， V2有n个顶点，则其边数共有mn条。,7. 子图，部分图 对图G1= V1，E1 和图G2= V2，E2 ，若有 ，则称G1是G2的一个子图。 若有 ，则称G1是G2的一个部分图。,定理 ：在图G中，所有顶点次之和等于边数的两倍。即： 定理 ：在任一图中，奇点的个数必为偶数。,例：有八种化学药品，某些不能放入同一个仓库，用连线表示。见下图。 （v1) （ v2， v4，v7) （v3，v5) （v6，v8) 例：四色问题。,8. 同构 对图G1= V1，E1 和图G2= V2，E2 ，如果顶点集合V1与V2之间以及边的集合E1与E2之间都建立了一一对应关系，并且图G1的两顶点之间的边对应于图G2对应顶点的边，则称图G1与图G2是同构的。,9. 赋权图：对一个无向图G的每一条边（vi，vj) ，相应地有一个数wij，则称这样的图G为赋权图（也称网络图，记为N)，wij称为边（vi，vj) 上的权。,10. 一笔画问题 欧拉链：给定一个连通图G,若存在一条链，过每边一次且仅一次，则称这条链为欧拉链。 欧拉圈：若存在一个简单圈，过每边一次，则称这个圈为欧拉圈。 欧拉图：有欧拉圈的图称为欧拉图。 能一笔画的图一定是欧拉圈或含有欧拉链。 定理：连通的多重图G是欧拉图的充要条件是G中无奇点。 推论：连通的多重图G有欧拉链的充要条件是G中恰有两个奇点。,第二节 树图和图的最小部分树 树图：无圈的连通图称为树图，记为T(V,E)。 2-1 树的性质 性质1：任何树中必存在至少两个次为1的点（悬挂点）。 性质2：具有n个顶点的树的边数恰好为(n-1)条。 性质3：任何具有n个顶点、（n-1)条边的连通图是树。 2-2 图的最小部分树（最短树） 如果G1是G2的部分图，又是树图，则称G1是G2的部分树（或支撑树）。 G2的树枝总长最小的部分树称为该图的最小部分树。,定理1. 图中任一个点i，若j是与i相邻点中距离最近的，则边(i, j)必含在该图的最小部分树内。 推论： 把图的所有点分成V和 两个集合，则两集合之间连线的最短边一定包含在最小部分树内。,2-3 求最小部分树的破圈法和避圈法 1. 避圈法,2.破圈法 从网络图N中任取一回路，去掉这个回路中权数最大的一条边，得一子网络图N1。在N1中再任取一回路，再去掉回路中权数最大的一条边，得N2。如此继续下去，一直到剩下的子图中不再含回路止。该子图就是N的最小部分树。,例:某工厂内联结六 个车间的道路网如图 所示，已知每条道路 的长，要求沿道架设 联结六个车间的电话 线网，使电话线的 总长最小。,第三节 最短路问题 3-1 狄克斯特拉（标号）算法（dijkstra)： 令： dij 为相邻两点 vi 与 vj 的距离，若vi 与 vj不相邻，则令dij = ，显然，dii=0。 L1i 为从v1 到图中任一点vi 的最短距离。 狄克斯特拉（标号）算法步骤： （1）从v1点出发，将L11=0标在v1旁的小方框内，表示v1已经标号；,（2）找出与v1相邻的点中距离最小的一个，设为vr， 将L1r= L11+ d1r的值标注在点vr旁的小方框内，此时， vr也已经标号； （3）从已标号点出发，找出与已标号点相邻的所有未标号点vp，若有 则将L1p的值标在vp旁的小方框内，此时，点vp已得到标号； （4）重复第（3）步，直到vn得到标号。,作业： P172 6.11 6.13,修正狄克斯特拉（标号）算法： 步骤： 1. 对起点v1给予固定标号L(v1)=0，其余点为临时标号，并记为： (j=1,2.n) 2. 设vi是刚刚得到固定标号的点L(vi) ，修改与其相邻的临时标号点vj ：,3. 在与固定标号点相邻的临时标号点中选取具有最小标号的点vi给予固定标号，即: L(vi)=min T(vj) 返回第2步。 4. 当vn得到固定标号时，计算结束。 注： 固定标号L(vi)表示v1到vi的最短距离，临时标号T(vj)表示v1到vi距离的上界。,固定标号 临时标号 v1（0） v2（5） v3（2） v4（） v5（） v6（） v7（） 2. v1（0） v3（2） v2（5） v4（9） v5（） v6（6） v7（） 3. v1（0） v3（2） v2（5） v4（7） v5（12） v6（6） v7（） 4. v1（0） v3（2） v2（5） v4（7） v5（7） v7（12） v6（6） 5. v1（0） v3（2） v2（5） v5（7） v7（12） v6（6） v4（7） 6 v1（0） v3（2） v2（5） v7（10） v6（6） v4（7） v5（7） 7. v1（0） v3（2） v2（5） v6（6） v4（7） v5（7） v7（10）,Dijkstra算法仅适合于所有的权wij0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。例如下图中，根据Dijkstra算法，可以得出从v1到v2最短路权是2，但是这显然不对，因为从v1到v2的最短路是（v1,v3,v2）,权是-1。,2,v1,3,v3,v2,-2,下面介绍当赋权有向图中，存在负权弧时，寻求最短路的算法(Ford): 1.若点vi到点vj之间有一条弧，则令权数为dij，否则，令dij=+。 2.由于从vs到vj的最短路是从vs点出发，沿着这条路到某个点vi,再沿弧(vi,vj)到点vj。显然，从vs到vi必定是从vs到vj的最短路，否则从vs到vj的这条路将不是最短路。于是，从vs到vj的最短距离L(vs,vj)满足以下条件， L(vs，vj)=minL(vs，vi)+dij, i=1,p i,这个关系式L(vs，v1)L(vs，vp)可利用如下的递推公式求解 L(1)(vs，vj)=dsj ,j=1p L(t)(vs,vj)=minL(t-1)(vs，vi)+ dij,t=2,3 i 3.当计算到第K步时,若对一切的j=1p,有 L(k)(vs，vj)=L(k-1)(vs，vj) 则L(k)(vs，vj),j=1p,就是从vs到各点vj的最短路径。,设C是赋权函数有向图D中的一个回路。如果回路C的权S（C）是负数那么称C是D中的一个负回路。 可以证明以下的结论： 1.如果赋权有向图D不含有负回路，那么从vs到任一点的最短路至多包含P-2个中间点，并且必可取为简单路。 2.如果赋权有向图D不含有负回路，那么上述递推算法至多经过P-1次迭代必收敛，可以求出从vs到各个点的最短路权。 3.如果上述算法经过P-1次迭代，还存在在着某个j，使得L(p)(vs,vj)L(p-1)(vs,vj),那么D中含有负回路。这时，不存在从vs到vj的路（权无界）。,结论,例: 在如下图所示的赋权有向图中求从v1到各 点的最短路。 解:利用上述递推公式，将求解结果列出如下表所示。 可以看出，当t=4时，有： L(t)(vs,vj)=L(t-1)(vs,vj) j=18。因此，表中的最后一列，就是从v1到v1,v2,v8的最短路权。,1,1,1,1,1,1,2,3,3,5,5,2,2,3,6,7,8,dij,L(t)(vs,vj),为了求出从v1到各个点的最短路，一般采用反向追踪的方法：如果已知L(vs,vj),那么寻求一个点vk,使得L(vs,vk)+wkj=L(vs,vj),然后记录下(vk,vj)。再看L(vs,vk),寻求一个点vi,使得L(vs,vi)+wiK=L(vs,vk)依次类推，一直到达L(vs,v1)为止。这样，从vS到vj的最短路是（vs,vi,vk,vj）。 在本例中,由表知，L(v1,v8)=6,由于L(v1,v6)+d68=(-1)+7记录下v6 ,由于L(v1,v3)+d36=L(v1,v6),j记录下v3 ,由于L(v1,v1)+d13=L(v1,v3),于是，从v1到v8的最短路是(v1,v3,v6,v8)。,3-2 求任意两点间最短距离的矩阵算法(Floyd) 设邻接矩阵为D,计算D1=D+D, D2= D1 +D , D3= D2 +D , 。若Dm+1= Dm ，则Dm中的元素值即为各点间的最短距离。 Dk+1= Dk +D算法： 例4：,D1=D+D= + =,3-3 求中心 在一个连通图G中，设d(vi ,vj)为vi至vj的最短距离，令： 为点vi至点vj的最大距离,若G中的一点v*满足： 则称点v*为图G的中心。,3-4 求重心 在一个连通图G中，设w(vi)为点vi的权重，令 表示将点vi的物资运到点vj的总运输量。 若满足 则称点 为图G的重心。,例：上例中， v1， v2， v3，v4， v5， v6， v7为七个村子，现决定要办一所小学，已知各村学生人数分别为： v130， v240， v325， v420， v550，v660, v760， 问小学应建在那个村子，使学生上学走的路程最短。 解：计算见表。 小学应建在v6村。,例：下图为一大型企业区域交通网络图。设点v1v7为某公司的7个分厂，边表示经过测绘的交通路线，边旁的数字表示两点之间的距离。现该企业欲修建正规道路使各分厂互通，并欲在某一分厂建一俱乐部。问如何选择交通路线来修建正规道路既保证各分厂畅通，又使道路总长度最短？俱乐部应建在那个分厂才能使离该俱乐部最远的分厂的职工所走的路程最短？,解：显然，第一个问题就是求最短树问题。第二个问题就是求中心问题。 用避圈法或破圈法求出最小部分树见图。,先用公式 计算d(vi)，见下表： 再用公式 计算d(v*)，由表可知，应将俱乐部建在分厂v2或v6。,求中心的步骤： 1. 求出网络中任意两点之间的最短距离； 2.求出各点到其它点的最远距离； 3.从这些最远距离中找出最短的距离所在点即为中心。,例：仍以上例为例，现准备在该地区建一个中心仓库以贮存分发给各分厂的原材料。已知各分厂每月的原材料需求量见下图。问中心仓库应建在那个分厂，能使每月总的运输量最小。 解：由计算重心的公式： 既可算得应把中心仓库建在v6分厂，每月的最小运输量为122000。,补： 中国邮路问题 首先判断是否欧拉图,若是就可归结为一笔画问题；否则，将图中奇点两两相连，变为欧拉图，连线为邮递员重复走的路程。 邮递员重复所走路程最短的条件： 奇点两两之间的连线最短。 （1） 每条边上最多重复一次； （2） 在图的每个回路上，有重复的边的长度不超过总长的一半。,作业：P173P174 6.15(c) 6.17 6.18 6.19(b) 6.21 第四节 网络最大流 4-1 网络最大流的有关概念 1. 有向图与容量网络 有向图：点与弧的集合，记作D(V，A)。 弧(vi，vj)标明方向是从点vi指向点vj。 弧(vj，vi)则相反。,容量网络：对网络上的每条弧(vi，vj)都给出一个最大的通过能力，称为该弧的容量，记为c(vi，vj)或简记为cij。容量网络记为D(V，A，C) 容量网络的点通常分为三类： 发点vs（始点）、收点vt（终点）、中间点vi 。 网络最大流：网络中从发点到收点之间允许通过的最大流量。 注：多发点和多收点的处理。,2. 流与可行流 （网络）流：加在网络各条弧上的一组负载量。弧(vi，vj)上的流量记为f(vi，vj)或fij。 可行流：在容量网络D(V，A，C)上，满足下列条件的一组流称为可行流： （1）容量限制条件，对所有的弧有 （2）中间点平衡条件 若以v(f)表示网络从vsvt的流量，则有：,最简单的可行流是零流。 网络最大流问题：在满足容量限制条件和中间点平衡条件下，使网络流v(f)值达到最大。或求使网络流v(f)实现最大值的可行流。 最大流问题的线性规划模型,4-2 割集和割量 割集（截集）：将网络图中的点分割成V和 两个集合，并且有sV, t ，则称弧集（V, )为网络的一个割集。割集中各弧的容量之和称为割量，记为C(V, )。,例：图6-16中的所有割集及其割量见下表。,4-3 最大流最小割定理 增广链：在网络图中找出一条从始点s到终点t的链，定义： 所有从s指向t(s t)的弧称作正向弧(记作+)； 所有从t指向s(t s)的弧称作反向弧(记作-)。 若在该链中： 对所有的正向弧都有f0（称为非零流弧）， 则称该链为网络的一条增广链。,在增广链中，令： 显然，0，再令： 此时， 仍是一个可行流，但其流量比 增加了。,结论：只要网络图中存在增广链，就可使网络的流量增加。只有当网络中不存在增广链时，才得到网络的最大流量。 定理2 （最大流最小割定理）网络的最大流等于它的最小割集的容量。,4-4 求网络最大流的标号法 （Ford-Fulkerson标号法）,例：求下列网络的最大流。 解：给出一个初始的可行流xij=0,找从1到7的增广链,=8,=3,=1,=8,调整量：1 = min8,3,1,8=1,调整流量，f=1。继续找从1到7的增广链,=7,=1,=6,=9,调整量：2 = min7,1,6,9=1,调整流量，f=1+1=2。继续找从1到7的增广链,=7,=5,=8,调整量：3 = min7,5,8=5,调整流量，f=1+1+5=7。继续找从1到7的增广链,=6,=3,=4,调整量：4 = min6,4,4,3=3,=4,调整流量，f=1+1+5+3=10。继续找从1到7的增广链,=3,=1,=3,调整量：5 = min3,1,3,7=1,=7,调整流量，f=1+1+5+3+1=11。继续找从1到7的增广链,已找不到从1到7的增广链，已求得最大流为f=11， 最小割集为（2,5）（3,4）（3,6）。,第五节 最小费用流（最小费用最大流） 最小费用流可以这样描述：设网络有n个点，fij为弧(i，j)上的流量，cij为该弧的容量，bij为在弧(i，j)上通过单位流量时的费用，si代表第i点的可供量或需求量，当i为发点时， si 0，i为收点时， si 0，i为中转点时，si =0。当网络供需平衡(si=0)时，将各发点物资调运到各收点(或从各发点按最大流量调运到各收点)，使总调运费用最小。可归结为下线性规划模型：,求最小费用流时，一方面仍通过寻找增广链来调整流量，并判别是否达到了最大流量，但另一方面为了保证每步调整的流量花的费用最少，需要找出每一步费用最小的增广链，以保证最终给出的流量（包括最大流)也是费用最少的。,设b(f)为可行流f的费用，沿增广链调整后的流量为f (f)，相应费用为b(f)，有： 称比值b(f)/最小，也即调整单位流量花费最小的增广链为费用最小的增广链。,若将每条弧可能作为正向弧或反向弧出现时，通过该弧一单位流量的费用在该弧旁作为权数标注，则寻找费用最小的增广链，又可转化为一个求发点至收点的最短路问题。 因此求最小费用流的步骤可归结为： 第一步 从零流f0开始。f0是可行流，也是相应的流量为零时费用最小的。,第二步 对可行流fk构造加权网络W(fk)，方法是： (1)对0fijcij的弧(i，j)，当其为正向弧时，通过单位流的费用为bij，为反向弧时，相应费用为 -bij。故在i和j点间分别给出弧(i，j)和(j，i)其权数分别为bij和-bij。 (2)对fij=cij的弧(i，j)，因该弧流量已饱和，在增广链中只能作为反向弧。故在W(fk)中只画出弧(j，i)，其权数值为-bij。 (3)对fij=0的弧(i，j)，在增广链中该弧只能为正向弧，故在W(fk)中只给出弧(i，j)，其权数值为bij。,第三步 在加权网络W(fk)中，寻找费用最小的增广链，也即求从st的最短路。并将该增广链上流量调整至允许的最大值，得到一个新的流量fk+1(fk)。 第四步 重复第2、3