第4章 网络规划

第4章

网络规划

图的基本概念

树和最小支撑树

最短路问题

网络上的最大流问题本章内容重点第4章

网络规划§4.1

图论导引§4.2最小支撑树§4.3最短路问题§4.4网络上的最大流问题§4.1

图论导引

图论已经广泛应用于物理学、控制论、信息论、工程技术、交通运输、经济管理、电子计算机等各项领域。生产和生活中的许多问题，都可以用图论的理论和方法来加以解决，例如：各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局，等。§4.1图论导引1736年瑞士科学家欧拉发表第一篇图论方面的论文，解决著名的哥尼斯堡七座桥问题：布勒格尔河流经哥尼斯堡，河中有两个中心岛，它们彼此以及河岸共有七座桥连接。能否无遗漏又不重复地走遍七座桥而又回到出发地？（图4.1a）§4.1图论导引图4.1a§4.1图论导引1736年欧拉把这个问题抽象成图4.1b所示图形的一笔画问题，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出。§4.1图论导引图4.1bACDB

例1

有六个公司存在债务关系，我们分别用点v1…v6表示这六个公司，它们之间的债务情况，可以用下图4.3反映出来：如v1借债给v2，v2借债给v3，如此等等。§4.1图论导引§4.1图论导引v3v1v2v4v6v5图4.3可以看出：用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系；由点和线所构成的图，能够反映实际问题的相互关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。§4.1图论导引

图是由点和点与点之间的线所组成的。通常，把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。如果一个图是由点和边所构成的，则称为无向图，记作G=(V，E)，其中V表示顶点集，E表示边集。连接vi,vj

V的边记作[vi,vj]，或者[vj,vi]。如果一个图是由点和弧所构成的，则称为有向图，记作D=(V,A)，其中V表示顶点集，A表示弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。§4.1图论导引例2

图4.4是一个无向图G=（V，E）,其中V={v1,v2,v3,v4},E={e1,e2,e3,e4,e5,e6}§4.1图论导引v4v3v2v1图4.4e1e6e3e4e2e5例3

图4.5是一个有向图D=（V，A）,其中V={v1,v2,v3,v4,v5,v6,v7}A={(v1,v2),(v1,v3),(v3,v2),(v2,v4),(v2,v5)(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)}§4.1图论导引v7v5v3v4v2v1v6图4.5

下面介绍一些常用的名词：如果边[vi,vj]

E，则称vi,vj是边的端点，或者vi,vj是相邻的。如果一条边的两个端点是相同的,则称之为环，如图4.4中的边e5是环。如果两个端点之间有两条以上的边，则称它们为多重边，如图4.4中的边e2和e3。一个无环无多重边的图称为简单图。§4.1图论导引

设G1=[V1,E1],G2=[V2,E2]子图：如果V2

V1,E2

E1

，称

G2

是G1

的子图；支撑子图：如果V2

=V1,E2

E1

，称G2

是G1

的支撑子图.§4.1

图论导引

§4.1图论导引G16个点，9条边G2：子图§4.1图论导引5个点，4条边

§4.1图论导引G3：支撑子图6个点，5条边链：由两两相邻的点及相关联的边构成的点边序列。如：v1,e1,v2,e2,v3,e3,v4,…,vn-1,en-1,vn

.

v1和vn分别为链的起点和终点。简单链：链中所含的边均不相同。初等链：链中所含的点均不相同。§4.1图论导引圈：起点和终点相同的链。连通图：图中任意两点之间均至少有一条链。树：一个无圈的连通图叫做树。§4.1图论导引§4.1图论导引树的性质：（1）树的充分必要条件是任意两个顶点之间有且仅有一条链。（2）在树中的两个不相邻的点之间加上一条边，那么恰好得到一个圈。（3）如果树中点的个数为n，那么树中边的个数为n-1。§4.1图论导引支撑树6个点，5条边有向图弧：a=(u,v)A，起点u，终点v；路：若有从u到v（不考虑方向）链，且各方向一致，则称之为从u到v的路；初等路：各顶点都不相同的路；初等回路：u=v的初等路;连通图：若不考虑方向是无向连通图;§4.1图论导引Return§4.2最小支撑树图G=（V，E），对于G中的每一条边[vi,vj]，相应地有一个数Wij，那么称这样的图G为赋权图，Wij称为边[vi,vj]的权。

