第六章网络模型

1、第第1页页 共共49页页第六章第六章 网络模型网络模型 w 重点：重点：图的基本概念、最小支撑树问题、最短路问题，最大流问题、网络分析w 难点：难点：最大流-最小截问题第第2页页 共共49页页十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有 7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡 7 桥”难题。 “哥尼斯堡 7 桥”难题最终在 1736 年由数学家 euler 的论文“依据几何位置的解题方法”给予了完满的解决。第第

2、3页页 共共49页页 图论与网络分析理论所研究的问题十分广泛，内容极其丰富。图论中研究的图并非几何学中的图，也不是绘画中的图。图论关心的仅仅是图中有多少个点，点与点之间有无边连接。第第4页页 共共49页页1. 图与子图2. 关联与相邻3. 链与圈4. 有向图与无向图5. 欧拉回路经过每个边一次且仅一次的回路6. 哈密顿回路经过每个点一次且仅一次的回路7. 树一、基本概念一、基本概念（邮递员问题）（货郎问题）第第5页页 共共49页页1.1. 图与子图图与子图第第6页页 共共49页页2.2. 关联与相邻关联与相邻3.3. 链与圈链与圈第第7页页 共共49页页7.7. 树树第第8页页 共共49页页二

3、、网络分析二、网络分析1. 最小部分树（支撑树） 方法：破圈法 避圈法 应用2. 最大流3. 最短路权和最小第第9页页 共共49页页1542453134421512例6-1 用破圈法及避圈法求下图的最小生成树。15424531344215121542453134421512第第10页页 共共49页页最小支撑树的应用例6-2 已知有a、b、c、d、e、f 六个城镇间的道路网络如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图。求能保证各城镇均能通话且总架设费用最少的架设方案。第第11页页 共共49页页练习 求下图所示网络的最小支撑树。第第12页页 共共49页页网络流与最

