第三章 图与网络技术

第三章图与网络技术2023/3/29第一页，共五十页，2022年，8月28日图的概念

所谓图，就是顶点和边的集合，点的集合记为V，边的集合记为E，则图可以表示为：G＝（V，E），点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。

第一节图的基本概念2023/3/29第二页，共五十页，2022年，8月28日1.图与子图e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如

G：简单图：无环、无多重边的图。2023/3/29第三页，共五十页，2022年，8月28日2.关联与相邻3.链与圈2023/3/29第四页，共五十页，2022年，8月28日4.有向图与无向图，圈，回路比较：2023/3/29第五页，共五十页，2022年，8月28日一个没有圈的图称为一个无圈图或称为林。一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。定理以下关于树的六种不同描述是等价的：①无圈连通图。②无圈，q=p-1。③连通，q=p-1。④无圈，但若任意增加一条边，则可得到一个且仅一个圈。⑤连通，但若任意舍弃一条边，图便不连通。⑥每一对顶点之间有一条且仅有一条链。5.树2023/3/29第六页，共五十页，2022年，8月28日6.图的部分（支撑）树

若图G=（V，E）的子图T=（V，E’）是树，则称T为G的部分树或支撑树。特点——边少、点不少。性质：G连通，则G必有部分树。证：破圈、保连通。2023/3/29第七页，共五十页，2022年，8月28日第二节网络分析网络——赋权图，记D=（V，E，C），其中C={c1，…，cn}，

ci为边ei上的权（设ci）。网络分析主要内容——最小部分树、最短路、最大流。图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。2023/3/29第八页，共五十页，2022年，8月28日一.最小部分（支撑）树问题问题：求网络D的部分树，使其权和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例2求如图网络的最小部分树。v5v1v3v6v4v2v72552335757112023/3/29第九页，共五十页，2022年，8月28日避圈法是一种选边的过程，其步骤如下：1.从网络D中任选一点vi，找出与vi相关联的权最小的边[vi，vj]，得第二个顶点vj；2.把顶点集V分为互补的两部分V1,1，其中2023/3/29第十页，共五十页，2022年，8月28日用避圈法解例2v5v1v3v6v4v2v7255233575711•最小部分树如图上红线所示；最小权和为14。思考：破圈法是怎样做的呢？——见圈就破，去掉其中权最大的。2023/3/29第十一页，共五十页，2022年，8月28日二.最短路问题1.问题：求网络D中一定点v1到其它点的最短路。例3求如图网络中v1至v7的最短路，图中数字为两点间距离。v5v1v3v6v4v2v72552335757112.方法：标号法（Dijkstra，1959）给每点vj标号[dj，vi]，其中dj为v1至vj的最短距，vi为最短路上的前一点。2023/3/29第十二页，共五十页，2022年，8月28日标号法步骤：2023/3/29第十三页，共五十页，2022年，8月28日用标号法解例3v5v1v3v6v4v2v7255233575711[0，v1][2，v1][3，v1]其中2=min{0+2,0+5,0+3}其中3=min{0+3，0+5，2+2，2+7}[4，v2][7，v3][8，v5][13，v6]最短距为13；最短路为v1-v2-v3-v5-v6-v7。2023/3/29第十四页，共五十页，2022年，8月28日最短路问题的应用例子

某汽车公司正在制订5年内购买汽车的计划。下面给出一辆新汽车的价格以及一辆汽车的使用维修费用(万元)：年号1 234 5价格 2 2.1 2.3 2.4 2.6

汽车使用年龄 0–1 1–2 2–3 3–4 4–5 维修费用 0.7 1.1 1.5 2 2.5 试用网络分析中求最短路的方法确定公司可采用的最优策略。方法：以年号作顶点绘图，连线表示连续使用期间，以费用作路长。2023/3/29第十五页，共五十页，2022年，8月28日所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下规定：①网络有一个起点υs和一个终点υt②网络是有向网络，即流有方向性。③在网络各条弧上都有一个权，表示允许流过的最大流量。若以cij表示由υi到υj的弧上允许流过的最大流量，以xij表示实际流过该弧的流量，则0≤xij≤cij④网络中，除起点υs和终点υt之外的任何顶点，流入量总和应该等于流出量的总和。

三.最大流问题2023/3/29第十六页，共五十页，2022年，8月28日最大流问题的数学模型最大流问题的数学模型：

vs1011

65

4

7

3

915vt

v5

v3

v4

v22023/3/29第十七页，共五十页，2022年，8月28日最大流最小割集定理1网络中的最大流量fmax值大小是由网络中最狭窄处瓶颈的容量所决定的。

最大流－最小割集定理揭示了最小割集（网络中的瓶颈）容量与最大流量的关系，也提供了一个求最大流的方法。割集

网络割集容量最小割集所有割集中容量最小的一个割集。2023/3/29第十八页，共五十页，2022年，8月28日最大流最小割集定理2网络中的最大流量fmax值大小是由网络中最狭窄处瓶颈的容量所决定的。

网络割集容量最小割集所有割集中容量最小的一个割集。最大流－最小割集定理流过网络的最大流量等于最小割集的容量。