这里的权，是具有广义的数量值，例如：长度，费用、流量等。最小支撑树问题是赋权图的最优化问题之一。§4.2最小支撑树

在已知的几个城市之间联结电话线网或交通线网，要求总长度最短和总建设费用最少，可以归结为最小支撑树问题。

Kruskal算法

步骤1

把图中所有的边，按照每一条边的权从小到大的次序排列起来，并选取最前面的一条边，作为支撑树的第一条边，把它从排列中划去。§4.2最小支撑树

Kruskal算法

步骤2

如果排列中已经没有边，那么得到的支撑树就是最小支撑树，算法终止；否则，检查排列中最前面的一条边，转步骤3。§4.2最小支撑树

Kruskal算法步骤3

如果选取最前面的边与已经有的支撑树不会形成圈，就把它加到支撑树中去，并把它从排列中划去；否则，直接把它从排列中划去，转步骤2。§4.2最小支撑树§4.2最小支撑树v6v5v2v3v4v162453544v3v2v1v4v6v55131421，2，3，4，4，5，5，6，7已得到最小支撑树，权=1+2+3+4+5=15.！一棵树点的个数为n，边的个数为n-1。如果再加一条边，一定会产生圈。例4（续）两个习题：§4.2最小支撑树§4.2最小支撑树v6v5v2v3v4v1v7v10v9v11v81212631110968991111512127最小支撑树的权=751.求下图最小支撑树§4.2最小支撑树v6v4v1v6v8v5v10v7251428187661312204167最小支撑树的权=73v2v3v92.求下图最小支撑树§4.3最短路问题

最短路径问题是图论中十分重要的最优化问题之一，可以解决生产实际中的许多问题，比如：城市中的管道铺设，线路安排，工厂布局，设备更新等等；也可以用于解决其它的最优化问题。最短路问题——Dijkstra算法（1959年）

§4.3最短路问题Dijksta算法基本步骤（1）给发点vs标号(0,s)，表示从vs到终点vt的距离为0；（2）找出已标号的点的集合I、没标号的点的集合J以及弧的集合{vi,vj|vi

I,vj

J}；§4.3最短路问题Dijksta算法基本步骤（3）如果上述弧的集合是空集，则算法结束。此时有两种情况：如果vt已标号(lt,kt)，则从vs到vt的距离即为lt

，而从vs到vt的最短路，可以从vt反向追踪到vs而得到。如果vt未标号，则不存在从vs到vt的（有向）路。如果上述弧的集合不是空集，转到第（4）步；

§4.3最短路问题Dijksta算法基本步骤（4）对上述弧集合的每一条弧，计算sij=li+cij，找出sij值最小的弧，不妨设为(vc,vd)，给此弧的终点以双标号(scd,c)，返回第（2）步。

§4.3最短路问题例5

