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

Operational Research图论之二,ZHU TongChangan University,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,6,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）调整流量（保持每个中间点的平衡）；（4）再找增广链。,最大流为10,15,最大流问题：案例2,（4,3）,（3,3）,（5,1）,（2,2）,（1,1）,（1,1）,（3,0）,（5,3）,（2,1）,