精品第4章 图与网络.docx

精品第4章 图与网络.docx

《精品第4章 图与网络.docx》由会员分享，可在线阅读，更多相关《精品第4章 图与网络.docx（21页珍藏版）》请在冰点文库上搜索。

精品第4章图与网络

第4章图与网络

一、图与网络的基本概念

1.概念的引入

2.例1我国北京、上海等10个城市间的铁路交通示意图如图所示，它反映了这10个城市的铁路分布情况。

图中，用点代表城市，点与点之间的连线代表两个城市之间的铁路线。

3.

基本概念

（1）图

图：

图是由一些点以及点之间的连线所组成的。

其中，这些点又称为顶点。

边（弧）：

两顶点之间不带箭头的连线称为边；带箭头的连线称为弧。

边（或弧）上相应的数值称为边（或弧）的权。

无向图：

由点和边构成的图称为无向图（简称图），记作G=（V，E），其中V、E分别是G的顶点集合和边的集合。

连接两顶点vi,vj∈V的边e记为e=（vi，vj）或e=（vj，vi）。

有向图：

由点和弧构成的图称为有向图，记作D=（V，A），其中V、A分别是D的顶点集合和弧的集合。

从起始点vi∈V指向终点vj∈V的弧a记为a=（vi，vj）≠（vj，vi）。

多重边和环：

两个顶点间具有两条以上的边称为多重边；若边的两端为同一顶点则称其为环，如图1中的“边7”。

多重图和简单图：

含多重边的图称为多重图；无环且无多重边的图称为简单图。

图1环图2支撑子图

支撑子图：

如果图G=（V，E），G'=（V'，E'）且V'

V，E'

E，则称G'为G的子图，如图2（b）所示；若在同一图中，V'=V，E'

E，则称G'为G的支撑子图，如图2（c）所示。

（2）链

链：

在图G=（V，E）中，由一些顶点和边所组成的交错序列{v1,e1,v2,e2,…,vk-1,ek,vk

}就称为一条联结顶点v1、vk的链。

开链和闭合链：

起点和终点不是同一顶点的链，则称其为开链，否则就称其为闭合链。

单纯链和基本链：

一条没有重复边的链称为单纯链，如图3中的边序列{5,6,2,7,8}；一个没有重复顶点的链称为基本链，如图3中的边序列{1,2,3}。

路和回路：

一个开的基本链称为路，如图中的边序列{1,6,7,3}；一个闭合的基本链称为回路，如图中的边序列{1,6,5}。

连通图：

如果在一个图中任意两个不同的顶点之间至少有一条路，则该图就称为连通图。

图3链图4树

（3）树

树：

如果连通图G的子图Gl也是连通的，并包含了G的所有顶点，且没有回路，则称Gl为G的一个生成树（简称树），记为T，如图4中的（b）、（c）、（d）即为图（a）的树：

T1={l,3,5}，T2={2,3,5}，T3={2,4,5}。

组成树的边就称为树枝。

树的性质如下：

树的任意两个顶点之间只有一条链；

在树中不相邻的两个顶点间添上—条边，则恰好得到一个回路；

在树中去掉任何一条边，则成为不连通图；

含有n个顶点的树，则有n-1条边。

例2已知有五个城市，试问如何在它们之间架设电话线，使任何两个城市都可以互相通话（允许通过其它城市），且电话线的根数最少？

解用五个点v1,v2,v3,v4,v5代表五个城市，如果某两个城市之间架设电话线，则在相应的两点之间连一条边，则该电话线网就可以用一个图来表示。

为了使任何两个城市都可以互相通话，则此图必须是连通图；另外，若此图中有回路，从回路上任意去掉一条边，使余下的图仍是连通的，且可以省去一根电话线。

因此，满足要求的电话线网所对应的图必定是一个树，如图5所示。

（注意：

由于连通图对应的树有多个，故这里只给出了其中一个树）

图5电话线网图6割集

（4）割集