下图是单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。§4.3最短路问题8114219182421225V3V1V2V8V4V5V6V7例5（续）§4.3最短路问题8114219182421225V3V1(0,0)V2V8V4V5V6V71128解：§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2V8V4V5V6V71128解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2V8V4V5V6V7112876解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4V5V6V7112876解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4V5V6V711287615解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4V5V6(7,3)V711287615解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4V5V6(7,3)V71128761581115解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4(8,6)V5V6(7,3)V71128761581115解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4(8,6)V5V6(7,3)V7112876158112015解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4(8,6)V5V6(7,3)V7(11,6)112876158112015解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4(8,6)V5V6(7,3)V7(11,6)11287615811201315解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,4)V4(8,6)V5V6(7,3)V7(11,6)11287615811201315解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,7)V4(8,6)V5V6(7,3)V7(11,6)解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,7)V4(8,6)V5V6(7,3)V7(11,6)解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,7)V4(8,6)V5V6(7,3)V7(11,6)解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,7)V4(8,6)V5V6(7,3)V7(11,6)解（续）§4.3最短路问题8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,7)V4(8,6)V5V6(7,3)V7(11,6)解（续）§4.3最短路问题8114219182421225V3V1V2V8V4V5V6V7最短链问题解（续）§4.3最短路问题8114219182421225V3V2V8V4V5V6V7V1(0,0)解（续）§4.3最短路问题8114219182421225V3V2V8V4V5V6V7V1(0,0)8211解（续）§4.3最短路问题8114219182421225V2V8V4V5V6V7V1(0,0)8211V3(2,1)解（续）§4.3最短路问题8114219182421225V2V8V4V5V6V7V1(0,0)8211V3(2,1)674解（续）§4.3最短路问题8114219182421225V2V8V4(4,3)V5V6V7V1(0,0)8211V3(2,1)647解（续）§4.3最短路问题8114219182421225V2V8V4(4,3)V5V6V7V1(0,0)8211V3(2,1)674165解（续）§4.3最短路问题8114219182421225V2V8V4(4,3)V5V6(5,4)V7V1(0,0)8211V3(2,1)674165解（续）§4.3最短路问题8114219182421225V2V8V4(4,3)V5V6(5,4)V7V1(0,0)8211V3(2,1)6741657139解（续）4.3最短路问题8114219182421225V2(6,3)V8V4(4,3)V5V6(5,4)V7V1(0,0)8211V3(2,1)6741657139解（续）§4.3最短路问题8114219182421225V2(6,3)V8V4(4,3)V5V6(5,4)V7V1(0,0)8211V3(2,1)674165713915解（续）§4.3最短路问题8114219182421225V2(6,3)V8V4(4,3)V5(7,6)V6(5,4)V7V1(0,0)8211V3(2,1)674165713915解（续）§4.3最短路问题8114219182421225V2(6,3)V8V4(4,3)V5(7,6)V6(5,4)V7V1(0,0)8211V3(2,1)6741657139158解（续）§4.3最短路问题8114219182421225V2(6,3)V8(8,5)V4(4,3)V5(7,6)V6(5,4)V7V1(0,0)8211V3(2,1)6741657139158解（续）§4.3最短路问题8114219182421225V2(6,3)V8(8,5)V4(4,3)V5(7,6)V6(5,4)V7V1(0,0)V3(2,1)解（续）§4.3最短路问题思考题：从V1到V8的最短路的距离为什么不会比最短链的距离小？

Return§4.4网络上的最大流问题

在许多实际的网络系统中都存在着最大流问题,例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。最大流问题算法——Ford-Fulkerson算法（1956年）§4.4网络上的最大流问题V6V3V2V5V1645126156735V4

上图是联结发点（起始地）v1和收点（目的地）v6的交通运输网，每一条弧（vi,vi）旁边的权cij表示这段运输线的最大通过能力（容量），货物经过交通冈从v1运送到v6.要求确定一个运输方案，使得从v1到v6的货运量最大，这个问题就是寻求网络系统的最大流问题。例6§4.4网络上的最大流问题V6V4V3V2V5V16,04,05,012,06,0515,06,07,03,01266V1V2V355,0371564V5V4V6流量|f|=0增量网络解：§4.4网络上的最大流问题V451266V1V2V35371564V5V6在增量网络中找到从V1到V6的路:V1-V3-V4-V6,路的容量为6。解（续）§4.4网络上的最大流问题V6V4V3V2V5V16,04,05,012,06,6515,66,07,63,01266V1V2V355,031964V5V4V6流量|f|=6增量网络66解（续）§4.4网络上的最大流问题V451266V1V2V3531964V5V666在增量网络中找到从V1到V6的路:V1-V2-V4-V6,路的容量为5。解（续）§4.4网络上的最大流问题V6V4V3V2V5V16,04,05,512,56,615,116,07,63,0766V1V2V355,031464V5V4V6流量|f|=11增量网络61155解（续）§4.4网络上的最大流问题V4766V1V2V3531464V5V661155在增量网络中找到从V1到V6的路:V1-V2-V3-V4-V6,路的容量为1。解（续）§4.4网络上的最大流问题V6V4V3V2V5V16,04,05,512,66,615,126,17,73,0665V1V2V355,03364V5V4V6流量|f|=12增量网络712651解（续）§4.4网络上的最大流问题V4666V1V2V353364V5V671265在增量网络中不存在从V1到V6的路，已经是最大流！解（续）§4.4网络上的最大流问题V6V3V2V5V100566121700V4最大流如下图所示，最大流的流量|f|=12。解（续）例7

