OR1-3图与网络分析

1、第第3 3章章 图与网络分析图与网络分析图图 论论ABCDACBD第第3 3章章 图与网络分析图与网络分析1.1.认识图认识图2.2.最小支撑树问题最小支撑树问题3.3.中国邮递员问题中国邮递员问题4.4.最大流问题最大流问题5.5.最短路问题最短路问题6.6.旅行商问题旅行商问题一、认识图认识图一、认识图认识图第第3 3章章 图与网络分析图与网络分析1.1.认识图认识图2.2.最小支撑树问题最小支撑树问题3.3.中国邮递员问题中国邮递员问题4.4.最大流问题最大流问题5.5.最短路问题最短路问题6.6.旅行商问题旅行商问题二、最小支撑树问题最小支撑树问题例：某地新建例：某地新建5处居民点，拟

2、修道路连接处居民点，拟修道路连接5处，经勘测处，经勘测其道路可铺成如图所示，图中数据为相应道路的修建其道路可铺成如图所示，图中数据为相应道路的修建费用。为使费用。为使5处居民点都有道路相连，并使处居民点都有道路相连，并使总费用最总费用最小小，求修建方案。，求修建方案。v1v2v3v4v555.57.53.5423二、最小支撑树问题支撑子图二、最小支撑树问题树树：无圈的连通图。二、最小支撑树问题树(A)(B)(C)二、最小支撑树问题支撑树345863973458639734586397二、最小支撑树问题最小支撑树二、最小支撑树问题最小支撑树问题例：某地新建例：某地新建5处居民点，拟修道路连接处居

3、民点，拟修道路连接5处，经勘测处，经勘测其道路可铺成如图所示，图中数据为相应道路的修建其道路可铺成如图所示，图中数据为相应道路的修建费用。为使费用。为使5处居民点都有道路相连，并使处居民点都有道路相连，并使总费用最总费用最小小，求修建方案。，求修建方案。v1v2v3v4v555.57.53.5423算法1避 圈 法v1v2v3v4v555.57.53.54233v12v4v545v23.5v3避圈法避圈法：把边按权从小到大依次：把边按权从小到大依次添入图中，若出现圈，则删去其添入图中，若出现圈，则删去其中最大边，直至填满中最大边，直至填满n-1条边为止条边为止（n为结点数）为结点数） 。总费用

4、总费用=13.5算法2破 圈 法3v12v4v545v23.5v3破圈法破圈法：在图中找：在图中找圈圈，并，并删除删除其中其中最大边最大边。如此进行下去，直至图中不。如此进行下去，直至图中不存在圈。存在圈。v1v2v3v4v555.57.53.5423总费用总费用=13.5 练习练习1：今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，

5、并求所需的总费用。济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531二、最小支撑树问题总费用总费用=25万元万元31前两节重点1. 最小支撑树问题课堂练习 P129，习题5.15.1（a）72461872416323543165.1（b）12522323434125.1（c）3535132234222222185.1（d）57336441763215第第3 3章章 图与网络分析图与网络分析1.1.认识图认识图2.2.最小支撑树问题最小支撑树问题3.3.中国邮递员问题中国邮递员问题4.4.最大流问题最大流问题5.5.最短路问题最短路问题6.6.旅行

6、商问题旅行商问题问题的提出：问题的提出： 一邮递员所管街区示意如图，一邮递员所管街区示意如图，他每天都要从邮局出发，到他所他每天都要从邮局出发，到他所管街区的每一条道路投递信件，管街区的每一条道路投递信件，他应如何选择一条线路，使每条他应如何选择一条线路，使每条街都能经过，而且总的路程最短。街都能经过，而且总的路程最短。 如何确定一条闭链，使其包含该图的每条边至少一次，而且总长度最短。三、中国邮递员问题第第3 3章章 图与网络分析图与网络分析1.1.认识图认识图2.2.最小支撑树问题最小支撑树问题3.3.中国邮递员问题中国邮递员问题4.4.最大流问题最大流问题5.5.最短路问题最短路问题6.6

