Chapter6 图与网络分析 ( Graph Theory and Network Analysis )

Presentation on theme: "Chapter6 图与网络分析 ( Graph Theory and Network Analysis )"— Presentation transcript:

1 Chapter6 图与网络分析 ( Graph Theory and Network Analysis )
本章主要内容： 图的基本概念与模型 树与图的最小树 最短路问题 网络的最大流

2 图的基本概念与模型 近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。 “哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到 1936 年匈牙利数学家 O.König写出了图论的第一本专著《有限图与无限图的理论》。 图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了——历史上许许多多数学猜想之一。 世界近代三大数学难题：费马最后猜想、哥德巴赫猜想和“四色”猜想。 它描述对一张地图着色的问题，在一维直线上用两种颜色可以区分任意多不同线段，在二维平面内至少需要四种颜色可以区分任意多区域（当然最简单的情况是二色，如国际象棋棋盘）；在三维空间内至少需要八种颜色可以区分任意多的立体，（最简单的情况还是二色，如NaCl） Königsberg桥对应的图

3 图的基本概念与模型 图论中图是由点和边构成，可以反映一些对象之间的关系。
一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。 图的定义： 若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作： 其中: V——点集 E——边集 ※ 图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。

4 图的基本概念与模型 例如：在一个人群中，对相互认识这个关系我们可以用图来表示。 可见图论中的图与几何图、工程图是不一样的。 (v1) 赵
周 (v6)吴 (v7)陈 e2 e1 e3 e4 e5 (v1) 赵 (v2)钱 孙(v3) 李(v4) 周(v5) 吴(v6) 陈(v7) e2 e1 e3 e4 e5 可见图论中的图与几何图、工程图是不一样的。

5 图的基本概念与模型 定义: 图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1]; e2=[v1,v2];
端点,关联边,相邻 若有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。

6 图的基本概念与模型 环, 多重边, 简单图 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。

7 图的基本概念与模型 次，奇点，偶点，孤立点
v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 次，奇点，偶点，孤立点 与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1)＝４,d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。 图的次: 一个图的次等于各点的次之和。

8 图的基本概念与模型 子图，部分图(支撑子图) 图G1={V1、E1}和图G2={V2，E2}如果有
称G1是G2的一个子图。若有 ，则称G1是G2的一个部分图(支撑子图)。 v3 e7 e4 e8 e6 e2 e3 v1 v2 v4 v5 v3 e4 e8 e5 e6 v2 v4 v5 （G图） (a) (b)

9 图的基本概念与模型 网络（赋权图） 设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。 权可以代表距离、费用、通过能力(容量)等等。 端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。 ① ② ③ ④ ⑤ ⑥ 9 10 20 15 7 14 19 25 6

10 图的基本概念与模型 图的矩阵描述： 如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有： 邻接矩阵、关联矩阵、权矩阵等。 1. 邻接矩阵 对于图G=（V，E），| V |=n， | E |=m，有nn阶方矩阵A=(aij) nn，其中 在图与网络分析的应用中，将面临一个问题——如何分析、计算一个较大型的网络，这当然需借助快速的计算工具——计算机。那么，如何将一个图表示在计算机中。

11 图的基本概念与模型 例6.2 下图所表示的图可以构造邻接矩阵A如下 v5 v1 v2 v3 v4 v6 4 3 2 5 6 7

12 图的基本概念与模型 2. 关联矩阵 对于图G=(V,E), | V |=n, | E |=m, 有mn阶矩阵M=(mij) mn，其中:
3. 权矩阵 对于赋权图G=(V,E), 其中边 有权 , 构造矩阵B=(bij) nn 其中：

13 图的基本概念与模型 例6.3 下图所表示的图可以构造邻接矩阵M如下: M=（mij）= v1 v2 v3 v5 v8 v7 e1 e2 e3
e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1 v2 v3 v4 v5 v6 v7 v8 M=（mij）=

14 图的基本概念与模型 例6.4 下图所表示的图可以构造权矩阵B如下: v5 v1 v2 v3 v4 v6 4 3 2 5 6 7

15 树与图的最小树 树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。
例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。 A B C D E F G H 运动员