以下图中给出的流作为初始流（流量|f|为12），求从发点V1到收点V6的最大流。V6V3V2V5V19,63,07,48,89,48,63,32,23,15,5V4§4.4网络上的最大流问题V6V3V2V54V6V3V2V5V19,63,07,48,89,48,63,32,23,15,5V444166流量|f|=12增量网络解：V6V3V2V5444166在增量网络中找到从V1到V6的路，容量为3：

V1-V3-V2-V4-V5-V6.

§4.4网络上的最大流问题解（续）V6V3V2V5V138223225V4V6V3V2V5V19,93,37,78,89,78,63,02,23,15,5V477169流量|f|=15增量网络解（续）V6V3V2V5V138223225V477169在增量网络中不存在从V1到V6的路，已达到最大流！§4.4网络上的最大流问题解（续）§4.4网络上的最大流问题最大流如下图所示，最大流的流量|f|=15。V6V3V2V5V19378760215V4解（续）§4.4网络上的最大流问题V8V5V2V7V154671232649V4例8

求V1到V8的最大流。V3V6538V8V5V2V7V154671232649V4V3V6538V8V5V2V7V15,04,06,07,012,03,02,06,04,09,0V4V3V65,03,08,0流量|f|=0增量网络解：V8V5V2V7V154671232649V4V3V6538在增量网络中找到从V1到V8的两条路:V1-V2-V4-V8和V1-V5-V7-V8，总容量为4+5=9。§4.4网络上的最大流问题解（续）V8V5V2V7V146373269V4V3V634V8V5V2V7V15,54,06,07,412,53,02,06,04,49,0V4V3V65,53,08,4流量|f|=9增量网络444555解（续）V8V5V2V7V146373269V4V3V634444555在增量网络中找V1到V8的两条路:V1-V2-V3-V8和V1-V5-V6-V8，总容量为3+4=7。§4.4网络上的最大流问题解（续）V8V5V2V7V133265V4V3V634V8V5V2V7V15,54,46,37,712,93,32,06,04,49,4V4V3V65,53,08,4流量|f|=16增量网络7449553344解（续）V8V5V2V7V133265V4V3V6347449553344在增量网络中找到从V1到V8的路，容量为2：

V1-V5-V6-V2-V3-V4-V8.§4.4网络上的最大流问题解（续）V8V5V2V7V11143V4V3V632V8V5V2V7V15,54,46,57,712,113,32,26,24,49,6V4V3V65,53,08,6流量|f|=18增量网络74611555346解（续）V8V5V2V7V11143V4V3V63274611555346在增量网络中不存在从V1到V8的路（到V7点为止），已达到最大流。§4.4网络上的最大流问题解（续）V8V5V2V7V154571132246V4V3V6506最大流如下图所示，最大流的流量：|f|=18.§4.4网络上的最大流问题解（续）例9

以下图中给出的流作为初始流（流量|f|为3），求从发点V1到收点V5的最大流。V5V3V2V15,13,02,14,23,22,12,2V4§4.4网络上的最大流问题V5V3V2V143112V41221211增量网络§4.4网络上的最大流问题解：V5V3V2V143112V41221