割集：

将连通图分割为两个子图所需割断的最少边集就称为割集，如图6中的边集{8,9}、{1,3,6}、{4,5,6}等。

注意：

割集的定义表明，当去掉构成割集的一组边时，则原连通图被分割成相互分离的两部分；而只要少去掉一条边，则被分开的两部分仍是连通的。

例如，边集{7,8,9}就不是割集，因为移去这个边集可以使图分离为两部分，但若再连上边7，已分离的图仍不能连通，不符合割集的定义。

最小割集：

对于一个图有若干个割集，其中边数最少的割集，则称其为最小割集（简称最小割），如图6中的边集{8,9}。

二、最短路问题

1.问题的提出

例3（管道铺设问题）从油田铺设管道，把原油运输到原油加工厂。

要求管道必须沿图7所给定的路线铺设，图中v1点为油田，v9点为原油加工厂，弧权为相应路段的管道长度，试问如何铺设管道才能使管道总长最短？

图7油田管道路线图图8油田管道最短路线图

解显然，可能的油田管道铺设方案有多种，而不同方案的管道总长不同，则现在的问题是要寻求一条从v1到v9的路线，使油田的管道总长最短。

若v1-…-vi-v9是从v1到v9的最短路，则v1-…-vi是从v1到vi的最短路，根据这一原理来求出该最短路问题。

（1）与v1直接相连的点为v2、v3，但l13=2

（2）与v1v3直接相连的点为v2、v5、v6，则l12=4，l15=6，l16=6，min{l12,l15,l16}=4，连接v1v2；

（3）与v1v2v3直接相连的点为v4、v5、v6，则l14=10，l15=6，l16=6，min{l14,l15,l16}={l15,l16}=6，连接v3v5、v3v6；

（4）与v1v2v3v5v6直接相连的点为v4、v7、v8，则l14=10，l17=10，l18=8，min{l14,l17,l18}=8，连接v5v8；

（5）与v1v2v3v5v6v8直接相连的点为v4、v7、v9，则l14=10，l17=10，l19=12，min{l14,l17,l18}={l14,l17}=10，连接v2v4、v5v7；

（6）与v1v2v3v4v5v6v7v8直接相连的点为v9，则l19=12，min{l19}=12，连接v7v9、v8v9；

（7）至此已将所有的点都相连，如图8所示。

由图可见，v1v3v5v7v9或v1v3v5v8v9为所求的最短路线，相应的油田管道总长均为12。

2.两固定顶点间的的最短路问题——标号算法（又称狄克斯屈拉算法）

利用狄克斯屈拉（Dijkstra）算法，可以求出从起点v1到终点vn（即两个固定顶点间）的最短路，但该算法只适用于各弧权lij均为非负的情况（即lij≥0），一般在实际的管理工作中都能满足这一要求。

注意：

标号算法不适用于弧权为负的情况（但这种情况可以用福特算法来求解，略）。

标号算法的基本思路是：

从起点v1开始，对每个顶点给定一个标号，标号分临时标号T和固定标号P两类。

顶点vi的临时标号记为T（i），它表示起点v1到顶点vi最短距离的上界；顶点vi的固定标号记为P（i），它表示起点v1到顶点vi的实际最短距离。

已得到P类标号的顶点不再改变其标号，而没有标上P类标号的顶点则必须标上T类标号，算法的每一步都要把某一顶点的T类标号改为P类标号，直到终点vn获得P类标号时，就可求得从起点v1到终点vn的最短路线。

标号算法的计算步骤如下：

（1）给起点v1标上固定标号P

（1）=0，表示v1到v1的最短距离为零；其余顶点vj（j=2,…,n）标上临时标号T（j）=∞，表示v1到vj暂时无路；

（2）设顶点vi是刚得到P类标号的顶点，把与顶点vi有弧直接相连且又属于T类标号的各顶点vj的标号，改为以下新的T类标号，即

T（j）=min{T（j），P（i）+lij}

