OR1-3 图与网络分析.pptVIP

(T) V7 V6 V5 V4 V3 V2 (S) V1 (6) 6 (5) 2 (5) 1 (4) 3 (2) 2 (1) 1 (2) 2 (3) 0 (3) 3 (2) 1 (4) 2 (3) 3 容量 流量 四、最大流问题——最大流最小截集定理 3 1 4 0 3 截集：{(V2, V6),(V3, V6),(V3, V5),(V4, V5)} 截量=2+1+2+4=9 (T) V7 V6 V5 V4 V3 V2 (S) V1 (6) 6 (5) 2 (5) 1 (4) 3 (2) 2 (1) 1 (2) 2 (3) 0 (3) 3 (2) 1 (4) 2 (3) 3 容量 流量 截量：3+4+3=10 截集：{(v1, v2),(v1, v3),(v1, v4)} 四、最大流问题——最大流最小截集定理 构建一个可行流； 在可行流的基础上，找增广链前向未满，后向非0； 一旦找到增广链，就对增广链进行调整，形成新的可行流。 四、最大流问题 练习1：有三个发电站V1, V2, V3，发电能力分别为15、10和40兆瓦，经输电网可把电力送到8号地区，电网能力如图所示。求三个发电站输到该地区的最大电力。 v2 v1 v3 v4 v5 v6 v7 v8 40 15 30 15 45 10 15 10 20 四、最大流问题 v2 v1 v3 v4 v5 v6 v7 v8 40 15 30 15 45 10 15 10 20 v0 10 15 40 （1）完善图，构建虚拟起始点 四、最大流问题 v2 v1 v3 v4 v5 v6 v7 v8 40 15 30 15 45 10 15 10 20 v0 10 15 40 （2）确定一个可行流 10 15 30 30 15 15 15 20 20 10 10 20 35 20 四、最大流问题 （3）找增广链 v2 v1 v3 v4 v5 v6 v7 v8 40 15 30 15 45 10 15 10 20 v0 10 15 40 10 15 30 30 15 15 15 20 20 10 10 20 35 20 ∴ 不存在增广链，已得到最大流 最小截集： {(V0,V2),(V6,V5),(V6,V7)}， 最大流=10+20+15=45 四、最大流问题 四、最大流问题 练习2：一网络如图，图中每条弧上带有（ ）的数字为该弧的容量，不带括弧的数字为该弧上的流量。要求： （1）在未标注流量的弧上标上适当的流量，使之与标出的流量构成该网络的一可行流； （2）对于（1）中得到的可行流，网络中是否存在增广链？若存在请指出该条增广链，并说明此增广链的调整量； （3）求该网络的最大流并指出相应的最小截集（若需改变流量，需分步绘制新图，并在新图中标出各条弧的容量和流量，最后指出最大流量）； 作 业 7 练习2，P130，5.4，5.5，5.6 重 点 构建可行流 理解增广链的含义 求最大流 最大流最小截集定理 第3章 图与网络分析 认识图 最小支撑树问题 中国邮递员问题 最大流问题 最短路问题 旅行商问题 V6 V5 V4 V3 V2 V1 150 200 100 275 150 300 100 400 250 S T 五、最短路问题 V6 V5 V4 V3 V2 V1 150 200 100 275 150 300 100 400 250 (250，①) (350，②) (0，①) (500，③) (600，④) (700，④) V6 V4 V3 V2 V1 最短路线为： ，距离为700。 五、最短路问题 双标号法 ：（始点到当前最短距离，前一个节点号） 课堂练习 P130，习题5.3 重 点 双标号法 ：（始点到当前最短距离，前一个节点号） (0,v1) (3,v1) 5.3 (4,v1) (5,v2) (6,v2) (6,v2) (7,v4) (7,v6) (8.5,v6) 最短路为v1-v2-v6-v9，最短路长为8.5。 (9,v7) 第3章 图与网络分析 认识图 最小支撑树问题 中国邮递员问题 最大流问题 最短路问题 旅行商问题 TSP问题的提出： 一旅行推销员从他家所在村庄出发，到他拟去的若干村庄推销商品，他应如何选择一条线路，使拟去的每个村庄都能经过，而且总的路程最短。 从图的意义上，该问题是：对于一赋权图，如何确定一条闭链，使其包含该图的每个顶点至少一次，而且总长度最短。 六、旅行商问题 第3章