运筹学-图与网络模型以及最小费用最大流.ppt

Chapter11 图与网络分析图与网络分析(Graph Theory and Network Analysis)图与网络的基本概念与模型图与网络的基本概念与模型最短路问题最短路问题最小生成树问题最小生成树问题最大流问题最大流问题最小费用最大流问题最小费用最大流问题本章主要内容：本章主要内容：本章主要内容：本章主要内容：.图与网络的基本概念与模型图与网络的基本概念与模型 长江汉江武昌武昌汉口汉口汉阳汉阳您能从武汉理工大学出发走过您能从武汉理工大学出发走过每座桥且只走一次然后回到学每座桥且只走一次然后回到学校吗校吗?2.近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名这就是著名的的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Euler1736年证明了不可能存在这样年证明了不可能存在这样的路线。的路线。图与网络的基本概念与模型图与网络的基本概念与模型KnigsbergKnigsberg桥对应的图桥对应的图桥对应的图桥对应的图3.图与网络的基本概念与模型图与网络的基本概念与模型图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。直，对于反映对象之间的关系并不是重要的。图的定义图的定义图的定义图的定义(P230)P230)P230)P230)若用点表示研究的对象，用边表示这些对象之间的联系，则图若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：可以定义为点和边的集合，记作：其中其中:V点集点集 E边集边集 图图G区别于几何学中的图。这里只关心图中有多少个点以及哪区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。些点之间有连线。4.图与网络的基本概念与模型图与网络的基本概念与模型(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示。表示。5.11图与网络的基本概念图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈图图11-3 如果我们把上面例子中的如果我们把上面例子中的“相互认识相互认识”关系改为关系改为“认识认识”的关系，那么只用两点之间的联线就很难刻画他们之间的的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入关系了，这是我们引入一个带箭头的联线，称为弧一个带箭头的联线，称为弧。图。图11-311-3就是一个反映这七人就是一个反映这七人“认识认识”关系的图。相互认识用两条反关系的图。相互认识用两条反向的弧表示。向的弧表示。6.图与网络的基本概念与模型图与网络的基本概念与模型定义定义:图中的点用图中的点用v v表示，边用表示，边用e e表示。对每条边可用它所表示。对每条边可用它所连接的点表示，记作：连接的点表示，记作：e e1 1=v=v1 1,v,v1 1;e;e2 2=v=v1 1,v,v2 2;v3e7e4e8e5e6e1e2e3v1v2v4v5 端点端点端点端点,关联边关联边关联边关联边,相邻相邻相邻相邻若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。若点。若点vi、vj与同一条边关与同一条边关联，称点联，称点vi和和vj相邻；若边相邻；若边ei和和ej具具有公共的端点，称边有公共的端点，称边ei和和ej相邻相邻。7.图与网络的基本概念与模型图与网络的基本概念与模型 环环环环,多重边多重边多重边多重边,简单图简单图简单图简单图如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如右图中边。如右图中边e1为环。如果两个点为环。如果两个点之间多于一条，称为之间多于一条，称为多重边多重边，如右图，如右图中的中的e4和和e5，对无环、无多重边的图，对无环、无多重边的图称作称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v58.图与网络的基本概念与模型图与网络的基本概念与模型 链，圈，连通图链，圈，连通图链，圈，连通图链，圈，连通图(P231)(P231)(P231)(P231)图中某些点和边的交替序列，若其图中某些点和边的交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意Vi-1,Vi 和和vi+1均相邻称为均相邻称为链链。用。用表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作起点与终点重合的链称作圈圈。如果。如果每一对顶点之间至少存在一条链，每一对顶点之间至少存在一条链，称这样的图为称这样的图为连通图连通图，否则称，否则称图不图不连通连通。9.图与网络的基本概念与模型图与网络的基本概念与模型 网络（赋权图网络（赋权图网络（赋权图网络（赋权图）(P232)(P232)设图设图G（V，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标wij，wij称为边称为边(vi,vj)的权的权,赋予权的图赋予权的图G称为称为网络网络(或赋权图）。或赋权图）。权权可以代表距离、费用、通过能力可以代表距离、费用、通过能力(容量容量)等等。等等。端点无序的赋权图称为端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有有向网络。向网络。91020157141925610.图与网络的基本概念与模型图与网络的基本概念与模型 主要概念主要概念主要概念主要概念(p231-p232)(p231-p232)无向图无向图：由：由点和边构成的图，记作点和边构成的图，记作G=（V，E）。）。有向图有向图：由：由点和弧构成的图，记作点和弧构成的图，记作D=（V，A）。）。连通图连通图：对：对无向图无向图G，若，若任何任何任何任何两个不同的点之间，至少存在一条链，则两个不同的点之间，至少存在一条链，则G为连通图。为连通图。回路回路：若：若路的第一个点和最后一个点相同，则该路为回路。路的第一个点和最后一个点相同，则该路为回路。赋权图赋权图：对：对一个无向图一个无向图G的每一条边的每一条边(vi,vj)，相应地有一个数，相应地有一个数wij，则称，则称图图G为赋权图，为赋权图，wij称为边称为边(vi,vj)上的权。上的权。网络网络：在：在赋权的有向图赋权的有向图赋权的有向图赋权的有向图D D中指定一点，称为发点，指定另一点称为收点，中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，中的每一条弧的赋权数称为弧的容量，D就就称为网络。称为网络。11.最短路问题最短路问题如何用最短的线路将三部电话连起来？如何用最短的线路将三部电话连起来？此问题可抽象为设此问题可抽象为设ABC为等边三角形，连接三顶点为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如线者显然是二边之和（如ABAC）。）。ABC12.最短路问题最短路问题ABCP但若增加一个周转站（新点但若增加一个周转站（新点P），连接），连接4点的新网络的最短点的新网络的最短路线为路线为PAPBPC。最短新路径之长。最短新路径之长N比原来只连三点比原来只连三点的最短路径的最短路径O要短。这样得到的网络不仅比原来节省材料，要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。而且稳定性也更好。13.最短路问题最短路问题问题描述：问题描述：问题描述：问题描述：要求：要求：就是从给定的网络图中找出一点到各点或任意两就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应最短路的问题。因此这类问题在生产实际中得到广泛应用。用。14.最短路问题最短路问题例例例例 渡河游戏渡河游戏渡河游戏渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。以用求最短路方法解决。15.最短路问题最短路问题定义：定义：定义：定义：1）人）人M（Man），狼），狼W（Wolf），），羊羊G（Goat），），草草H（Hay）2）点点 Vi 表示河岸的状态表示河岸的状态3）边边 ek 表示由状态表示由状态 vi 经一次渡河到状态经一次渡河到状态 vj 4）权权边边 ek 上的权定为上的权定为 1我们可以得到下面的加权有向图我们可以得到下面的加权有向图：16.最短路问题最短路问题状态说明：状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G)此游戏转化为在下面的二部图中求从此游戏转化为在下面的二部图中求从 v v1 1 到到 u u1 1 的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u117.最短路问题最短路问题求最短路有两种算法求最短路有两种算法:狄克斯屈拉狄克斯屈拉(Dijkstra)（双标号）算法（双标号）算法 逐次逼近算法逐次逼近算法最短路问题：最短路问题：对一个赋权的有向图对一个赋权的有向图D中的指定的两个点中的指定的两个点Vs和和Vt找找到一条从到一条从 Vs 到到 Vt 的路，使得这条路上所有弧的权数的总和最小，的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从这条路被称之为从Vs到到Vt的最短路。这条路上所有弧的权数的总的最短路。这条路上所有弧的权数的总和被称为从和被称为从Vs到到Vt的距离。的距离。18.最短路问题最短路问题狄克斯屈拉狄克斯屈拉狄克斯屈拉狄克斯屈拉(Dijkstra)(Dijkstra)标号算法的基本思路：标号算法的基本思路：标号算法的基本思路：标号算法的基本思路：若序列若序列 vs,v1.vn-1,vn 是从是从vs到到vt间的最短路，则序列间的最短路，则序列 vs,v1.vn-1 必为从必为从vs 到到vn-1的最短路。的最短路。假定假定v1v2 v3 v4是是v1 v4的最短路，则的最短路，则v1 v2 v3一定是一定是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4的的最短路。最短路。v1v2v3v4v519.最短路问题最短路问题最短路的最短路的最短路的最短路的DijkstraDijkstra算法算法算法算法(双标号法）的步骤：双标号法）的步骤：双标号法）的步骤：双标号法）的步骤：1.给出点给出点V1以标号以标号(0,s)2.找出已标号的点的集合找出已标号的点的集合I，没标号的点的集合，没标号的点的集合J以及弧的集合以及弧的集合3.如果上述弧的集合是空集，则计算结束。如果如果上述弧的集合是空集，则计算结束。如果vt已标号（已标号（lt,kt），），则则 vs到到vt的距离为的距离为lt，而从，而从 vs到到vt的最短路径，则可以从的最短路径，则可以从kt 反向反向追踪到起点追踪到起点vs 而得到。如果而得到。如果vt 未标号，则可以断言不存在从未标号，则可以断言不存在从 vs到到vt的有向路。如果上述的弧的集合不是空集，则转下一步。的有向路。如果上述的弧的集合不是空集，则转下一步。4.对上述弧的集合中的每一条弧，计算对上述弧的集合中的每一条弧，计算 sij=li+cij。在所有的。在所有的 sij中，中，找到其值为最小的弧。不妨设此弧为（找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终），则给此弧的终点以双标号（点以双标号（scd,c）,返回步骤返回步骤2。20.最短路问题最短路问题(P233)例例1 求下图中求下图中v1到到v6的最短路的最短路解：采用解：采用Dijkstra算法，可解得最短路径为算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v23527531512 V1（0,s)v5(8,4)v6(2,1)v3(3,3)v421.最短路问题最短路问题(P234)例例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。的长度（单位：公里）。解：这是一个求无向图的最短路的问题。可以把无向图的每一边解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（）都用方向相反的两条弧（vi,vj）和（）和（vj,vi）代替，就化为有向图，）代替，就化为有向图，即可用即可用Dijkstra算法来求解。也可直接在无向图中用算法来求解。也可直接在无向图中用Dijkstra算法来求解。算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。未标号的点的边的集合即可。V1（甲地）（甲地）151762444 31065v2V7（乙地）（乙地）v3v4v5v622.最短路问题最短路问题（0,s）V1（甲地）（甲地）1517624431065(13,3)v2 (22,6)V7（乙地）（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)23.最短路问题最短路问题 例例3 3 设备更新问题。某公司使用一台设备，在每年年初，公司就要设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表已知：设备每年年初的价格表 设备维修费如下表设备维修费如下表年份年份12345年初价格年初价格1111121213使用年数使用年数0-11-22-33-44-5每年维修每年维修费用费用568111824.最短路问题最短路问题例例3的解：的解：将问题转化为最短路问题，如下图：将问题转化为最短路问题，如下图：用用vi表示表示“第第i年年初购进一台新设备年年初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进年年初购进的的设备一直使用到第设备一直使用到第j年年初。年年初。把所有弧的权数计算如下表：把所有弧的权数计算如下表：v1v2v3v4v5v612345611622304159216223041317233141723518625.最短路问题最短路问题(继上页继上页)把权数赋到图中，再用把权数赋到图中，再用Dijkstra算法求最短路。算法求最短路。最终得到下图，可知，最终得到下图，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条：v1 v3 v6和和 v1 v4 v6v1v2v3v4v5v6162230415916223041312317181723 V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)26.最短路问题最短路问题课堂练习：课堂练习：1.用用Dijkstra算法求下图从算法求下图从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：27.最短路问题最短路问题2.求从求从v1到到v8的最短路径的最短路径23718456613410527593468228.最短路问题最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为1029.最短路问题最短路问题3.求下图中求下图中v1点到另外任意一点的最短路径点到另外任意一点的最短路径v1v2v3v4v6v532276213330.最短路问题最短路问题v1V2V3V4 V6V532276213302471431.最短路问题最短路问题v1V2V3V4 V6V532276213302471432.最短路问题最短路问题算法适用条件：算法适用条件：算法适用条件：算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次某边上权为负的，算法失效。此时可采用逐次逼近算法。逼近算法。例例6.7 如右图所示中按如右图所示中按dijkstra算法可得算法可得P(v1)=5为从为从vsv1的的最短路长显然是错误的，从最短路长显然是错误的，从vsv2v1路长只有路长只有3。v2vsv15-5833.最小生成树问题最小生成树问题树是图论中结构最简单但又十分重要的图。在自然和社会树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。领域应用极为广泛。例例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。如下图所示。AB CDEF GH运动员运动员34.最小生成树问题最小生成树问题例例 某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科35.树与图的最小树树与图的最小树 树：无圈的连通图即为树树：无圈的连通图即为树树：无圈的连通图即为树树：无圈的连通图即为树性质性质性质性质1 1：任何树中必存在次为任何树中必存在次为1的点。的点。(一个点一个点Vi的相关联边的数目称为点的相关联边的数目称为点Vi的次的次)性质性质性质性质2 2：n 个顶点的树必有个顶点的树必有n-1 条边。条边。性质性质性质性质3 3：树中任意两个顶点之间，恰有且仅有一条链。树中任意两个顶点之间，恰有且仅有一条链。性质性质性质性质4 4：树连通，但去掉任一条边，必变为不连通。树连通，但去掉任一条边，必变为不连通。性质性质性质性质5 5：树无回圈，但不相邻的两个点之间加一条边，恰树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v636.最小生成树问题最小生成树问题树是图论中的重要概念，所谓树就是一个无圈的连通图。树是图论中的重要概念，所谓树就是一个无圈的连通图。图图11-11中，中，(a)就是一个树，而就是一个树，而(b)因为图中有圈所以就不因为图中有圈所以就不是树，是树，(c)因为不连通所以也不是树。因为不连通所以也不是树。图图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)37.最小生成树问题最小生成树问题 图的最小部分树图的最小部分树图的最小部分树图的最小部分树(支撑树支撑树支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一般图G1含有多含有多个部分树，其中树枝总长最小的部分树，称为该图的最小个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G238.最小生成树问题最小生成树问题a ab bc cf fe ed dh hg gb bf fe ed d39.最小生成树问题最小生成树问题a ab bc cf fe ed dh hg gb bf fd dg g40.最小生成树问题最小生成树问题b bc ce ed da ab bc cf fe ed dh hg g41.最小生成树问题最小生成树问题a ab bc ch ha ab bc cf fe ed dh hg g42.最小生成树问题最小生成树问题a af fd dg ga ab bc cf fe ed dh hg g43.最小生成树问题最小生成树问题 给了一个无向图给了一个无向图G=(V,E)，我们保留，我们保留G的所有点，而删掉部分的所有点，而删掉部分G的边或者的边或者说保留一部分说保留一部分G的边，所获得的图的边，所获得的图G，称之为，称之为G的生成子图。在图的生成子图。在图11-12中，中，(b)和和(c)都是都是(a)的生成子图。的生成子图。如果图如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在的一个生成子图还是一个树，则称这个生成子图为生成树，在图图11-12中，中，(c)就是就是(a)的生成树。的生成树。最小生成树问题就是指在一个赋权的连通的无向图最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。并使得这个生成树的所有边的权数之和为最小。图图11-12(a)(b)(c)44.最小生成树问题最小生成树问题求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法破圈法破圈法破圈法破圈法45.最小生成树问题最小生成树问题部分树46.最小生成树问题最小生成树问题避圈法避圈法避圈法避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v547.最小生成树问题最小生成树问题 赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法破圈法破圈法破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=548.最小生成树问题最小生成树问题v1v2v3v4v5v643521得到最小树得到最小树：Min C(T)=1549.最小生成树问题最小生成树问题 避圈法避圈法避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通形成圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v684375261850.最小生成树问题最小生成树问题v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=1551.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636练习：练习：应用破圈法求最小树应用破圈法求最小树52.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323363653.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 1232354.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 1232355.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 1232356.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 1232357.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 1232358.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 1232359.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 1232360.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 1232361.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 1232362.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 1232363.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=5764.最小生成树问题最小生成树问题练习：练习：应用避圈法求最小树应用避圈法求最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323363665.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323363666.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323363667.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323363668.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323363669.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323363670.最小生成树问题最小生成树问题v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=5771.最小生成树问题最小生成树问题课堂练习：课堂练习：课堂练习：课堂练习：3749346321Min C(T)=12Min C(T)=15254173314475答案：72.最小生成树问题最小生成树问题34122323242Min C(T)=12213638534567454321Min C(T)=1873.最小生成树问题最小生成树问题 例例5、某大学准备对其所属的、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中能联通的途径如下图，图中v1,v7 表示表示7个学院办公室，请设计一个网个学院办公室，请设计一个网络能联通络能联通7个学院办公室，并使总的线路长度为最短。个学院办公室，并使总的线路长度为最短。解：此问题实际上是求图解：此问题实际上是求图11-1411-14的最小生成树，这在例的最小生成树，这在例4 4中已经求得，中已经求得，也即按照图也即按照图11-1311-13的的(f)(f)设计，可使此网络的总的线路长度为最短，为设计，可使此网络的总的线路长度为最短，为1919百米。百米。“管理运筹学软件管理运筹学软件”有专门的子程序可以解决最小生成树问题。有专门的子程序可以解决最小生成树问题。v1331728541034v7v6v5v4v2v3图图11-1474.网络的最大流网络的最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。这就是一个网络最大流问题。75.网络的最大流网络的最大流基本概念：基本概念：1.1.1.1.容量网络：容量网络：容量网络：容量网络：队网络上的每条弧队网络上的每条弧(v(vii,v,vj j)都给出一个最大的都给出一个最大的通过能力，称为该弧的通过能力，称为该弧的容量容量容量容量，简记为，简记为c cij ij。容量网络中通常。容量网络中通常规定一个规定一个发点发点发点发点(也称源点，记为也称源点，记为s)s)和一个和一个收点收点收点收点(也称汇点，也称汇点，记为记为t)t)，网络中其他点称为，网络中其他点称为中间点中间点中间点中间点。st484412267976.网络的最大流网络的最大流2.2.网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3.3.流与可行流流与可行流 流流是指加在网络各条弧上的实际流量，对加在弧是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的上的负载量记为负载量记为fij。若。若fij=0，称为零流。，称为零流。满足以下条件的一组流称为满足以下条件的一组流称为可行流可行流。容量限制条件。容量网络上所有的弧满足：容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。中间点平衡条件。若以若以v(f)表示网络中从表示网络中从st的流量，则有：的流量，则有：77.网络的最大流网络的最大流结论结论：任何网络上一定存在可行流。（零流即是：任何网络上一定存在可行流。（零流即是可行流）可行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使v(f)v(f)值达到最大。值达到最大。78.网络的最大流网络的最大流一、最大流的数学模型一、最大流的数学模型 例例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（变化，它的各段管道（vi,vj）的流量）的流量cij（容量）也是不一样的。（容量）也是不一样的。cij的单的单位为万加仑位为万加仑/小时。如果使用这个网络系统从采地小时。如果使用这个网络系统从采地 v1向销地向销地 v7运送石油，运送石油，问每小时能运送多少加仑石油？问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图图11-2679.网络的最大流网络的最大流 我们可以为此例题建立线性规划数学模型：我们可以为此例题建立线性规划数学模型：设弧设弧(vi,vj)上流量为上流量为fij，网络上的总的流量为，网络上的总的流量为F，则有：，则有：80.网络的最大流网络的最大流 在这个线性规划模型中，其约束条件中的前在这个线性规划模型中，其约束条件中的前6 6个方程表示个方程表示了网络中的流量必须满足守恒条件，了网络中的流量必须满足守恒条件，发点的流出量必须等于发点的流出量必须等于收点的总流入量收点的总流入量；其余的点称之为；其余的点称之为中间点中间点，它的总流入量必，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧须等于总流出量。其后面几个约束条件表示对每一条弧(v(vi i,v,vj j)的流量的流量fij要满足流量的可行条件，应小于等于弧要满足流量的可行条件，应小于等于弧(v(vi i,v,vj j)的容量的容量c cijij，并大于等于零，即，并大于等于零，即0 0f fijij c cijij。我们把满。我们把满足守恒条件及流量可行条件的一组网络流足守恒条件及流量可行条件的一组网络流 ffijij 称之为称之为可行流可行流，（即线性规划的可行解），可行流中一组流量最大（也即发（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为出点总流出量最大）的称之为最大流最大流（即线性规划的最优解）。（即线性规划的最优解）。我们把例我们把例6 6的数据代入以上线性规划模型，用的数据代入以上线性规划模型，用“管理运筹管理运筹学软件学软件”，马上得到以下的结果：，马上得到以下的结果：f f1212=5=5，f f1414=5=5，f f2323=2=2，f f2525=3=3，f f4343=2=2，f f4646=1=1，f f4747=2=2，f f3535=2=2，f f3636=2=2，f f5757=5=5，f f6767=3=3。最优值。最优值（最大流量）（最大流量）=10=10。81.网络的最大流网络的最大流二、最大流问题网络图论的解法二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图对网络上弧的容量的表示作改进。为省去弧的方向，如下图:(a)和和(b)、(c)和和(d)的意义相同。的意义相同。用以上方法对例用以上方法对例6的图的容量标号作改进，得下图的图的容量标号作改进，得下图vivjvivjcij0（a）（b）cijcijvivj（cji）（c）vivj cij cji（d）63522241263v1v2v5v7v4v3v60000000000082.网络的最大流网络的最大流 求最大流的基本算法求最大流的基本算法（1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的