16 树与图的最小树 例6.3 某企业的组织机构图也可用树图表示。

17 树与图的最小树 v2 树：无圈的连通图即为树 v1 性质1：任何树中必存在次为1的点。 v6 性质2：n 个顶点的树必有n-1 条边。 v3
性质3：树中任意两个顶点之间，恰有且仅有一条链。 性质4：树连通，但去掉任一条边，必变为不连通。 性质5：树无回圈，但不相邻的两个点之间加一条边，恰 得到一个圈。

18 树与图的最小树 图的最小部分树(支撑树) 如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 G1 G2

19 树与图的最小树 a b c f e d h g b f e d

20 树与图的最小树 a b c f e d h g b f d g

21 树与图的最小树 a b c f e d h g b c e d

22 树与图的最小树 a b c f e d h g a b c h

23 树与图的最小树 a b c f e d h g a f d g

24 树与图的最小树 求树的方法：破圈法和避圈法 破圈法

25 树与图的最小树 部分树

26 树与图的最小树 v1 v3 v1 v2 v3 v4 v5 v6 v1 v3 v2 v5 v1 v3 v2 v1 v3 v2 v5 v6 v1
避圈法 v1 v3 v1 v2 v3 v4 v5 v6 v1 v3 v2 v5 v1 v3 v2 v1 v3 v2 v5 v6 v1 v3 v2 v5 v6 v4

27 破圈法：任取一圈，去掉圈中最长边，直到无圈。
树与图的最小树 赋权图中求最小树的方法：破圈法和避圈法 破圈法：任取一圈，去掉圈中最长边，直到无圈。 5 v1 v2 v3 v4 v5 v6 8 4 3 7 2 6 1 v3 v5 v1 5 4 1 2 边数＝n-1=5 v2 3 v4 v6

28 树与图的最小树 得到最小树： v1 v2 v3 v4 v5 v6 4 3 5 2 1 Min C(T)=15

29 树与图的最小树 避圈法: 去掉G中所有边，得到n个孤立点；然后加边。
5 v1 v2 v3 v4 v5 v6 8 4 3 7 2 6 1

30 树与图的最小树 5 v1 v2 v3 v4 v5 v6 8 4 3 7 2 6 1 v1 v3 v5 5 4 1 2 v2 3 v4 v6 Min C(T)=15

31 树与图的最小树 练习：应用破圈法求最小树 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23
36

32 树与图的最小树 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36

33 树与图的最小树 v1 v2 20 1 15 23 4 v7 9 v6 v3 25 28 16 3 v5 17 v4

34 树与图的最小树 v1 20 v2 1 15 23 4 v7 9 v6 v3 25 28 16 3 v5 17 v4

35 树与图的最小树 v1 v2 1 15 23 4 v7 9 v6 v3 25 28 16 3 v5 17 v4

36 树与图的最小树 v1 v2 1 15 23 4 v7 9 v6 v3 25 28 16 3 v5 17 v4

37 树与图的最小树 v1 v2 23 1 4 v7 9 v6 v3 25 28 16 3 v5 17 v4

38 树与图的最小树 v1 v2 23 1 4 v7 9 v6 v3 25 28 16 3 v5 17 v4

39 树与图的最小树 v1 v2 23 1 4 v7 9 v6 v3 25 28 3 v5 17 v4

40 树与图的最小树 v1 v2 23 1 4 v7 9 v6 v3 25 28 3 v5 17 v4

41 树与图的最小树 v1 v2 23 1 4 v7 9 v6 v3 28 3 v5 17 v4

42 树与图的最小树 v1 v2 23 1 4 v7 9 v6 v3 28 3 v5 17 v4

43 树与图的最小树 v2 v1 1 23 4 v7 v6 9 v3 3 v5 17 v4 min= =57

44 树与图的最小树 练习：应用避圈法求最小树 v1 20 v2 23 1 4 15 v7 v6 36 9 v3 28 25 16 3 v5 v4
17

45 树与图的最小树 v1 20 v2 23 1 4 15 v7 v6 36 9 v3 28 25 16 3 v5 v4 17

46 树与图的最小树 v1 20 v2 23 1 4 15 v7 v6 36 9 v3 28 25 16 3 v5 v4 17