（3）在T类标号中选出标号最小的顶点j0，并将其临时标号T（j0）改为固定标号P（j0）；

（4）若终点vn获得P类标号，则算法终止，最短路已经找到，否则返回

（1）。

确定由起点v1到终点vn最短路径的方法有以下两种：

其一，在算法进行时作出标记，以表明每个固定标号的顶点是由哪个顶点得到标号的，然后从终点反向追踪到起点，这样就可找出最短路径；

其二，从终点反向逆算，看哪个顶点的固定标号与终点固定标号的差值恰好等于与终点直接相连的相应弧权，如顶点j，则对顶点j之前的顶点再做类似的逐点推算，直到起点为止，这样也可找到最短路径；

例4（邮递员投递路线问题）已知某邮递员沿着图9所示的街道网络投递邮件，试求从顶点1到顶点6的最短距离及其路线。

图9街道网络路线图

解用最短路标号算法求解时，首先给顶点1标上P类标号，即P

（1）=0，其余顶点标上T类标号，且T（j）=∞（j=2,…,6）。

第一步

与顶点1直接相连且又为临时标号的顶点是2和3，则将这两个顶点的T类标号改为

T

（2）=min{T

（2），P

（1）+l12}=min[∞，0+4]=4

T（3）=min{T（3），P

（1）+l13}=min[∞，0+3]=3

在所有的T类标号中，T（3）=3最小，于是令P（3）=3，即顶点3获得固定标号；

第二步

与顶点3直接相连且又为临时标号的顶点是2和5，则将它们的T类标号改为

T

（2）=min{T

（2），P（3）+l32}=min[4，3+2]=4

T（5）=min{T（5），P（3）+l35}=min[∞，3+2]=5

在所有的T类标号中，T

（2）=4最小，于是令P

（2）=4；

第三步

与顶点2直接相连且又为临时标号的顶点是4和5，则将它们的T类标号改为

T（4）=min{T（4），P

（2）+l24}=min[∞，4+3]=7

T（5）=min{T（5），P

（2）+l25}=min[5，4+1]=5

在所有的T类标号中，T（5）=5最小，于是令P（5）=5；

第四步

与顶点5直接相连且又为临时标号的顶点是4和6，则将它们的T类标号改为

T（4）=min{T（4），P（5）+l54}=min[7，5+2]=7

T（6）=min{T（6），P（5）+l56}=min[∞，5+4]=9

在所有的T类标号中，T（4）=7最小，于是令P（4）=7；

第五步

与顶点4直接相连且又为临时标号的顶点只有6，则将它的T类标号改为

T（6）=min{T（6），P（4）+l46}=min[9，7+3]=9

显然应令P（6）=9，即终点（顶点6）获得固定标号，算法到此结束，则顶点1到顶点6的最短距离为9。

要找出从顶点1到顶点6最短路的各顶点顺序，可从顶点6反向逆算。

与顶点6直接相连的是顶点4和顶点5，而顶点6与顶点4或顶点5固定标号之差为2和4，与顶点6直接相连的弧中只有弧（5,6）的弧权为4，因此顶点6之前的是顶点5。

类似地可以推算出，顶点5之前的是顶点3，顶点3之前的是顶点1，即有一条最短路线为1→3→5→6；或者得出，顶点5之前的是顶点2，顶点2之前的是顶点1，即另一条最短路线为1→2→5→6。

这两条路线的最短距离均为9。

注意：

标号算法可用于任何弧（边）权为正的有向图（无向图）。

3.任意两顶点间的最短路问题——福劳德算法

设网络图的顶点编号为1,2,…,N，令Dm矩阵的元素dijm为顶点vi到vj的一条最短路长度，该路径的中间顶点只有m个。

若不存在这种最短路，则dijm=∞。

由dijm的含义可知，dij0为直接相连（即相邻）的两顶点间的最短长度，且dii0=0；dijN为所要确定的任意两顶点vi、vj之间的最短距离。

