运筹学21图论最小树和最大流.ppt

Operational Research 图论之二,ZHU Tong Changan University E-mail: ,2012.12,Home,Home,2,最小树问题,问题描述 给定网络G，设T是G的生成树，T中所有边的权数之和为树T的权。 权最小的生成树称为G的最小生成树。对于任意联通网络，寻找最小树称为最小树问题,3,最小树问题,问题描述 给定网络G，设T是G的生成树，T中所有边的权数之和为树T的权。 权最小的生成树称为G的最小生成树。对于任意联通网络，寻找最小树称为最小树问题 解法 Joseph Kruskal（克鲁斯克尔 ，American mathematician and computer scientist ） 从网络中一步步挑选边，构成最小树，每次挑选权最小的边并且确保已选好的边不产生圈。,4,例题用Kruskal方法构造图的最小生成树,集合E中的边按权递增顺序排列为 (v1, v2 5), (v1, v3 6), (v2, v3 6), (v0, v1 10), (v1, v5 11), (v3, v5 14), (v3, v4 18), (v0, v4 19), (v0, v5 21), (v4, v5 33),5,7,8,最大流问题,案例 v1表示工厂，v6表示市场，v1-v5表示转运站。产品从工厂到市场要经过转运站。 弧的权数表示能通过的货物量，求如何安排运输，使到达市场数量最大？,9,最大流问题,容量 Capacity 在有向图D=（V，A），指定一个点为起点与终点，其余点叫作中间点。对于A的每条弧，都对应一个权数 wij 0，称为弧的容量。 流 Flow 每一弧（vi，vj）的流量为xij，集合X=xij | （vi，vj）属于A 称为该网络一个流。 可行流 最大流问题一定是求网络流值上的最大可行流,流入量=流出量,中间点,10,最大流问题,增广链 所谓增广链，指某可行流上，沿着从始点到终点的某条链调整各弧上的流量，可以使网络的流量增大，得到一个比原可行流流量更大的可行流。增广链必须满足以下条件： 该链上所有的前向弧流量小于容量，即流量可以增加；该链上所有的后向弧流量大于零，即流量可以减少。 有增广链说明还有可改变的余地 虚线所示的链是一条增广链,V1,V6,V2,V4,V3,V5,（5,3）,（6,6）,（3,1）,（4,2）,（5,3）,（4,4）,（6,4）,（8,5）,（6,2）,流为9,11,最大流问题,定理： 可行流为最大流的充要条件是不存在关于x*的增广链。 算法 Ford-Fulkerson算法,12,最大流问题,过程 从某一可行流出发，通过找增广链、检查-标号、调整三步完成算法； （1）找到一个增广链； （2）逐一检查，给出标号；每一标号点包括两部分（第一标号表明标号从哪里来，顺则+逆则-；第二标号表明可调整量，取之前的最小值）。 （3）调整流量； （4）再找增广链。,(+v1,2),13,最大流问题,过程 从某一可行流出发，通过找增广链、检查-标号、调整三步完成算法； （1）找到一个增广链； （2）逐一检查，给出标号；每一标号点包括两部分（第一标号表明标号从哪里来，顺则+逆则-；第二标号表明可调整量，取之前的最小值）。 （3）调整流量（保持每个中间点的平衡）； （4）再找增广链。,V1,V6,V2,V4,V3,V5,（5,3）,（6,6）,（3,1）,（4,2）,（5,3）,（4,4）,（6,4）,（8,5）,（6,2）,(+v1,2),(-v2,1),(+v3,1),(-v5,1),(+v4,1),14,最大流问题,过程 从某一可行流出发，通过找增广链、检查-标号、调整三步完成算法； （1）找到一个增广链； （2）逐一检查，给出标号；每一标号点包括两部分（第一标号表明标号从哪里来，顺则+逆则-；第二标号表明可调整量，取之前的最小值）。 （3）调整流量（保持每个中间点的平衡