47 树与图的最小树 v1 20 v2 23 1 4 15 v7 v6 36 9 v3 28 25 16 3 v5 v4 17

48 树与图的最小树 v1 20 v2 23 1 4 15 v7 v6 36 9 v3 28 25 16 3 v5 v4 17

49 树与图的最小树 v1 20 v2 23 1 4 15 v7 v6 36 9 v3 28 25 16 3 v5 v4 17

50 树与图的最小树 v1 20 v2 23 1 4 15 v7 36 9 v6 v3 28 25 16 3 v5 v4 17 min= =57

51 树与图的最小树 课堂练习： 3 7 4 9 6 2 1 2 5 4 1 7 3 答案： Min C(T)=12 Min C(T)=15

52 树与图的最小树 4 1 2 2 Min C(T)=12 2 3 2 2 3 4 3 2 1 3 6 8 5 4 7 Min C(T)=18

53 最短路问题 求最短路的算法: 狄克斯屈拉(Dijkstra)标号算法

54 最短路问题 狄克斯屈拉(Dijkstra)标号算法的基本思路：
若序列{ vs,v1…..vn-1,vn }是从vs到vt间的最短路，则序列{ vs,v1…..vn-1 } 必为从vs 到vn-1的最短路。 假定v1→v2 →v3 →v4是v1 →v4的最短路，则v1 →v2 →v3一定是v1 →v3的最短路，v2 →v3 →v4也一定是v2 →v4的最短路。 v1 v2 v3 v4 v5

55 最短路问题 求网络图的最短路，设图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为 (i, j) 距离为dij
P标号(点标号)：b(j) —起点vs到点vj的最短路长； T标号(边标号)： k(i,j)=b(i)+dij， 步骤： 1. 令起点的标号；b(s)＝0。 2. 找出所有已标号的vi到未标号的vj的弧集合 B={(i, j)} 如果这样的弧不存在或vt已标号则计算结束； 3. 计算集合B中弧k(i，j)=b(i)+dij的标号 4. 选一个点标号 在终点vi处标号b(i), 返回到第2步。

56 最短路问题 例6.5 求下图v1到v7的最短路长及最短路线 7 12 ① ② ③ ④ ⑤ ⑥ ⑦ 8 6 2 5 3 4 10 7 8 10
T标号 7 12 ① ② ③ ④ ⑤ ⑥ ⑦ 8 6 2 5 3 4 10 7 P标号 8 10 6 5 7 14 11 5 2 11 4 2 4 v7已标号，计算结束。从v1到v7的最短路长是 11, 最短路线： v1→ v4 → v6 → v7

57 注：无向图最短路的求法只将上述步骤2将弧改成边即可。
最短路问题 从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj 。 注：无向图最短路的求法只将上述步骤2将弧改成边即可。

58 最短路问题 例6.6 求下图v1到各点的最短距离及最短路线。 4 6 8 18 6
11 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 4 5 2 6 1 7 8 3 9 12 16 18 18 4 9 6 8 3 8 5 12 24 18 6 12 3 2 24 10 2 6 所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。

59 最短路问题 课堂练习： 1. 用Dijkstra算法求下图从v1到v6的最短距离及路线。 v1到v6的最短路为： v1 v2 v4 v6 3
5 2 4 1 v3 4 v5 v1到v6的最短路为：

60 最短路问题 2. 求从v1到v8的最短路径 2 3 7 1 8 4 5 6 10 9

61 v1到v8的最短路径为v1→v4→v7→v5→v8，最短距离为10
最短路问题 2 3 7 1 8 4 5 6 10 9 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 p8=10 v1到v8的最短路径为v1→v4→v7→v5→v8，最短距离为10

62 最短路问题 3. 求下图中v1点到另外任意一点的最短路径 v2 1 7 v6 v1 3 3 3 6 2 v4 2 v5 v3 2

63 最短路问题 1 7 V2 1 7 V6 v1 3 3 3 6 2 V4 4 2 V5 2 V3 4 2

64 最短路问题 1 7 V2 1 7 V6 v1 3 3 3 6 2 V4 4 2 V5 4 2 V3 2