4、大流问题网络流与最大流问题 最大流问题是一类应用极为广泛的问题，如运输网络中的人流、车流、物流，供水网络中的水流，金融系统中的现金流，通信系统中的信息流等等。第第13页页 共共49页页1、问题的提出 已知网络d =（v,a,c），其中v 为顶点集，a 为弧集， c = cij 为容量集，cij 为弧 (vi ,vj)上的容量。现d 上要通过一个流 f = fij ，其中fij为弧(vi ,vj)上的流量。问应如何安排流量 fij 可使d 上通过的总流量v 最大？例6-3 第第14页页 共共49页页2、数学模型第第15页页 共共49页页 源、汇、中间点 弧容量、流量3、基本概念),(ijijf

5、jviv 可行流 流量 v（ f ）第第16页页 共共49页页 弧 饱和弧、非饱和弧 零流弧、非零流弧 正向弧、反向弧 增广链：在增广链上可以调整增加流量。4、最大流：流量 v( f ) 达到最大的流 f 。例6-3正向弧皆非饱和反向弧皆非零第第17页页 共共49页页 截集、截量定理： 最大流的流量等于最小截集的截量。例例6-36-3 中若 v1 = vs ,v1，请指出相应的截集与截量。第第18页页 共共49页页0,+0,+5、标号法求最大流 重复标号求增广链并调整可行流，直到不存在增广链。vtvsv2v3v4v1(8,3)(6,6)(7,6)(3,0)(2,0)(10,4)(8,4)(7,

6、7)(3,3)vs ,5-v2 ,3vs ,5v1 ,3-v2 ,3v4 ,3v1 ,3vt v4 v1 v2 vs: 3 例6-4 用标号法求下图的最大流。第第19页页 共共49页页vtvsv2v3v4v1(8,6)(6,6)(7,6)(3,0)(2,0)(10,7)(8,7)(7,7)(3,0)0,+vs ,20,+vs ,2vt v4 v1 v2 vs: 3 f1中不存在增广链，即为最大流，其流量v( f ) = 6+7 = 13第第20页页 共共49页页0,+vs ,10,+v4 ,2vt v4 v1 vs: 2 vtvsv2v3v4v1(4,3)(1,1)(7,6)(5,3)(3,2

7、)(8,3)(4,2)(10,4)(3,2)(3,2)(4,3)v5(2,2)vs ,1vs ,6vs ,6v1,2v1,2例6-5 求最大流。第第21页页 共共49页页v5 ,10,+vs ,10,+v3 ,1vt v3 v5 vs: 1 vtvsv2v3v4v1(4,3)(1,1)(7,6)(5,3)(3,2)(8,5)(4,4)(10,6)(3,2)(3,2)(4,3)v5(2,2)vs ,1vs ,4vs ,4vs ,1v5 ,1v5 ,1vt v4 v1 vs: 2 vs ,1第第22页页 共共49页页0,+vs ,10,+v4 ,1vt v4 v5 v1 vs: 1 vtvsv2v

8、3v4v1(4,3)(1,1)(7,7)(5,3)(3,2)(8,5)(4,4)(10,6)(3,3)(3,2)(4,4)v5(2,2)v1 ,1vs ,4vs ,4v1 ,1v5 ,1v5 ,1vt v3 v5 vs: 1 vs ,1第第23页页 共共49页页0,+vs ,10,+v4 ,1vt v4 v5 v2 vs: 1 vtvsv2v3v4v1(4,3)(1,1)(7,7)(5,4)(3,2)(8,6)(4,4)(10,7)(3,3)(3,3)(4,4)v5(2,2)v2 ,1vs ,3vs ,3vs ,1v5 ,1v5 ,1v2 ,1vt v4 v5 v1 vs: 1 第第24页页

9、共共49页页0,+0,+vtvsv2v3v4v1(4,4)(1,1)(7,7)(5,5)(3,3)(8,7)(4,4)(10,7)(3,3)(3,3)(4,4)v5(2,2)vs ,3vs ,3 f 中不存在增广链，即为最大流，其流量vt v4 v5 v2 vs: 1 v( f ) = 4+3+3+4 = 14第第25页页 共共49页页应用实例（10,10）（10,10）（15,15）（20,10）（15,5）（5,5）（20,20）（15,0）第第26页页 共共49页页最短路和最小费用流问题最短路和最小费用流问题 最大流问题反映了网络的流通能力，没有考虑运输费用的多少，实际问题中经常需要寻求

10、网络中总费用达到最小的方案，即最小费用流问题。1、最短路 网络中两点间的各边权值之和达到最小的路。 dijkstra 标号法 warshallfloyd 算法第第27页页 共共49页页 dijkstra 标号法第第28页页 共共49页页165821128299722v1v2v5v6v75vsvtv40,vs例6-4 求vsvt的最短路。2,vsv33,v25,v45, vs5,v46,v17,v59,v710,v6第第29页页 共共49页页练习 求v1v7的最短路。第第30页页 共共49页页 warshallfloyd 算法 对于权值非负的网络图，标号法可以求原点到任意顶点的最短路。但当网络图

11、中存在权值为负的边时，算法失效，可用floyd算法（可以求解任意两点之间的最短路）进行求解。 其基本思路是：v1 到 vj 的最短路总是从v1先到达某一点vi ，然后再沿边（vi,vj）达到 vj ，且从v1 到 vi 的路也是最短路。令 p1j 表示从v1 到 vj 的最短路长，则有p1j = minl1j ，p1i+lij第第31页页 共共49页页 floyd 算法步骤i.初始化距离矩阵和序号矩阵)0()0( 、lii.计算矩阵 )()(kkl 、kjiothersllllllkikkijkijkijkijkkjkikkijkij ,min)1()1()()1()()1()1()1()(

12、其中， 的第 k 行和第 k 列与 保持一致。)(kl)1( kliii. 若 或 k = n ，算法停止，否则转。0)( kiil第第32页页 共共49页页例6-5 求下图中各顶点间的最短路。v5v1v2v3v4323-4-1394第第33页页 共共49页页2009439-4020331312-10111112222333344444555551130122-42-200-15903398-101111122212334444455552122930043-402039-1201111122222333334444455555)(k )(klk = 0 k = 1 k = 2 第第34页页

13、共共49页页30122-42-200-15903398-1011111222123344444555521220-1-12010322-1-408-233912-1011111222122331244555232231122122331223442558-40-210-2200-1311201522-13019812-13424234)(k )(klk = 2 k = 3 k = 4第第35页页 共共49页页)(k )(kl112212233122344255k = 4 2-13018-40-210-2200-1311201529812-1342423413412222233223442234

14、55k = 5 8-40-11-22-1010-2210-132120439-320455第第36页页 共共49页页2、最小费用流：流量为 v 且使总费用达到最小的流 f 。),(ijijb jviv基本思路为：从零流费用有向图出发，求源点到终点的最小费用链 ，并调整可行流 f 的流量。若 f 的流量 v，算法结束，否则重新构造关于 f 的费用有向图，重复如上操作。 第第37页页 共共49页页 算法步骤i.作零流费用有向图)(0fd 上的非零弧上的非饱和弧 )1ijb 添加反向弧，权为 上的零弧上的饱和弧 )2ijb 原弧反向，权为iii. 重复 ii 。ii.找 的最短路 ，不存在则结束。否

15、则， 调整流量得新的最小费用可行流 。若 算法结束；否则构造 对应的有向图tsvv f)( fdvfv )(f第第38页页 共共49页页例6-6 设要从仓库 vs 向商店 vt 运送物资，问应如何 调运使运输费用最省。vtv1v3vs(4,10)(1,7)(1,8)(2,5)(3,10)(2,4)(6,2)v2其中， 分别表示单位运价和运输能力。),(ijijb 第第39页页 共共49页页vtv1v2v3vs4112326d( f0 )vtv1v2v3vs0555000f1vtv1v3vs(4,10)(1,7)(1,8)(2,5)(3,10)(2,4)(6,2)v2d( f1 )vtv1v2v

16、3vs4112326-1-1-2第第40页页 共共49页页vtv1v2v3vs2755000f2v11-1vtv2v3vs 41-2326-4d( f2 )-1-1vtv1v2v3vs2785330f3v ( f3 ) = 2+8=10 = v第第41页页 共共49页页三、网络计划三、网络计划（关键路径法）（关键路径法）1. 问题的一般提法设：有一项工程，分为若干道工序；已知各工序间的先后关系，以及各工序所需时间 t。 问：（1）工程完工期 t=？ （2）工程的关键工序有哪些？第第42页页 共共49页页例6-7为筹建某餐馆，需制定计划。将工程分为 14 道工序，各工序需时及先后关系如下表。试求该工程完工期 t及关键路径。第第43页页 共共49页页2. 求解方法关键路径法（cpm） 绘制工程网络图 u 顺序：按工序先后从左至右； u 顶点：表示相邻工序