福劳德算法的求解步骤为：

（1）确定D0矩阵，其元素dij0为任意两相邻顶点vi、vj间的最短路长度，若顶点vi、vj间不存在这种最短路，则dij0=∞；若i=j，则dii0=0；

（2）对m=1,2,…,N，依次按下式由Dm-1矩阵确定Dm矩阵：

dijm=min{dimm-1+dmjm-1，dijm-1}

若选出的最小元素是由dimm-1+dmjm-1决定的，则记下m；若二者相等或取决于dijm-1，则不记录；

（3）如此类推，直到计算出DN矩阵为止。

例5（防火安全问题）某工地有四个重点防火点，道路和防火点位置如图10所示，试问安全员该如何确定任一防火点到其他防火点的最短路径？

图10防火点位置及其道路示意图

解应用福劳德算法：

第一步，写出D0矩阵

第二步，根据D0矩阵列表求出D1矩阵和相应的路径

dij1=min{di10+d1j0,dij0}

中间点

dij1=min{di10+d1j0,dij0}

中间点

d111=d110=0

d311=min{6+0,6}=6

d121=min{0+1,1}=1

d321=min{6+1,5}=5

d131=min{0+2,2}=2

d331=min{6+2,0}=0

d141=min{0+1,1}=1

d341=min{6+1,2}=2

d211=min{2+0,2}=2

d411=min{1+0,1}=1

d221=min{2+1,0}=0

d421=min{1+1,∞}=2

1

d231=min{2+2,7}=4

1

d431=min{1+2,4}=3

1

d241=min{2+1,∞}=3

1

d441=min{1+1,0}=0

其路径矩阵为

其中，D1中的矩阵元素表示中间点为1（即m

=1）时各点间的最短距离，相应的路径表示经过中间点1的最短路径。

例如，d421=2表示路径4→1→2对应的距离为2。

第三步，由D1矩阵按上述方法求出D2矩阵和相应的路径

此时中间点为两个，即m=2，其计算公式为

dij2=min{di21+d2j1,dij1}

dij2=min{di21+d2j1,dij1}

中间点

dij2=min{di21+d2j1,dij1}

中间点

d112=min{1+2,0}=0

d312=min{5+2,6}=6

d122=min{1+0,1}=1

d322=min{5+0,5}=5

d132=min{1+4,2}=2

d332=min{5+4,0}=0

d142=min{1+3,1}=1

d342=min{5+3,2}=2

d212=min{0+2,2}=2

d412=min{2+2,1}=1

d222=min{0+0,0}=0

d422=min{2+0,2}=2

1

d232=min{0+4,4}=4

1

d432=min{2+4,3}=3

1

d242=min{0+3,3}=3

1

d442=min{2+3,0}=0

由于没有选择中间点，所以对应的路径与上一步相同。

注意，D2中的矩阵元素表示经过两个中间点时各点间的最短距离，而不是经过第二个顶点时各点间的最短距离，因为公式dij2=min{di21+d2j1,dij1}中di21+d2j1或dij1为已经经过一个中间点的值。

第四步，由D2矩阵按上述方法求出D3矩阵和相应的路径

此时中间点为三个，即m=3，其计算公式为

dij3=min{di32+d3j2,dij2}

dij3=min{di32+d3j2,dij2}

中间点

dij3=min{di32+d3j2,dij2}

中间点

d113=min{2+6,0}=0

d313=min{0+6,6}=6

d123=min{2+5,1}=1

d323=min{0+5,5}=5

d133=min{2+0,2}=2

d333=min{0+0,0}=0

d143=min{2+2,1}=1

d343=min{0+2,2}=2

d213=min{4+6,2}=2

d413=min{3+6,1}=1

d223=min{4+5,0}=0

d423=min{3+5,2}=2

1

d233=min{4+0,4}=4

1

d433=min{3+0,3}=3

1

d243=min{4+2,3}=3

1