65 最短路问题 最短路问题的应用： 例6.7 电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。 v7 (乙地) 17 v2 5 6 6 v4 15 v1 （甲地） 3 4 2 v6 4 10 v5 v3

66 最短路问题 解：这是一个求无向图的最短路的问题。

67 网络的最大流 如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。

68 网络的最大流 基本概念： 1. 容量网络：对网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。 4 ① ③ 7 4 1 s 4 t 6 8 2 9 ② ④ 2

69 网络的最大流 2. 网络的最大流 是指网络中从发点到收点之间允许通过的最大流量。 3. 流与可行流
流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。 满足以下条件的一组流称为可行流。 容量限制条件。容量网络上所有的弧满足：0≤fij≤cij 中间点平衡条件。 若以v(f)表示网络中从s→t的流量，则有：

70 网络的最大流 结论：任何网络上一定存在可行流。（零流即是可行流） 网络最大流问题：
指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。

71 网络的最大流 割与割集 割是指容量网络中的发点和收点分割开，并使s→t的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用 表示。 如下图中，AA′将网络上的点分割成 两个集合。并有 ，称弧的集合{(v1,v3),(v2,v4)}是一个割，且 的流量为18。

72 网络的最大流 t s A’ v1 9(5) v3 B’ 5(5) 8(8) 2(0) 5(3) 6(0) 7(6) 10(9) v2 v4
● 5(5) 8(8) 2(0) 5(3) 6(0) t s 7(6) 10(9) v2 v4 9(9) A B

73 网络的最大流 定理1 设网络N中一个从 s 到 t 的流 f 的流量为v(f )， (V, V´)为任意一个割集，则
v(f ) = f(V, V´)  f(V´, V) 推论1 对网络 N中任意流量v(f )和割集 (V, V´)，有 v(f )  c(V, V´) [证明] w= f(V, V´)  f(V´, V)  f(V, V´)  c(V, V´) 推论2 最大流量v＊ (f )不大于最小割集的容量，即： v＊ (f )  min{c(V, V´)} 定理2 在网络中s→t的最大流量等于它的最小割集的容量， 即： v＊ (f ) = c ＊(V, V´)

74 网络的最大流 增广链 在网络的发点和收点之间能找到一条链，在该链上所有指向为s→t的弧，称为前向弧，记作μ+,存在f<c；所有指向为t→s的弧，称为后向弧，记做μ－，若f>0，则称这样的链为增广链。例如下图中，s→v2→v1→v3→v4→t。 定理3 网络N中的流 f 是最大流当且仅当N中不包含任何增广链

75 网络的最大流 v1 9(4) v3 5(5) 8(8) 2(0) 5(4) 6(1) t s ● 7(5) 10(8) v2 v4 9(9)

76 网络的最大流 求网络最大流的标号算法： [基本思想] 由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。
[基本方法] 找出第一个可行流，（例如所有弧的流量fij =0。） 用标号的方法找一条增广链 首先给发点s标号(∞),标号中的数字表示允许的最大调整量。 选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：

77 网络的最大流 如果弧的起点为vi，并且有fij<Cij，则给vj标号为(Cij－fij)
如果弧的方向指向vi，并且有fji>0，则vj标号(fji) (3) 重复第(2)步，可能出现两种结局： 标号过程中断，t无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V′,(V,V′)为网络的最小割。 t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步

78 网络的最大流 (4) 修改流量。设原图可行流为f，令 得到网络上一个新的可行流f’。
(5) 擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。

79 网络的最大流 t s 例6.10 用标号算法求下图中s→t的最大流量，并找出最小割。 v1 9(3) v3 5(4) 8(7) 2(0)
● 5(4) 8(7) 2(0) 5(4) 6(1) t s 7(5) 10(8) v2 v4 9(9)

80 网络的最大流 t s 解：(1) 先给s标号(∞) v1 9(3) v3 5(4) 8(7) 2(0) 5(4) 6(1) 7(5)
● 5(4) 8(7) 2(0) (∞) 5(4) 6(1) t s 7(5) 10(8) v2 v4 9(9)