2023/3/29第十九页，共五十页，2022年，8月28日最大流最小割集定理3

vs

1011

65

4

7

3

915vt

v5

v3

v4

v2SS割集容量vsv2v3v4v5vt(vsv2)

(vsv3)24vsv2v3v4v5vt(vsv3)

(v2v4)(v2v5)20vsv3v2v4v5vt(vsv2)

(v3v2)(v3v4)

(v3v5)29………..…2023/3/29第二十页，共五十页，2022年，8月28日福德－富克逊方法原理算法的原理首先，依据最大流问题的要求，为网络分配一个可行流。所谓可行流，是指所有弧上流量满足容量限制，所有中间点满足平衡条件的流；若这一可行流的流量就是最大流量，则问题已经解决；若不是最大流量，则增加流量获得流量更大的可行流。2023/3/29第二十一页，共五十页，2022年，8月28日福德－富克逊方法流图

求一个初始可行流

是判断初始可行流是否最优结束

不是

求使目标得到改善的可行流2023/3/29第二十二页，共五十页，2022年，8月28日福德－富克逊方法图示算法原理图示初始流初始流2023/3/29第二十三页，共五十页，2022年，8月28日福德－富克逊方法讨论若弧(vi,vj)上的流量满足xij=cij，则称该弧为饱和弧，否则称为非饱和弧。若弧(vi,vj)上的流量xij=0。则称该弧为零流弧，否则称为非零流弧。一条从υs到υt的初等链是由υs开始的点、边序列，其中没有相同的点，也不考虑弧的方向。把这条链中的υs到υt方向相同的弧称为正向弧。把这条链中的υs到υt方向相反的弧称为逆向弧。在上述的可行流中，从υs到υt的某个初等链满足：①其上的正向弧均为非饱和弧。②其上的逆向弧均为非零流弧。则称该链为一条流量增广链。2023/3/29第二十四页，共五十页，2022年，8月28日福德－富克逊方法讨论流量增广链:从υs到υt的某个初等链满足①其上的正向弧均为非饱和弧。②其上的逆向弧均为非零流弧。结论：若在可行流中，存在从υs到υt的增广链，则该可行流不是最大流，其流量可以增加；否则若不存在从υs到υt的增广链，则该可行流是最大流。

2023/3/29第二十五页，共五十页，2022年，8月28日增广链的性质流量增广链:从υs到υt的某个初等链满足①其上的正向弧均为非饱和弧。②其上的逆向弧均为非零流弧。增广链的性质：Vs到增广链上任一点也有增广链;增广链上任一点到Vt也有增广链;2023/3/29第二十六页，共五十页，2022年，8月28日福德－富克逊方法步骤算法的步骤：①为网络分配初始流xij标在图中弧旁的()内②寻求增广链，若不存在，则已最优,否则③在增广链上调整流量，产生新的可行流。重复②、③两步，直到最优。2023/3/29第二十七页，共五十页，2022年，8月28日寻求增广链的方法寻求流量增广链的方法，是依据增广链的性质而产生的，其基本思路类似于最短树问题的生长法。从υs开始，逐个检查每个点υi，看是否存在从υs到υi的增广链。如果存在从υs到υi的增广链，而（ViVj）非饱和或（VjVi）非零流，则存在从V1到Vj的增广链。

2023/3/29第二十八页，共五十页，2022年，8月28日福德－富克逊方法示例标记化算法的步骤：①为网络分配初始流xij标在图中弧旁的()内

vs10115

6

4

7

3

915vt

v5

v3

v4

v2(4)(9)(3)(1)(5)(7)(5)(8)2023/3/29第二十九页，共五十页，2022年，8月28日福德－富克逊方法示例②寻求增广链从υs开始，赋上标记（－，∞），表示υs是源点，能够得到任意多的量。υs称为已标记的点。也表示增广链可以从V1延伸到V1

vs10115

6

4

7

3

915vt

v5

v3

v4

v2(4)(9)(3)(1)(5)(7)(5)(8)[-,∞]2023/3/29第三十页，共五十页，2022年，8月28日福德－富克逊方法示例②寻求增广链如果vi是已经标记的点,vj是未标记的点则当(vi,vj)是非饱和弧时,vj可以标记:[vi+,ej]ej=min{ei,bij-xij}

当(vj,vi)是非零流弧时,vj可以标记:[vi-,ej]ej=min{ei,xji}如果vt可以标记,则找到增广链,否则继续.如果对于一切未标记的点,均不能再标记,则已经是最优.2023/3/29第三十一页，共五十页，2022年，8月28日福德－富克逊方法示例②寻求增广链如图v1是已经标记的点,其它点是未标记的点

(v1,v2)是非饱和弧,v2可以标记:[v1+,e2]e2=min{e1,b12-x12}(v1,v3)是饱和弧,目前v3和其它点暂时不能标记，即暂时没有从v1到v3或其它点的增广链。

vs10115

6

4

7

3

915vt

v5

v3

v4