7、.旅行商问题旅行商问题四、最大流问题(T)V7V6V5V4V3 V2(S)V1(6)(5)(5)(4) (2)(1)(2)(3) (3) (2) (4)(3)容量容量323102123126流量流量四、最大流问题可行流四、最大流问题容量限制条件）平衡条件）(),(0(,0)()(. .)(maxAvvcfTSvTvfvSvfvfftsfvzjiijijiiikkijij(T)V7V6V5V4V3 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容量容量 流量流量 前向弧：前向弧： + 后向弧：后向弧：

8、 - 四、最大流问题增广链 增广链：增广链：前向未满前向未满，后向非后向非0(T)V7V6V5V4V3 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容量容量 流量流量 增广链：前向未满，后向非增广链：前向未满，后向非0四、最大流问题增广链调整量),(),(min, )(minminjijivvijijijvvffc(T)V7V6V5V4V3 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容量容量 流量流

9、量 增广链：前向未满，后项非增广链：前向未满，后项非0四、最大流问题增广链调整),(),(min, )(minminjijivvijijijvvffc 前向弧：前向弧： + 后向弧：后向弧： - 31403(T)V7V6V5V4V3 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容量容量 流量流量四、最大流问题最大流最小截集定理314031234AVVVV集合：点 ， ， ，567BVVV集合：点 ， ，截集截集：(V2, V6),(V3, V6),(V3, V5),(V4, V5)截量截量=2+1

10、+2+4=9 (T)V7V6V5V4V3 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)四、最大流问题最大流最小截集定理),()(BACfvv构建一个可行流；构建一个可行流；v在可行流的基础上，找增广链前向未满，后向非在可行流的基础上，找增广链前向未满，后向非0；v一旦找到增广链，就对增广链进行调整，形成新的一旦找到增广链，就对增广链进行调整，形成新的可行流。可行流。四、最大流问题练习练习

11、1：有三个发电站有三个发电站V1, V2, V3，发电能力分别为，发电能力分别为15、10和和40兆兆瓦，经输电网可把电力送到瓦，经输电网可把电力送到8号地区，电网能力如图所示。求三号地区，电网能力如图所示。求三个发电站输到该地区的最大电力。个发电站输到该地区的最大电力。v2v1v3v4v5v6v7v8 40 15 30154510151020四、最大流问题v2v1v3v4v5v6v7v8 40 15 30154510151020v0 10 15 40（1）完善图，构建虚拟起始点）完善图，构建虚拟起始点四、最大流问题v2v1v3v4v5v6v7v8 40 15 30154510151020v0

12、 10 15 40（2）确定一个可行流）确定一个可行流1015303015151520201010203520四、最大流问题（3）找增广链）找增广链v2v1v3v4v5v6v7v8 40 15 30154510151020v0 10 15 401015303015151520201010203520 不存在增广链，已得到最大流不存在增广链，已得到最大流最小截集：最小截集： (V0,V2),(V6,V5),(V6,V7)，最大流最大流=10+20+15=45四、最大流问题四、最大流问题练习练习2 2：一网络如图，图中每条弧上带有（一网络如图，图中每条弧上带有（ ）的数字为该）的数字为该弧的容量，

13、不带括弧的数字为该弧上的流量。要求：弧的容量，不带括弧的数字为该弧上的流量。要求：（1 1）在未标注流量的弧上标上适当的流量，使之与标出的）在未标注流量的弧上标上适当的流量，使之与标出的流量构成该网络的一可行流；流量构成该网络的一可行流；（2 2）对于（）对于（1 1）中得到的可行流，网络中是否存在增广链？）中得到的可行流，网络中是否存在增广链？若存在请指出该条增广链，并说明此增广链的调整量；若存在请指出该条增广链，并说明此增广链的调整量；（3 3）求该网络的最大流并指出相应的最小截集（若需改变）求该网络的最大流并指出相应的最小截集（若需改变流量，需分步绘制新图，并在新图中标出各条弧的容量和流

14、量，需分步绘制新图，并在新图中标出各条弧的容量和流量，最后指出最大流量）；流量，最后指出最大流量）； 练习2，P130，5.4，5.5，5.6 构建可行流 理解增广链的含义 求最大流 最大流最小截集定理第第3 3章章 图与网络分析图与网络分析1.1.认识图认识图2.2.最小支撑树问题最小支撑树问题3.3.中国邮递员问题中国邮递员问题4.4.最大流问题最大流问题5.5.最短路问题最短路问题6.6.旅行商问题旅行商问题 V6 V5 V4 V3 V2 V1150200100275150300 100400250ST五、最短路问题 V6 V5 V4 V3 V2 V1150200100275150300

15、 100400250(250，)(350，)(0，)(500，)(600，)(700，)V6V4V3V2V1最短路线为：最短路线为：，距离为，距离为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 3章章 图与网络分析图与网络分析1.1.认识图认识图2.2.最小支撑树问题最小支撑树问题3.3.中国邮递员问题中国邮递员问题4.4.最大流问题最大流问题5.5.最短路问题最短路问题6.6.旅行商问题旅行商问题TSP问题的提出： 一旅行推销