81 网络的最大流 t s (2) 检查与s点相邻的未标号的点，因fs1<cs1，故对v1标号=min{∞, cs1-fs1}=1, v1
(1) v1 9(3) v3 ● 5(4) 8(7) 2(0) (∞) 5(4) 6(1) t s 7(5) 10(8) v2 v4 9(9)

82 网络的最大流 (2) 检查与v1点相邻的未标号的点，因f13<c13，故对v3标号=min{1, c13-f13}= min{1, 6}= 1 (1) (1) v1 9(3) v3 ● 5(4) 8(7) 2(0) (∞) 5(4) 6(1) t s 7(6) 10(8) v2 v4 9(9)

83 网络的最大流 (3) 检查与v3点相邻的未标号的点，因f3t<c3t，故对vt标号=min{1, c3t-f3t}= min{1, 1}= 1 找到一条增广链s→v1→v3→t (1) (1) v1 9(3) v3 ● 5(4) 8(7) 2(0) (1) (∞) 5(4) 6(1) t s 7(5) 10(8) v2 v4 9(9)

84 网络的最大流 t s (4) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 v1 9(3) v3 5(4) 8(7) 2(0)
(1) (1) v1 9(3) v3 ● 5(4) 8(7) 2(0) (1) (∞) 5(3) 6(1) t s 7(5) 10(8) v2 v4 9(9)

85 网络的最大流 t s (5) 擦除所有标号，重复上述标号过程，寻找另外的增广链。 v1 9(4) v3 5(5) 8(8) 2(0)
(1) (1) v1 9(4) v3 ● 5(5) 8(8) 2(0) (1) (∞) 5(3) 6(0) t s 7(5) 10(8) v2 v4 9(9)

86 网络的最大流 t s (5) 擦除所有标号，重复上述标号过程，寻找另外的增广链。 ε(1)=min{2,3}=2
(2) (2) ε(1)=min{2,3}=2 ε(3)=min{2,5}=2 v1 9(4) v3 ● 5(5) 8(8) 2(0) (1) (∞) 5(3) 6(1) t s ε(t)=min{1,2}=1 7(5) 10(8) v2 9(9) v4 ε(2)=min{∞,2}=2 ε(4)=min{2,1}=1 (2) (1)

87 网络的最大流 t s (6) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 v1 9(4) v3 5(5) 8(8) 2(0)
(2) (2) v1 9(4) v3 ● 5(5) 8(8) 2(0) (1) (∞) 5(3) 6(1) t s 7(5) 10(8) v2 9(9) v4 (2) (1)

88 网络的最大流 t s (7) 擦除所有标号，重复上述标号过程，寻找另外的增广链。 v1 9(5) v3 5(5) 8(8) 2(0)
(2) (2) v1 9(5) v3 ● 5(5) 8(8) 2(0) (1) (∞) 5(2) 6(0) t s 7(6) 10(9) v2 9(9) v4 (2) (1)

89 网络的最大流 t s (7) 擦除所有标号，重复上述标号过程，寻找另外的增广链。 ε(1)=min{1,2}=1
v1 9(5) v3 ● 5(5) 8(8) 2(0) (∞) 5(2) 6(0) t s 7(6) 10(9) v2 9(9) v4 ε(2)=min{∞,1}=1 (1)

90 网络的最大流 s t 例6.9 求下图s→t的最大流，并找出最小割 1(1) v1 v4 7(6) 4(3) 3(2) v5 2(2)
10(4) 1(1) 5(3) 4(2) 2(2) 7(6) 8(3) ●

91 网络的最大流 s t 解: (1) 在已知可行流的基础上，通过标号寻找增广链。 1(1) v1 v4 ε(t)=min{2,5}=2
4(3) 3(2) 10(4) 1(1) 5(3) 4(2) 2(2) 7(6) 8(3) ● ε(t)=min{2,5}=2 (∞) (2) ε(3)=min{6,2}=2 (6) (2) ε(2)=min{∞,6}=6 存在增广链s→v2→v3→ t

92 网络的最大流 s t (2) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 1(1) v1 v4 7(6) 4(3) 3(2)
(2) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(4) 1(1) 5(3) 4(2) 2(2) 7(6) 8(3) ● (∞) (2) (6) (2)

