1、图论的产生：图论的产生：1736年的年的“哥尼斯堡七桥哥尼斯堡七桥问题问题”十八世纪的东普鲁士哥尼斯堡城十八世纪的东普鲁士哥尼斯堡城哥尼斯堡七桥问题的网络分析哥尼斯堡七桥问题的网络分析一、图与网络的基本概念一、图与网络的基本概念由一些点及一些点的连线所组成的图形。若由一些点及一些点的连线所组成的图形。若V=V1,V2, Vn是空间是空间n个点个点的集合的集合; E= e1,e2, em是空间是空间m个边的集合个边的集合,满足满足: 1)V非空非空 2)E中每一条线中每一条线ei是以是以V中两个点中两个点Vs,Vt为端点为端点 3)E中任意两条线之间除端点之外无公共点中任意两条线之间除端点之外无
2、公共点.则由则由V、E构成的二元组合构成的二元组合G=(V， E)就是图。就是图。已知图已知图G1（V1，E1）若）若V1 V， E1 E ; 则称图则称图G1（V1，E1）是）是图图G=(V， E)的子图的子图若在图若在图G中，某个边的两个端点相同，则称中，某个边的两个端点相同，则称e是是。图中某两点之间有多余一条的边，称之为多重边。图中某两点之间有多余一条的边，称之为多重边。含有多重边的图。含有多重边的图。无环、无多重边的图。无环、无多重边的图。 无向图：无向图：G（V，E）点集）点集+边集边集 弧：弧：点与点之间有方向的边，叫做弧。弧集：点与点之间有方向的边，叫做弧。弧集：A=a1,a1
3、,am 有向图：有向图：由点及弧所构成的图，记为由点及弧所构成的图，记为D=(V,A)，V,A分别是分别是D的点集合和弧集合。的点集合和弧集合。 环：环：某一条孤起点某一条孤起点=终点，称为环。终点，称为环。 基础图：基础图：给定一个有向图给定一个有向图D=(V,A) ，从，从D中去掉所有弧上的箭头，所得到的无中去掉所有弧上的箭头，所得到的无向图。记之为向图。记之为G(D)。 链：链：设设(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是是D中的一个点弧交错序列，如果这个序中的一个点弧交错序列，如果这个序列在基础图列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错
4、序列是中所对应的点边序列是一条链，则称这个点弧交错序列是D的的一条一条链链。 路：路：如果如果(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是是D中的一条链，并且对中的一条链，并且对t=1,2,k-1，均有均有ait=(vit,vit+1)，称之为从，称之为从vi1到到vik的一条的一条路路。 回路：回路：若路的第一个点和最后一点相同，则称之为回路。若路的第一个点和最后一点相同，则称之为回路。 次：次：图中的点图中的点V，以，以V为端点的边的个数，称为为端点的边的个数，称为V的次，的次，记为记为d(V)。 定理定理1：图：图G=(V,E)中，所有点的次之和是边数的两倍，中，
5、所有点的次之和是边数的两倍，即设边数为即设边数为q ，则，则d(vi)=2q ，其中，其中vi V 奇点：奇点：次为奇数的点。否则称为偶点。次为奇数的点。否则称为偶点。 任一图中，奇点的个数为偶数。任一图中，奇点的个数为偶数。 一笔划：一笔划：可以一笔划：没有或仅有两个奇次点的图形可以一笔划：没有或仅有两个奇次点的图形 如没有奇次点：任取一点，它既是起点又是终点。如没有奇次点：任取一点，它既是起点又是终点。 两个奇次点：分别选为起点和终点。两个奇次点：分别选为起点和终点。1、链：链：给定一个图给定一个图G=(V,E)，一个点边的交错序列，一个点边的交错序列(vi1, ei1, vi2, ei2
6、,vik-1,eik-1,vik)，如果满足，如果满足eit=vit,vit+1 (t=1,2,k-1)，则称为一条联结，则称为一条联结vi1和和vik的的链链，称点，称点vi2, vi3,vik-1为链的中间点。为链的中间点。2、圈：圈：链链(vi1,vi2,vik)中，若中，若vi1=vik,，则称之为一个，则称之为一个圈圈。3、简单链：简单链：若链若链(vi1,vi2,vik)中，点中，点vi1,vi2,vik都是不同都是不同的，则称之为的，则称之为简单链。简单链。4、连通图：连通图：图图G中，若任何两个点之间，至少有一条链。否中，若任何两个点之间，至少有一条链。否则为不连通图。则为不连
7、通图。 1、赋权图：赋权图：给图给图G=(V,E) ，对，对G中的每一条边中的每一条边vi,vj，相应地有一个数，相应地有一个数wij，则称这样的图则称这样的图G为赋权图，为赋权图，wij称为边称为边vi,vj上的权。上的权。2、网络（赋权图）、网络（赋权图）G=（V，E），其边（），其边（vi,vj）有权）有权wij, 构造矩阵构造矩阵A=（aij）nn,其中：其中： aij= wij（vi,vj）E 0 其他其他称矩阵称矩阵A为网络为网络G的的权矩阵权矩阵。如。如P239，例，例23、对于图、对于图G=（V，E），）， V =n,构造一个矩阵构造一个矩阵A=（aij）nn,其中：其中： a
8、ij= 1（vi,vj）E 0 其他其他称矩阵称矩阵A为图为图G的的邻接矩阵邻接矩阵。如。如P239，例，例31、欧拉回路与道路：欧拉回路与道路：连通图连通图G中，若存在一条道路，经过每边一次中，若存在一条道路，经过每边一次且仅一次，则称这条路为且仅一次，则称这条路为欧拉道路欧拉道路。若存在一条回路，经过每边。若存在一条回路，经过每边一次且仅一次，则称这条回路为一次且仅一次，则称这条回路为欧拉回路，具有欧拉回路的图也欧拉回路，具有欧拉回路的图也称欧拉图称欧拉图。仅当无向连通图仅当无向连通图G中无奇点时是欧拉图，仅当恰有两个奇点时为欧拉中无奇点时是欧拉图，仅当恰有两个奇点时为欧拉道路；道路；仅当
9、有向连通图仅当有向连通图G中每个顶点的出次等于入次时是欧拉图，仅当两个中每个顶点的出次等于入次时是欧拉图，仅当两个顶点外，其余每一个顶点的出次等于入次，且这两个顶点中，一顶点外，其余每一个顶点的出次等于入次，且这两个顶点中，一个顶点出次多个顶点出次多1，另一个顶点入次多，另一个顶点入次多1时为欧拉道路；时为欧拉道路；2、中国邮路问题：中国邮路问题：给定一个连通图给定一个连通图G，每边有非负权，每边有非负权l(e)，要求一，要求一条回路过每边至少一次，且满足总权最小。条回路过每边至少一次，且满足总权最小。例如：比赛中的相遇情况、组织结构图、家庭树例如：比赛中的相遇情况、组织结构图、家庭树1、定义
10、、定义：一个无圈的连通图称为树。：一个无圈的连通图称为树。2、树的性质、树的性质：1）图）图G是树的充分必要条件是任意两是树的充分必要条件是任意两个顶点之间有且只有一条链。个顶点之间有且只有一条链。2）在树中去掉任意一条边则构成一个）在树中去掉任意一条边则构成一个不连通图，不再是树；在树中不相邻的不连通图，不再是树；在树中不相邻的两点之间添加一条边，恰好形成了一个两点之间添加一条边，恰好形成了一个圈，也就不再是树。圈，也就不再是树。3）树中顶点的个数为）树中顶点的个数为P，则其边数必，则其边数必为为P-1。3、生成树、生成树：设图：设图T=(V,E) 是图是图G（V，E）的子图，如果图）的子图
11、，如果图T=(V, E) 是一个树，则称是一个树，则称T是是G的一个支撑树。的一个支撑树。4、寻找生成树、寻找生成树的方法的方法1）破圈法：在图中任取一个圈，从圈中去掉任一边，对余下的图重复）破圈法：在图中任取一个圈，从圈中去掉任一边，对余下的图重复上述操作，即可得到一个支撑树。上述操作，即可得到一个支撑树。2）避圈法：每一步选取与已选的边构不成圈的边，直到不能继续为止。）避圈法：每一步选取与已选的边构不成圈的边，直到不能继续为止。（深探法广探法（深探法广探法阅读内容阅读内容）5、最小生成树、最小生成树1）最小支撑树：如果）最小支撑树：如果T=(V,E) 是是G的一个支撑树，称的一个支撑树，称
12、E中所有边的权中所有边的权之和为支撑树之和为支撑树T的权，记为的权，记为w(T)，即，即 w(T)=wij (vi,vj)T如果支撑树如果支撑树T*的权的权w(T*)是是G的所有支撑树的权中最小者，则称的所有支撑树的权中最小者，则称T*是是G的的最小生成树（最小支撑树，简称最小树）最小生成树（最小支撑树，简称最小树） w(T*)=min w(T)2）求最小树求最小树的方法：的方法：方法一方法一(避圈法避圈法) 开始选一条最小权的边，以后每一步中，总从未被开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。选取的边中选一条权最小的边，并使之与已选取
13、的边不构成圈。方法二方法二(破圈法破圈法) 任取一个圈，从圈中去掉一条权最大的边。在余下任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。最小树。 例例 用破圈法求下图的最小树用破圈法求下图的最小树122223122223334456、根树及其应用、根树及其应用定义定义17：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。为有向树。定义定义18：有向树：有向树T，恰有一个结点入次为，恰有一个结点入次为0
14、，其余各点入次均为，其余各点入次均为1，称树，称树T为根树（又称外向树）。为根树（又称外向树）。定义定义19：在根树中，若每个顶点的出次小于或等于：在根树中，若每个顶点的出次小于或等于m，称这颗树为，称这颗树为m叉叉树，若每个顶点的出次恰好等于树，若每个顶点的出次恰好等于m或或0，则称这颗树为完全，则称这颗树为完全m叉树。当叉树。当m=2时，称为二叉树、完全二叉树。满足总权最小的二叉树称为最优时，称为二叉树、完全二叉树。满足总权最小的二叉树称为最优二叉树（又称霍夫曼树）。二叉树（又称霍夫曼树）。最优二叉树求解步骤：最优二叉树求解步骤：（1）将）将s个叶子按权由小到大排序，不失一般性，设个叶子按
15、权由小到大排序，不失一般性，设p1p2ps（2）将两个具有最小权的叶子合并成一个分枝点，其权为）将两个具有最小权的叶子合并成一个分枝点，其权为p1+p2，将新，将新的分枝点作为一个叶子，令的分枝点作为一个叶子，令s=s-1，若，若s=1停止，否则转（停止，否则转（1）习题： P8.7 P8.8 P8.98.3 最短路问题最短路问题如下图中如下图中V1：油田，：油田，V9：原油加工厂：原油加工厂求使从求使从V1到到V9总铺路设管道最短方案。总铺路设管道最短方案。 V1V4V2V3V6V9V8V7V542466234442用图论来解释最短路问用图论来解释最短路问题：在一个赋权有向图题：在一个赋权有
16、向图D（V，A，w）中，其）中，其中始点中始点V1，终点，终点Vt，求，求从从V1到到Vt的一条路，使的一条路，使其为其为V1到到Vt的所有路中的所有路中总权值最小的路。总权值最小的路。1、情况一：、情况一： wij0(Dijkstra算法算法)原理：原理：Bellman最优性定理最优性定理方法：图上作业法（标号法）；双标号法（表的形式）方法：图上作业法（标号法）；双标号法（表的形式）标号：对于点标号：对于点V,若已求出若已求出V1到到Vi的最短值，标号（的最短值，标号（i,i) i ：表示：表示V1到到Vi的最短路值的最短路值 i:表示最短路中最后经过的点表示最短路中最后经过的点标号法步骤：
17、标号法步骤：1）给）给V1标号标号(0, Vs)2）把所有顶点分成两部分，）把所有顶点分成两部分，X：已标号的点；：已标号的点；X未标号的点未标号的点考虑与已标号点相邻的弧是存在这样的弧（考虑与已标号点相邻的弧是存在这样的弧（ Vi ，Vj ）, Vi X, Vj X若不存在，此问题无解，否则转若不存在，此问题无解，否则转3）3）选取未标号中所有入线的起点与未标号的点）选取未标号中所有入线的起点与未标号的点Vj进行计算进行计算:mini + wij= j并对其进行标号并对其进行标号(j, Vi)，重复，重复2）例9：（图831）步骤 v1v2v3v4v5v6v7v8最短路前向结点1002345
18、678*464v1*6986v1*988v2*913149v2*131413v5*141714v5*1515v7最短路长为15，路径可以逆向追踪，v8-v7-v5-v2-v1例2s5t6341074918815220230 0 8151012151131132s5t6341074918815220230 Dijkstra最短路算法的最短路算法的特点特点和和适应范围适应范围 一种隐阶段的动态规划方法一种隐阶段的动态规划方法 每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标
19、临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种记开始新一轮的临时标记，是一种深探法深探法 被框住的永久标记被框住的永久标记 Tj 表示表示 vs 到到 vj 的最短路，因此的最短路，因此 要求要求 dij 0，第，第 k 次迭代得到的永久标记，其最短路中最多有次迭代得到的永久标记，其最短路中最多有 k 条边，因此最多有条边，因此最多有n 1 次迭代次迭代 可以应用于可以应用于简单简单有向图和混合图，在临时标记时，所谓相邻必须是有向图和混合图，在临时标记时，所谓相邻必须是箭头指向的节点；若第箭头指向的节点；若第 n 1 次迭代后仍有节点的标记为次迭代后仍
20、有节点的标记为 ，则表明，则表明 vs 到该节点无有向路径到该节点无有向路径 如果只求如果只求 vs 到到 vt 的最短路，则当的最短路，则当 vt 得到永久标记算法就结束了；得到永久标记算法就结束了；但算法复杂度是一样的但算法复杂度是一样的 应用应用 Dijkstra 算法算法 n 1 次次 ，可以求所有点间的最短路，可以求所有点间的最短路 vs 到所有点的最短路也是一棵生成树，但不是最小生成树到所有点的最短路也是一棵生成树，但不是最小生成树设从设从V1到到Vj(j=1,2,t)的最短路长为的最短路长为P1jV1到到Vj无任何中间点无任何中间点 P1j（1）= wijV1到到Vj中间最多经过
21、一个点中间最多经过一个点 P1j（2）= min P1i（1）+wijV1到到Vj中间最多经过两个点中间最多经过两个点 P1j（3）= min P1i（2）+wij.V1到到Vj中间最多经过中间最多经过t-2个点个点 P1j（t-1）= min P1i（t-2）+wij终止原则：终止原则：1）当）当P1j（k）= P1j（k+1）可停止，最短路可停止，最短路P1j*= P1j（k）2）当）当P1j（t-1）P1j（t-2）时，再多迭代一次时，再多迭代一次P1j（t） ，若，若P1j（t） = P1j（t-1） ，则，则原问题无解，存在负回路。原问题无解，存在负回路。V1V2V3V4V5V6V7
22、V8P1j(1)P1j(2)P1j(3)P1j(4)P1j(5)P1j(6)V1V2V3V4V5V6V7V80v1v4v2v3v5v6v7v825-34674-23-1-34225-30-2406400-3047203-10025-3020-3611020-36615020-3361410020-336910020-336910例：例：例例 设备更新问题设备更新问题制订一设备更新问题，使得总费用最小制订一设备更新问题，使得总费用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 购买费购买费 13 14 16 19 24 使用年数使用年数 0-1 1-2 2-3 3-4 4-5
23、维修费维修费 8 10 13 18 27 解解设以设以vi(i=1,2,3,4,5)表示表示“第第i年初购进一台新设备年初购进一台新设备”这这种状态，以种状态，以v6表示表示“第第5年末年末”这种状态；以弧这种状态；以弧(vi, vj)表示表示“第第i年初购置的一台设备一直使用到第年初购置的一台设备一直使用到第j年初年初”这一方案，以这一方案，以wij表表示这一方案所需购置费和维护费之和。示这一方案所需购置费和维护费之和。v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(21，V1)(31, V1)(44,V1)(62,V1)(78,V3)这样，
24、可建立本例的网络模型。于是，该问题就这样，可建立本例的网络模型。于是，该问题就可归结为从图中找出一条从可归结为从图中找出一条从v1到到v6的最短路问题。的最短路问题。用用Dijkstra标号法，求得最短路为标号法，求得最短路为 v1v3v6 即第一年初购置的设备使用到第三年初予以更新，即第一年初购置的设备使用到第三年初予以更新，然后一直使用到第五年末。这样五年的总费用最然后一直使用到第五年末。这样五年的总费用最少，为少，为78。习题 P8.10 P8.11 如下是一运输网络，弧上的数字表示每条弧如下是一运输网络，弧上的数字表示每条弧上的容量，问：该网络的最大流量是多少？上的容量，问：该网络的最
25、大流量是多少？vsv2v1v3v4vt432312234定义定义1：给定一个有向图：给定一个有向图D=(V,A),在在V中有一个发点中有一个发点vs和和一收点一收点vt，其余的点为中间点。对于每一条弧，其余的点为中间点。对于每一条弧(vi,vj),对应对应有一个有一个c(vi,vj) 0,(cij)称为弧的容量。这样的有向图称为称为弧的容量。这样的有向图称为网络。记为网络。记为D=(V,A,C)。网络的流：定义在弧集合网络的流：定义在弧集合A上的一个函数上的一个函数f=f(vi,vj)，称，称f(vi,vj)为弧为弧(vi,vj)上的流量，简记上的流量，简记fij 。问题：求一流问题：求一流f
26、ij满足满足1）0 fij cij v(f) i=s2） fij fji= 0 i s，t v(f) i=t3）且使）且使v(f)达到最大。达到最大。 给定可行流给定可行流f=fij，使，使fij=cij的弧称为的弧称为饱和弧饱和弧，使，使fij0的弧称为的弧称为非非零流弧零流弧。 若若 是网络中连接发点是网络中连接发点vs和收点和收点vt的一条链，定的一条链，定义链的方向是从义链的方向是从vs到到vt，则链上的弧被分成两类：，则链上的弧被分成两类：前向弧前向弧：弧的方向与链的方向一致：弧的方向与链的方向一致 全体全体 +后向弧后向弧：弧的方向与链的方向相反：弧的方向与链的方向相反 全体全体
27、-定义：设定义：设f是一可行流，是一可行流， 是从是从vs到到vt的一条链，的一条链，若若 满足下列条件，则称之为（关于流满足下列条件，则称之为（关于流f的）一条的）一条增广链增广链： 在弧在弧(vi,vj)+上，上，0 fijcij 在弧在弧(vi,vj)-上，上，0fij cij可结合下图理解其实际涵义。可结合下图理解其实际涵义。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,3) 定义定义4 给定网络给定网络D=(V,A,C)，若点集，若点集V被剖分为两个非空集合被剖分为两个非空集合V1和和V1，使，使vs V1， vt V1
28、，则把弧集，则把弧集(V1,V1)称为是分离称为是分离vs和和vt的的割集割集。割集是从割集是从vs到到vt的必经之路的必经之路。定义：给定一割集定义：给定一割集(V1,V1)，把割集，把割集(V1,V1)中所有弧的容量中所有弧的容量之和称为这个割集的容量之和称为这个割集的容量(割量割量),记为记为C(V1,V1)。v(f) C(V1,V1)vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,3) 若对于一可行流若对于一可行流f*，网络中有一割集，网络中有一割集(V1*,V1*)，使得，使得v(f*)= C(V1*,V1*)，则，则f必
29、是最大流，而必是最大流，而(V1*,V1*)，必定是，必定是容量最小的割集，即最小割集。容量最小的割集，即最小割集。 定理定理1 可行流可行流f*是最大流的充要条件是不存在关于是最大流的充要条件是不存在关于f*的增广链。的增广链。 若若f*是最大流，则网络中必存在一个割集是最大流，则网络中必存在一个割集(V1*,V1*)，使得使得 v(f*)= C(V1*,V1*) 定理定理 任一网络任一网络D中，中，从从vs到到vt的最大流的流量等于的最大流的流量等于分离分离vs，vt的最小割集的割量。的最小割集的割量。XXXX234112243割集为(1,3)(2,3)(2,4)割集的容量92341122
30、43割集为(1,2)(1,3)割集的容量5XXXX234112243割集为(1,2)(3,4)割集的容量3234112243割集为(2,4)(3,4)割集的容量5网络最大流的流量等于网络最小割集的容量网络最大流的流量等于网络最小割集的容量步骤：步骤：1、选取一个可行流（可选择零流弧）、选取一个可行流（可选择零流弧）2、 标号过程标号过程从从Vs出发，在前向弧出发，在前向弧(vi,vj)上，若上，若fij0，则给，则给vj标号标号( Vi,l(vj)，其中，其中l(vj)=minl(vi)，fji。 思想：从一可行流出发，检查关于此流是否存在增广链。若存思想：从一可行流出发，检查关于此流是否存在
31、增广链。若存在增广链，则增大流在增广链，则增大流量，使此链变为非增广链；这时再检查是非还量，使此链变为非增广链；这时再检查是非还有增广链，若还有，继续调整，直至不存在增广链为止。有增广链，若还有，继续调整，直至不存在增广链为止。 3、若标号延续到、若标号延续到vt，表明得到一条从，表明得到一条从vs到到vt的增的增广链广链 ，转入调整阶段，转入调整阶段4，否则当前流即为最大流。，否则当前流即为最大流。4、调整过程、调整过程令调整量为令调整量为 = l(vt)令令 fij+ (vi,vj)+ fij = fij (vi,vj) fij (vi,vj)去掉所有的标号，对新的可行流去掉所有的标号，对
32、新的可行流f =fij ，重新进，重新进入标号过程。入标号过程。v1vsvtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例例 求下列网络的最大流与最小截集。求下列网络的最大流与最小截集。解解一、标号过程一、标号过程 （2）检查）检查vs,在弧在弧(vs,v1)上上,fs1=7,cs1=9,fs1cs1,则则v1的标号为的标号为(vs,l(v1)，其中，其中(vs,2)l(v1)=minl(vs)，cs1fs1=min+ ，9 7=2(Vs, ) （1）线）线vs标号：标号：(VS, )（3）检查）检查v1,在弧在弧(v1,v4)上上,f
33、14=1,c14=3,f140，则则v3的标号为的标号为(-v4, l(v3)，其中，其中l(v3)=minl(v4)，f34=min2，1=1(-v4,1)（5）检查）检查v3,在弧在弧(v3,vt)上上,f3t=3,c3t=6,f3tc3t,v1vsvtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(vs,2)(v1,2)(-v4,1)则则vt的标号为的标号为(v3,l(vt)，其中，其中l(vt)=minl(v3)，c3tf3t=min1，6-3=1(v3,1)这样，我们得到了一增广链这样，我们得到了一增广链 ,如图所示。如图所示。
34、其中其中 +=(vs,v1),(v1,v4),(v3,vt)， -=(v3,v4)(v3,1)vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(Vs, )(vs,2)(v1,2)(-v4,1)二、调整过程二、调整过程取调整量为取调整量为 =1，在，在 上调整上调整f。在在 +上：上： fs1+ =7+1=8 f14+ =1+1=2 f3t+ =3+1=4在在 -上：上： f34 =11=0其余弧上的流量不变，这样得到一个新的流，如下图所示。其余弧上的流量不变，这样得到一个新的流，如下图所示。tv4v2(5,5)(Vs, ) 在上
35、图中重复上述标号过程，依次给在上图中重复上述标号过程，依次给vs,v2,v1,v4标号，标号，vvsv1vtv4v2v3(9,8)(5,3)(3,2)(4,4)(5,5)(3,2)(2,0)(6,4)(7,7)vv(4,4)v(f)=8+3=11 与此同时，可找到最小截集与此同时，可找到最小截集(V1,V1)，其中，其中V1为标号点集合，为标号点集合，V1为未标号点集合，弧集合为未标号点集合，弧集合(V1,V1) 即为最小截集。即为最小截集。此例中，此例中， V1=vs,v2,v1,v4, V1=v3,vt,(V1,V1)=(v1,v3)， (v4,vt)由于标号无法继续下去，算法结束。这时的
36、流为最大流，由于标号无法继续下去，算法结束。这时的流为最大流，最大流的流量为最大流的流量为(vs,1)(v1,1)(vs,2)最大流最小割集的标号法举例st134256(14,14)(9,9)(15,9)(16,15)(3,1)(12,10)(6,6)(4,3)(5,5)(22,22)(13,12)(7,5)(6,3)(19,10)st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)(s+, )(s+,6)(2 ,6)(3+,1)(4+,1)(s+, )(s+,5
37、)(2+,2)(5 ,2)(4+,2)最大流最小割集的标号法举例st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)st134256(14,14)(9,9)(15,12)(16,15)(3,1)(12,12)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,1)(19,13)(s+, )(s+,3)(2 ,3)最小截集最小截集最大匹配问题最大匹配问题 考虑工作分配问题，有考虑工作分配问题，有n n个工人，个工人，m m件工作，每个工人能力件
38、工作，每个工人能力不同，各能胜任其中的几项工作，假设每件工作只需一人不同，各能胜任其中的几项工作，假设每件工作只需一人做，每人只做一件工作，怎样分配才能使尽量多的工作有做，每人只做一件工作，怎样分配才能使尽量多的工作有人做，更多的人有工作做？人做，更多的人有工作做？ 用图的语言来描述：用图的语言来描述：x x1 1,x,x2 2,x,xn n表示工人，表示工人， y y1 1,y,y2 2,y,ym m表表示工作，边示工作，边(x(xi i, y, yj j) )表示表示x xi i胜任胜任 y yj j工作，这样就得到了二工作，这样就得到了二部图部图G=G=（X X，Y Y，E E），工作分
39、配问题就要在图），工作分配问题就要在图G G中找一个边中找一个边集集E E的子集，使得其中任何两条边没有公共端点，最好的的子集，使得其中任何两条边没有公共端点，最好的方案就是要使此边集的边数尽可能多，这就是方案就是要使此边集的边数尽可能多，这就是最大匹配最大匹配问题。问题。举例举例 某单位招收懂俄、英、日、德、法文的翻译各某单位招收懂俄、英、日、德、法文的翻译各一人，有一人，有5人应聘。已知乙懂俄文，甲、乙、人应聘。已知乙懂俄文，甲、乙、丙、丁懂日文，乙、戊懂德文，戊懂法文，问丙、丁懂日文，乙、戊懂德文，戊懂法文，问这这5个人是否都能得到聘书？最多几个得到招个人是否都能得到聘书？最多几个得到招
40、聘，招聘后每人从事哪一方面翻译任务？聘，招聘后每人从事哪一方面翻译任务？ 将五个人与五个外语语种分别用点表示，把各将五个人与五个外语语种分别用点表示，把各个人与懂得的外语语种之间用弧相连。规定每个人与懂得的外语语种之间用弧相连。规定每条弧的容量为条弧的容量为1，图网络的最大流量数字即为，图网络的最大流量数字即为最多能得到招聘的人数。最多能得到招聘的人数。 vs甲乙丙丁戊俄英日德法 vt 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1从图中看出只能有四个人得到招聘，方案为：从图中看出只能有四个人得到招聘，方案为：甲甲-英，乙英，乙-俄，丙俄，丙-日，戊日，戊-德，
41、丁未能得到应聘。德，丁未能得到应聘。 另注：多发点多收点的问题还有很多，如另注：多发点多收点的问题还有很多，如P271，8.15。 应用实例应用实例某工程公司在未来某工程公司在未来1-4月份内需完成三项工程：第一项工程工期月份内需完成三项工程：第一项工程工期为为1-3月份共三个月，总计需劳动力月份共三个月，总计需劳动力80人月，第二项工程工期为人月，第二项工程工期为4个月，总计需劳动力个月，总计需劳动力100人月，第三项工程工期为人月，第三项工程工期为3至至4月份共月份共两个月，总计需劳动力两个月，总计需劳动力120人月。该公司每月可用劳力为人月。该公司每月可用劳力为80人，人，但任一项工程上
42、投入的劳动力任一月内不准超过但任一项工程上投入的劳动力任一月内不准超过60人。问该工人。问该工程公司能否按期完成上述三项工程任务，应如何安排劳力，试将程公司能否按期完成上述三项工程任务，应如何安排劳力，试将此问题归结为求网络最大流问题。此问题归结为求网络最大流问题。以以M1，M2，M3，M4，分别代表，分别代表1至至4月，月，A，B，C为为3项工程，项工程，Ai,Bi,Ci为三项工程在为三项工程在i月内施工完成的部分，则可作出以下容量月内施工完成的部分，则可作出以下容量网络图，如在该图中能得到最大流量为网络图，如在该图中能得到最大流量为300，表明公司能按时完，表明公司能按时完成各项工程。成各
43、项工程。M1M2M3M4ABCST 80 80 80 80 60 60 60 60 60 60 60 60 60 80 100 120习题 P8.14 8.16一、引题：一、引题：求求Vs至至Vt的最大流（运输网络上）的最大流（运输网络上）,其中每条弧其中每条弧边上的数字表示弧容量和弧费用边上的数字表示弧容量和弧费用VsVt(10,4)(7,1)(8,1)(5,2)(2,6)(4,2)(10,3)VsVt(10,7)(7,7)(8,4)(5,0 )(2,0)(4,4)(10,4)VsVt(10,3)(7,7)(8,8)(5,4)(2,0)(4,4)(10,4)二、增广链的费用二、增广链的费用已
44、知网络已知网络G=（V，A， c，d），），f是是G上的上的一个可行流，一个可行流， 为从为从Vs至至Vt的可增广链，则的可增广链，则d( )=dij- dij,称为链称为链 的费用。的费用。若若 *是从是从Vs至至Vt的所有增广链中费用最小的链，的所有增广链中费用最小的链，则称为最小费用可增广链。则称为最小费用可增广链。 + -三、求解方法三、求解方法1、求网络关于费用的最短路（费用最小的增广链），、求网络关于费用的最短路（费用最小的增广链），若不存在，停止。若不存在，停止。2、在最短路上求调整量、在最短路上求调整量1=mincij-fij, (Vi,Vj) +2=minfij, (Vi,Vj) -=min1, 23 、调整：、调整：fij= fij+ (Vi,Vj) + fij= fij- (Vi,Vj) - fij= fij，其他，其他4、对于非零流弧添加反向弧，权值为负，对于饱和、对于非零流弧添加反向弧，权值为负，对于饱和弧，舍去其原弧，返回弧，舍去其原弧，返回1。习题 8.19