d443=min{3+2,0}=0

对应的路径仍同上。

第四步，由D3矩阵按上述方法求出D4矩阵和相应的路径

此时中间点为四个，即m=4，其计算公式为

dij4=min{di43+d4j3,dij3}

其计算结果为

dij4=min{di43+d4j3,dij3}

中间点

dij4=min{di43+d4j3,dij3}

中间点

d114=min{1+1,0}=0

d314=min{2+1,6}=3

4

d124=min{1+2,1}=1

d324=min{2+2,5}=4

4

d134=min{1+3,2}=2

d334=min{2+3,0}=0

d144=min{1+0,1}=1

d344=min{2+0,2}=2

d214=min{3+1,2}=2

d414=min{0+1,1}=1

d224=min{3+2,0}=0

d424=min{0+2,2}=2

1

d234=min{3+3,4}=4

1

d434=min{0+3,3}=3

1

d244=min{3+0,3}=3

1

d444=min{0+0,0}=0

对应的路径矩阵为

由D4矩阵可求出网络图中任意两点间的最短距离，并确定所对应的路径。

例如，点3到点2之间的的最短距离是4；且由路径矩阵可知，先由第3行第2列对应的4确定由3→4，再查该矩阵的第4行第2列对应的1确定由4→1，最后查该矩阵的第1行第2列对应的0确定1→2可直接到达，因此确定点3到点2之间的的最短路径为3→4→1→2。

三、最大流问题

1.基本假设和符号含义

（1）将出发点称为源点S；终点称为汇点T；其余点称为中间点i；

（2）假设源点有无限多的物资、能量、信息及人力等要运出，而汇点则有无限大的仓库来存储这些物资、能量、信息及人力等；

（3）假设中间点不存储任何物资、能量、信息等，只起传递作用；

（4）由i点到j点的最大传递数量规定为线路的容量，用C（i,j）表示；

（5）规定X（i,j）为由i点到j点的实际通过流量。

注意：

实际支路通过流量X（i,j）等于支路容量C（i,j），就称为支路饱和。

2.基本定理及其有关概念

（1）流量守恒定律

根据上述假设，仿照电路中的基尔霍夫定律，可以得到流量守恒定律。

如果∑X（i,j），j∈V（i）表示流出i点的总流量，其中V（i）为可直接到达j点的点集合；而∑X（j,i），j∈R（i）表示流入i点的总流量，其中R（i）为可直接到达i点的点集合，由于基尔霍夫定律中流入节点的电流之和与流出节点的电流之和相等的原理，与上述假设中的中间点只起传递作用相似，因此有

上式就称为流量守恒方程，式中f表示流量。

由假设（4）可知，0≤X（i,j）≤C（i,j），即实际流量为非负且不大于线路的容量，因此，网络最大流问题的数学规划模型为

该问题单纯形法可以得到最优解，故最大流问题本质上是线性规划问题，但是当网络较大时，约束方程的数量和变量的个数较多，线性规划模型很大，不便于求解，则利用图的特性可是问题的求解变得容易。

（2）割集和割集容量

设G是一个连通图，则满足下列条件的边的集合就称为割集：

把这些边全部从图G中去掉，则图G成为不连通的两部分；

把该边集合的任何子集从图G中去掉，则图G仍是连通的。

割集中各支路容量的和称为割集容量。

（3）最大流——最小割定理

定理：

网络中从源点S到汇点T的最大流量就等于把S和T分开的最小割集容量。

3.标记法

由最大流——最小割定理可知，在求解网络最大流问题时，可以利用穷举法列出所有将源点S和汇点T分开的割集，并计算其相应的割集容量，从而确定其最小割集容量，即最大流量。

这种方法虽然准确，但过于繁琐，因此采用标记法来求解网络最大流问题。

标记法的基本思路是：

先假设网络各支路中有一个满足流量守恒方程的初始流量，该初始流量就称为“可行流”。

选择可行流的方法有两种：