93 网络的最大流 s t (3) 擦除原标号，重新搜寻增广链。 1(1) v1 v4 7(6) 4(3) 3(2) v5 2(2) 5(3)
10(6) 1(1) 5(3) 4(4) 2(2) 7(6) 8(5) ● (∞) (2) (6) (2)

94 网络的最大流 s t (4) 重新搜寻增广链。 存在增广链：s→v2→v5→v3→ t v1 v2 v3 v4 v5 4(3) 3(2)
10(6) 1(1) 5(3) 4(4) 2(2) 7(6) 8(5) ● (1) (1) (∞) ε(5)=min{4,1}=1 ε(t)=min{1,3}=1 (4) (1) ε(2)=min{∞,4}=4 ε(3)=min{1,2}=1

95 网络的最大流 s t (5) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 1(1) v1 v4 7(6) 4(3) 3(2)
(5) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(6) 1(1) 5(3) 4(4) 2(2) 7(6) 8(5) ● (1) (1) (∞) (1) (4)

96 网络的最大流 s t (6) 擦除原标号 1(1) v1 v4 7(6) 4(3) 3(2) v5 2(2) 3(3) 5(4) 10(7)
(6) 擦除原标号 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(7) 1(1) 3(3) 5(4) 4(4) 2(2) 7(6) 8(6) ● (1) (1) (∞) (4) (1)

97 网络的最大流 s t (7) 重新搜寻增广链。 存在增广链：s→v5→v3→ t 1(1) v1 v4 7(6) 4(3) 3(2) v5
10(7) 1(1) 3(3) 5(4) 4(4) 2(2) 7(6) 8(6) ● (1) (1) (∞) ε(5)=min{∞,1}=1 ε(5)=min{1,2}=1 (1) ε(5)=min{1,1}=1

98 网络的最大流 s t (8) 调整增广链上的流量，非增广链流量不变，得到新的可行流 1(1) v1 v4 7(6) 4(3) 3(2) v5
10(7) 1(1) 3(3) 5(4) 4(4) 2(2) 7(6) 8(6) ● (1) (1) (∞) (1)

99 网络的最大流 s t (9) 擦除原标号 v1 v2 v3 v4 v5 4(3) 3(3) 10(7) 3(2) 1(1) 5(5)
(9) 擦除原标号 s t v1 v2 v3 v4 v5 4(3) 3(3) 10(7) 3(2) 1(1) 5(5) 4(4) 2(2) 7(6) 8(7) ● (1) (1) (∞) (1)

100 网络的最大流 s t (10) 重新标号，搜索增广链 存在增广链：s→v1→v5→v4→t v1 v2 v3 v4 v5 4(3) 3(3)
(10) 重新标号，搜索增广链 存在增广链：s→v1→v5→v4→t (1) (1) s t v1 v2 v3 v4 v5 4(3) 3(3) 10(7) 3(2) 1(1) 5(5) 4(4) 2(2) 7(6) 8(7) ● ε(4)=min{1,1}=1 ε(1)=min{∞,1}=1 (1) (∞) (1) ε(5)=min{1,1}=1 ε(t)=min{1,1}=1

101 网络的最大流 s t (11) 调整增广链上的流量，非增广链流量不变，得到新的可行流 v1 v2 v3 v4 v5 4(3) 3(3)
(1) (1) s t v1 v2 v3 v4 v5 4(3) 3(3) 10(7) 3(2) 1(1) 5(5) 4(4) 2(2) 7(6) 8(7) ● (1) (∞) (1)

102 网络的最大流 s t (11) 擦除标号，在新的可行流上重新标号。 1(1) v1 v4 7(7) 4(4) 3(3) v5 2(2)
10(7) 1(1) 5(5) 2(2) 7(7) 8(7) ● (1) (∞) (1)

103 网络的最大流 s t (11) 擦除标号，在新的可行流上重新标号。 1(1) v1 v4 7(7) 4(4) 3(3) v5 2(2)
10(7) 1(1) 5(5) 2(2) 7(7) 8(7) ● (∞) ε(1)=min{∞,3}=1 (3) 无法标号，不存在增广链，此可行流已为最大流。最大流量为14。