v2(4)(9)(3)(1)(5)(7)(5)(8)[-,∞][vs+,11]2023/3/29第三十二页，共五十页，2022年，8月28日福德－富克逊方法示例②寻求增广链如图v2是已经标记的点,v3是未标记的点

(v3,v2)是非零流弧,v3可以标记:[v2-,e3]e3=min{e2,x32}=min{11,3}[-,∞][vs+,11][v2-,3][v2+,4][v3+,3][v5+,4]

vs115

4

315vt

v5

v3

v4

v2(4)(9)(1)(5)(7)(5)(8)10

7

9(3)

62023/3/29第三十三页，共五十页，2022年，8月28日福德－富克逊方法示例③在增广链上调整流量。

vt已经标记,找到流量增广链。

vs10115

6

4

7

3

915vt

v5

v3

v4

v2(4)(9)(3)(1)(5)(7)(5)(8)[-,∞][vs+,11][v2-,3][v2+,4][v3+,3][v5+,4]正向流流量增加et，逆向流流量减少et

调整后流量f=172023/3/29第三十四页，共五十页，2022年，8月28日福德－富克逊方法示例②寻求增广链

vs10115

4

315vt

v5

v3

v4

v2(8)(9)(3)(1)(5)(7)(9)(8)(4)

9

6

7[-,∞][vs+,7][v2-,3][v3+,1][v3+,3][v4+,3]vt已经标记,找到流量增广链。2023/3/29第三十五页，共五十页，2022年，8月28日福德－富克逊方法示例③在增广链上调整流量。正向流流量增加et=3，逆向流流量减少et调整后流量f=20

vs10115

4

315vt

v5

v3

v4

v2(11)(9)(4)(5)(7)(9)(11)(4)

9

6

72023/3/29第三十六页，共五十页，2022年，8月28日福德－富克逊方法示例②寻求增广链Vsv2已经标记，其余点不能标记，已经最优最大流量fmax=20

vs10115

4

315vt

v5

v3

v4

v2(11)(9)(4)(5)(7)(9)(11)(4)

9

6

7[-,∞][vs+,4]2023/3/29第三十七页，共五十页，2022年，8月28日一、工程计划网络问题（关键路径法）

问题的一般提法设：有一项工程，分为若干道工序；已知各工序间的先后关系，以及各工序所需时间t。问：（1）工程完工期T=？（2）工程的关键工序有哪些？2.解法——关键路径法（CPM）（1）绘制工程网络图第六章网络计划2023/3/29第三十八页，共五十页，2022年，8月28日1）顺序：按工序先后从左至右；2）图中弧（箭线）：表示工序；

顶点（结点）：表示相邻工序的时间分界点，称事项，用表示。

相邻弧：表示工序前后衔接关系，称紧前（后）工序；3）要求：图中不得有缺口、回路和多重边。i缺口：多个始点或多个终点的现象。

（应当只有一个始点和终点）回路：方向一致的闭合链。2023/3/29第三十九页，共五十页，2022年，8月28日例1

为筹建某餐馆，需制定计划。将工程分为

14道工序，各工序需时及先后关系如下表。试求

该工程完工期T及关键路径。多重边：两点间有多于一条的边。AB处理方法：增加虚工序。AA’B2023/3/29第四十页，共五十页，2022年，8月28日工序内容紧前工序所需天数A购买炉灶及材料——10B购买室内设备——3C招集工人——1D选择开业地点——2E申请许可得到执照D7F修理门窗、粉刷墙壁E3G砌炉灶、水池A、F5H接通上下水道G4I安装室内设备B、H4J做好室内装饰B、H3K购进米面及副食品I、J6L张贴开业广告G3M人员训练C、I4N开业前操作试验K、L72023/3/29第四十一页，共五十页，2022年，8月28日工序ABCDEFGHIJKLMN紧前工序____DEAFGBHBHIJGCIKL所需天数1031273544363471CBAD2E3F4G5H6IJ7I’8KL9I’’M10N112023/3/29第四十二页，共五十页，2022年，8月28日（2）求完工期（用标号法）1）标出各事项的最早开始时间，

-给始点标；

-给任意点

标,Ej=Max{以为箭头的各箭之“箭尾+箭长tij”}10jEjj2)终点的中的T即完工期。nT1C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I’(0)8K(6)L(3)9I’’(0)M(4)10N(7)1102912172125253125382023/3/29第四十三页，共五十页，2022年，8月28日（3）求关键路（用标号法）2）计算各工序的时差R(i,j)=的-tij-的。ijji1）标出各事项的最晚开始时间，

-给终点标；-给任意点标,Li=Min{以为箭尾的各箭之“箭头-箭长tij”}niLiiT3）关键路径：由R(i,j)=0的关键工序组成的由至的路。n191C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I’(0)8K(6)L(3)I’’(0)M(4)10N(7)11029121721252531253838253425213117129202023/3/29第四十四页，共五十页，2022年，8月28日1C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I’(0)8K(6)L(3)9I’’(0)M(4)10N(7)1102912172125253125383825342521311712920完工期T=38（天）；关键路：D-E-F-G-H-I-K-N。由本例可见：关键工序头尾皆有=，但反之未必。