为了计算方便，可将可行流全部选为零，因为零也是符合流量守恒方程的；

为了加快计算速度，通常把可行流选择成使网络中某些主要支路饱和。

然后在该可行流的基础上，再试探着对其进行扩充，一次次地试探扩充，直到再也无法扩充为止，这样就找到了该网络的最大流。

标记法的求解步骤如下：

第一步，先给源点S以标记（-,∞），其中“-”表示开始，依据假设条件

（1）可知“∞”表示进入源点S的流量可无穷大，这时源点S成为已标记未检查的点。

第二步，用已标记未检查的点i对有联系的未标记的点j进行检查

（1）首先检查从已标记点出发的支路

如果初始流量小于最大容量，即X（i,j）

点提供的数量和支路可以进一步扩充的流量中最小的一个，且ε（j）=min{ε（i）,C（i,j）-X（i,j）}，如图11（a）所示；

如果X（i,j）=C（i,j），则不标记；

完成上述检查后，由i点出发的支路检查完毕，j点成为已标记未检查的点。

（2）检查流向节点的支路

如果X（j,i）>0，则将j点标记为（i-,ε（j）），表示i点向j点可以少提供的流量为ε（j），实质上也等于j点向i点多提供的流量为ε（j），其中ε（j）表示i点可以少提供的数量和流量中最小的一个，且ε（j）=min{ε（i）,C（j,i）}，如图11（b）所示；

图11标记法

当ε（i）

X（i,j）=0不标记；

通过对i点的检查，使j点成为已标记未检查的点，而i点则由已标记未检查的点变为已标记已检查的点，这样一直进行到汇点T也标记成（n+,ε（T））为止。

第三步，从汇点T反向查找可以扩充的路径，并确定扩充量

其方法是：

由汇点T的标记（n+,ε（T）），倒推到n点，再按n点的标记倒推到n-1点，最后一直倒推到源点S为止，就可以找到由源点S到汇点T的一条可以扩充的路径。

在此扩充线路上标记相应的值ε（j），并选ε*（j）=min{ε（j）}作为扩充量。

第四步，根据扩充路径上标记的扩充流量对支路（i,j）扩充时，如果j点的标记为i+，初始流量X（i,j）就增加ε*（j）；如果j点的标记为i-，初始流量X（i,j）就减少ε*（j），这就完成了一次扩充，得到一个新的可行流。

第五步，重复上述步骤，一直到无扩充路径为止，即得到该网络的最大流。

例6某工地需要大量砾石，采石场与工地间的公路网及运输能力如图12所示，为了安排运输计划，试确定该公路网可运输砾石的最大数量为多少？

图12公路网及运输能力

解采用标记法，假设已预先给定初始可行流并用括号标注在线路旁。

第一步，点S标记（-,∞）；

第二步，对已标记、未检查的S点进行检查。

先看由i出发的支路（S,2）、（S,

3）。

因C（S,2）=13，X（S,2）=7，C（S,2）>X（S,2），则点2应标记（S+,ε

（2）），ε

（2）=min{∞,C（S,2）-X（S,2）}=min{∞,6}=6，所以点2标记（S+,6），它表明由S可增加6单位流量到点2。

此时，由于C（S,3）=9，X（S,3）=9为饱和支路；无指向点S的支路，故点S已检查完，成为已标记、已检查的点。

点2成为已标记未检查的点，对其进行检查。

先看由点2出发的两条支路（2,4）、（2,5），C（2,5）=X（2,5），C（2,4）=X（2,4）均为饱和支路；再看流向点2的支路（3,2），因X（3,2）>0，ε（3）=min{ε

（2）,C（3,2）}=min{6,4}=4，所以点3标记（2-,4），表明点2可以向点3提供4个单位，或点3可以少向点2提供4个单位。

故点2成为已标记、己检查的点，点3成为已标记未检查的点。

再继续按第二步检查点3，在支路（3,4）中，C（3,4