《数学建模-图论ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模-图论ppt课件.ppt（97页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模数学建模 图论方法专题图论方法专题专题板块系列专题板块系列概率统计专题概率统计专题1优化专题优化专题2模糊方法及微分方程专题模糊方法及微分方程专题3图论方法专题图论方法专题4图论方法专题图论的基本概念图论的基本概念最短路与最小生成树最短路与最小生成树二部图的匹配二部图的匹配网络流网络流ABCD哥尼斯堡哥尼斯堡七桥示意图七桥示意图问题问题1:七桥问题七桥问题能否从任一陆地出发通过每座桥恰好一次而能否从任一陆地出发通过每座桥恰好一次而回到出发点？回到出发点？图论的基本概念图论的基本概念七桥七桥问题模拟图问题模拟图:ABDC欧拉指出：如果每块陆地所连接的桥都是偶数座，则欧拉指出：如果每块陆地
2、所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出从任一陆地出发，必能通过每座桥恰好一次而回到出发地。发地。图论的基本概念图论的基本概念问题问题2:哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）十二面体的十二面体的20个顶点代表世界上个顶点代表世界上20个城市，能个城市，能否从某个城市出发在十二面体上依次经过每个否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？图论的基本概念图论的基本概念问题问题3:四色问题四色问题 对任何一张地图进行着色，两个共同边界的对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色
3、就够了。国家染不同的颜色，则只需要四种颜色就够了。德德摩尔根致哈密顿的信（摩尔根致哈密顿的信（1852年年10月月23日）日）我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。图论的基本概念图论的基本概念问题问题4(4(关键路径问题关键路径问题):): 一项工程任务一项工程任务, ,大到建造一座大坝大到建造一座大坝, ,一座体育中心一座体育中心, ,小至组装一台机床小至组装一台机床, ,一架电视机一架电视机, , 都要包括许多工序都要包括
4、许多工序. .这这些工序相互约束些工序相互约束, ,只有在某些工序完成之后只有在某些工序完成之后, , 一个工序一个工序才能开始才能开始. . 即它们之间存在完成的先后次序关系即它们之间存在完成的先后次序关系, ,一般一般认为这些关系是预知的认为这些关系是预知的, , 而且也能够预计完成每个工序而且也能够预计完成每个工序所需要的时间所需要的时间. . 这时工程领导人员迫切希望了解最少需要多少时间这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目才能够完成整个工程项目, , 影响工程进度的要害工序是影响工程进度的要害工序是哪几个？哪几个？ 图论的基本概念图论的基本概念定义定义1
5、一个有序二元组一个有序二元组 (V, E ) 称为一个称为一个图图, 记为记为G = (V, E ), 其中其中 V或或V(G)称为称为G的的顶点集顶点集, V, 其元素称为其元素称为顶点顶点或或结点结点, 简称简称点点; E或或E(G)称为称为G的的边集边集, 其元素称为其元素称为边边, 它联结它联结V 中的中的两个点两个点, 如果这两个点是无序的如果这两个点是无序的, 则称该边为则称该边为无向边无向边, 否则否则, 称为称为有向边有向边. 的顶点数和边数。表示图或可以用GEV图论的基本概念图论的基本概念如果如果V = v1, v2, , vn是有限非空点集是有限非空点集, 则称则称G为为有
6、限图有限图或或n阶图阶图. 如果如果E的每一条边都是无向边的每一条边都是无向边, 则称则称G为为无向图无向图; 如果如果E的每一条边都是有向边的每一条边都是有向边, 则称则称G为为有向图有向图; 否则否则, 称称G为为混合图混合图. 记记E = e1, e2, , em(ek = vivj ). 图论的基本概念图论的基本概念对于一个图对于一个图G = (V, E ), 人们常用图形来表示它人们常用图形来表示它, 称其为称其为图解图解. 凡是有向边凡是有向边, 在图解上都用箭头标明其方向在图解上都用箭头标明其方向. 称点称点vi, vj为边为边vivj的的端点端点. 有边联结的两个点称为有边联结
7、的两个点称为相邻顶点相邻顶点, 有一个公共端点的边称为有一个公共端点的边称为相邻边相邻边. 边和它的端点称为边和它的端点称为互相关联互相关联.有向图中的关联又分有向图中的关联又分出关联出关联和和入关联入关联。 图论的基本概念图论的基本概念常用常用d (v)表示图表示图G中与顶点中与顶点v关联的边的数目关联的边的数目, d (v)称为顶点称为顶点v的的度数度数.与顶点与顶点v出出关联的边的数目称为关联的边的数目称为出度出度，记作，记作d +(v),与顶点与顶点v入入关联的边的数目称为关联的边的数目称为入度入度，记作，记作d -(v)。用用N (v)表示图表示图G中所有与顶点中所有与顶点v相邻的顶
8、点的集合相邻的顶点的集合. 图论的基本概念图论的基本概念任意两顶点都相临的简单图称为任意两顶点都相临的简单图称为完全图完全图.有有n个顶点的完全图记为个顶点的完全图记为K n。几个基本定理：几个基本定理： .21EvdEVGVv，有，、对图数个。、度为奇数的顶点有偶2 . 3EvdvdEVGVvVv则是有向图，、设图论的基本概念图论的基本概念用图论思想求解以下各题用图论思想求解以下各题例例1、一摆渡人欲将一只狼，一头羊，一篮菜从、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡过河
9、，并且，狼与羊，羊与菜不能独处，给出渡河方法。河方法。图论的基本概念图论的基本概念解：解：用四维用四维0-1向量表示（人，狼，羊，菜）的在西岸向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取状态，（在西岸则分量取1，否则取，否则取0.）共共24=16种状态，种状态，由题设，状态（由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不是不允许的，允许的，从而对应状态（从而对应状态（1,0,0,1），），(1,1,0,0),(1,0,0,0)也是也是不允许的，不允许的，图论的基本概念图论的基本概念人在河西：（1,1,1,1） （1,1,1,0） （1,1,0,1） （1
10、,0,1,1）（1,0,1,0）（0,1,0,1） （0,1,0,0） （0,0,1,0） （0,0,0,1） （0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。图论的基本概念图论的基本概念例例2、考虑中国象棋的如下问题：、考虑中国象棋的如下问题：（1）下过奇数盘棋的人数是偶数个。）下过奇数盘棋的人数是偶数个。（2）马有多少种跳法？）马有多少种跳法？（3）马跳出后又跳回起点，证明马跳了
11、偶数步。）马跳出后又跳回起点，证明马跳了偶数步。（4）红方的马能不能在自己一方的棋盘上不重复）红方的马能不能在自己一方的棋盘上不重复的跳遍每一点，最后跳回起点？的跳遍每一点，最后跳回起点？图论的基本概念图论的基本概念例例3、证明：在任意、证明：在任意6人的集会上，总有人的集会上，总有3人互相认人互相认识，或总有识，或总有3人互相不认识。人互相不认识。解：以顶点表示人，以边表示认识，得解：以顶点表示人，以边表示认识，得6个顶点个顶点的简单图的简单图G。问题：问题：3人互相认识即人互相认识即G包含包含K3为子图，为子图， 3人互相不认识即人互相不认识即G包含（包含（3,0）图为子图。）图为子图。图
12、论的基本概念图论的基本概念 为子图。包含点不相邻，则点至少、这图为子图。包含点两两相邻，则、这。这又包含两种情况：点不相邻个顶即至少与另外个顶点相邻至多与另外）（为子图。包含点相邻，则点至少、这图为子图。包含点互不相邻，则、这两种情况：个顶点相邻，这又包含至少与另外则有两种情况：任取0 , 3232 31 )3(22232 0 , 331 3 1 ,33GKGvKGGvGVv图论的基本概念图论的基本概念定义2 若将图G的每一条边e都对应一个实数F (e), 则称F (e)为该边的权, 并称图G为赋权图(网络), 记为G = (V, E , F ). 定义3 设G = (V, E )是一个图,
13、v0, v1, , vkV, 且“1ik, vi1 viE, 则称v0 v1 vk是G的一条通路.图论的基本概念图论的基本概念 如果通路中没有相同的顶点, 则称此通路为路径, 简称路. 始点和终点相同的路称为圈或回路. 定义定义4 顶点u与v称为连通的，如果存在u-v通路，任二顶点都连通的图称为连通图连通图，否则，称为不连通图。极大连通子图称为连通支连通支。图论的基本概念图论的基本概念定义5 连通而无圈的图称为树, 常用T表示树. 树中最长路的长称为树的高。树的度为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。设G是有向图，如果G的基础图是树，则称G是有向树，也简称树。 邻接矩阵 A
14、 = (aij )nn , EvvEvvajijiij, 0, 1例4：写出右图的邻接矩阵：0101100101001010A解：图的矩阵表示图的矩阵表示 权矩阵A = (aij ) nn EvvjiEvvvvFajijijiij , , 0 ,例5：写出右图的权矩阵：05420370860A解：图的矩阵表示图的矩阵表示 关联矩阵A A = (aij )nm 不关联与若的终点是若的始点是若iiiiiiijeveveva, 0, 1, 1有向图：无向图：不关联与若关联与若jijiijvvvva, 0 , 1图的矩阵表示图的矩阵表示例6：写出右图与其基本图的关联矩阵解：分别为：1101100011
15、011000000111011001A1101100011011000000111011001A图的矩阵表示图的矩阵表示定义定义 1 设设 P ( u, v) 是赋权图是赋权图G = (V, E , F ) 中从中从点点u到到v的路径的路径, 用用E ( P ) 表示路径表示路径P (u, v)中全中全部边的集合部边的集合, 记记F ( P ) = ,则称则称F ( P )为路为路径径P ( u, v) 的的权权或或长度长度( (距离距离) ). )()(PEeeF定义定义 2 若若P0 ( u, v) 是是G 中连接中连接u, v的路径的路径, 且对且对任意在任意在G 中连接中连接u, v的
16、路径的路径P (u, v)都有都有F ( P0 )F ( P ), 则称则称P0 ( u, v) 是是G 中连接中连接u, v的的最短路最短路. 最短路最短路重要性质：重要性质：若若v0 v1 vm 是是G中从中从v0到到vm的最短路的最短路, 则则对对1km, v0v1 vk 必为必为G中从中从v0到到vk的的最短路最短路. 即：最短路是一条路，且最短路的任一段即：最短路是一条路，且最短路的任一段也是最短路。也是最短路。最短路最短路例例7 对下面的有向图求顶点对下面的有向图求顶点v0到到其余顶点的其余顶点的最短路。最短路。0v2v1v3v4v5v1445642537最短路最短路Dijkstr
17、a算法：求某一顶点到其余顶点的最短路 的的最最短短距距离离，最最短短路路到到踪踪）的的紧紧前前顶顶点点（作作逆逆向向追追树树中中的的距距离离到到集集表表示示生生长长到到树树中中的的顶顶点点表表示示用用其其对对应应下下标标数数记记号号：顶顶点点iiiikkvvPdvirvvklSGVSSkv0000:,: SjjrSjjiajllSstep , 0 , 00 ,0:1 3: , 4, , , , 2stepif Sthen stepor elsejSif l jl ka k jthen l jl ka k jr jkturn step 04: , ; 0, ,iojstepif l jthen
18、dl iPr r ir ii 2:min , 4, stepl kl jjSif l kthen stepor else SSk 最短路最短路1v3v2v4v5v68523374例例8：求下列任意两点的最短路和距离。：求下列任意两点的最短路和距离。最短路最短路Floyd算法算法:求任意两顶点的最短路求任意两顶点的最短路 设设A = (aij )nn为赋权图为赋权图G = (V, E, F)的权矩阵的权矩阵, dij表示从表示从vi到到vj点的距离点的距离, rij表示从表示从vi到到vj点的最短路中一点的最短路中一个点的编号个点的编号. 赋初值赋初值. 对所有对所有i, j, dij = ai
19、j, rij = j. k = 1. 转向转向. 更新更新dij , rij . 对所有对所有i, j, 若若dik + dk jdij , 则令则令dij = dik + dkj , rij = k, 转向转向; 终止判断终止判断. 若若k = n终止终止; 否则令否则令k = k + 1, 转向转向. 最短路线可由最短路线可由rij得到得到. 最短路最短路 求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般中某一点到其它各点最短路，一般用用Dijkstra标号算法；标号算法； Dijkstra标号算法只适用于全部权为非负情况。标号算法只适用于全部权为非负情况。 求非负赋权图上任意两点
20、间的最短路，一般用求非负赋权图上任意两点间的最短路，一般用Floyd算法算法. Floyd算法可以适用于有负权的情况，还能判断是算法可以适用于有负权的情况，还能判断是否有负回路。否有负回路。 这两种算法均适用于有向赋权图这两种算法均适用于有向赋权图.最短路最短路由树的定义不难知道由树的定义不难知道, 任意一个连通的任意一个连通的(p, q)图图G适当去掉适当去掉q-p+1条边后条边后, 都可以变成树都可以变成树, 这棵树这棵树称为图称为图G的的生成树生成树. 设设T是图是图G的一棵生成树的一棵生成树, 用用F ( T )表示树表示树T中所有边的权数之和中所有边的权数之和, F ( T )称为树
21、称为树T的的权权.一个连通图一个连通图G的生成树一般不止一棵的生成树一般不止一棵, 图图G的所有生成树中权数最小的生成树称为的所有生成树中权数最小的生成树称为图图G的的最小生成树最小生成树.最小生成树最小生成树1v2v3v4v5v64686865505061456054例例9：如下图：如下图G，求最小生成树：求最小生成树：Kruskal算法：从最小边开始按最小权加边，算法：从最小边开始按最小权加边，有圈去掉。有圈去掉。最小生成树最小生成树 例例10 (10 (设备更新问题设备更新问题) )某企业使用一台设备某企业使用一台设备, ,每年年每年年初初, ,企业都要作出决定企业都要作出决定, ,如果
22、继续使用旧的如果继续使用旧的, ,要付维修费；要付维修费；若购买一台新设备若购买一台新设备, ,要付购买费要付购买费. . 试制定一个试制定一个5 5年更新计年更新计划划, ,使总支出最少使总支出最少. . 已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11, 11,11, 12,12,13. 12,12,13. 使用不同时间设备所需的维修费分别为使用不同时间设备所需的维修费分别为5,6,8,11,18.5,6,8,11,18.最小生成树最小生成树 解解 设设bi 表示设备在第表示设备在第i 年年初的购买费年年初的购买费, ,ci 表示设备表示设备使用使用i 年后的维修
23、费年后的维修费, , V= v1, v2, , v6,点点vi表示第表示第i 年年年年初购进一台新设备初购进一台新设备, ,虚设一个点虚设一个点v6表示第表示第5 5年年底年年底. . E = vivj | 1ij6. . ijkkijicbvvF1)(求求v1到到v6的最短路问题的最短路问题. 最小生成树最小生成树 由实际问题可知由实际问题可知, ,设备使用三年后应当更新设备使用三年后应当更新, ,因此删因此删除该图中除该图中v1到到v5 , ,v1到到v6 , ,v2到到v6的连线；又设备使用一年的连线；又设备使用一年后就更新则不划算后就更新则不划算, ,因此再删除该图中因此再删除该图中v
24、1v2 , ,v2v3 , ,v3v4 , ,v4v5 , ,v5v6 五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6. . 而这两条路都是而这两条路都是v1到到v6的最短路的最短路. .最小生成树最小生成树例例11 多阶段存储问题多阶段存储问题某公司根据市场情况，预计某商品今后六个月的某公司根据市场情况，预计某商品今后六个月的需要量，进货单价与存储单价如下需要量，进货单价与存储单价如下月份123456需要（件） 607070504540单价（元） 800 780860 860 760 810存储月份存储月份 122
25、3344556存储单价存储单价 4035352540若当月订购当月所需商品不附加存储费，问如何若当月订购当月所需商品不附加存储费，问如何进货使总费用最小。进货使总费用最小。最小生成树最小生成树称称G = ( X, Y, E )为为二部图二部图. 如果如果X中的每个点都与中的每个点都与Y中的中的每个点邻接每个点邻接, 则称则称G = ( X, Y, E )为为完备二部图完备二部图. 若若 F：E R +, 则称则称G = ( X, Y, E, F )为为二部赋权图二部赋权图. 定义定义1 设设X , Y都是非空有限顶点集都是非空有限顶点集, 且且X Y = ,YyXxxyE, 的一个匹配。的一个
26、匹配。是是中均不邻接，则称中均不邻接，则称边在边在中任意两条中任意两条若若设图设图定义定义GMGMEM,EV,G 2 二部图的匹配及其应用二部图的匹配及其应用定义定义3 若匹配若匹配M的某条边与点的某条边与点v关联关联, 则称则称M饱和饱和点点v, 并且称并且称v是是M的的饱和点饱和点, 否则称否则称v是是M的的非饱非饱和点和点. 定义定义4 设设M是图是图G的一个匹配的一个匹配, 如果如果G的每一个点的每一个点都是都是M的饱和点的饱和点, 则称则称M是是完美匹配完美匹配；如果；如果G中中没有另外的匹配没有另外的匹配M0, 使使 | M0 | M |, 则称则称M是是最最大匹配大匹配. 每个完
27、美匹配都是最大匹配每个完美匹配都是最大匹配, 反之不一定成立反之不一定成立. 二部图的匹配及其应用二部图的匹配及其应用例例16： 判断下图的匹配判断下图的匹配最大匹配最大匹配非完美匹配非完美匹配完美匹配完美匹配二部图的匹配及其应用二部图的匹配及其应用定义定义5 设设M是图是图G的的一个匹配的的一个匹配, 其边在其边在EM和和M 中交错出现的路中交错出现的路, 称为称为G的一条的一条M交错路交错路. 起点起点和终点都不是和终点都不是M的饱和点的的饱和点的M 交错路交错路, 称为称为M 增广路增广路. 定理定理1 G的一个匹配的一个匹配M是最大匹配的是最大匹配的充要条件充要条件是是G不包含不包含M
28、 增广路增广路. 二部图的匹配及其应用二部图的匹配及其应用定理定理2 设设G = ( X, Y, E )为二部图为二部图, 则则 G存在存在饱和饱和X的每个点的匹配的充要条件是的每个点的匹配的充要条件是对任意对任意S ,有有 | N (S ) | | S | .其中其中, N (S ) = v | uS, v与与u相邻相邻. G存在完美匹配的充要条件是存在完美匹配的充要条件是对任意对任意S 或或S 有有 | N (S ) | | S | . X XY二部图的匹配及其应用二部图的匹配及其应用工作安排问题之一工作安排问题之一 给给n个工作人员个工作人员x1, x2, , xn安排安排n项工作项工作
29、y1, y2, , yn. . n个工作人员中每个人能胜任一项或几项工作个工作人员中每个人能胜任一项或几项工作, 但并但并不是所有工作人员都能从事任何一项工作不是所有工作人员都能从事任何一项工作. 比如比如x1能做能做y1, y2工作工作, x2能做能做y2, y3, y4工作等工作等. 这样便提出一个问题这样便提出一个问题, 对所有的工作人员能不能都对所有的工作人员能不能都分配一件他所能胜任的工作？分配一件他所能胜任的工作？ 二部图的匹配及其应用二部图的匹配及其应用 我们构造一个二部图我们构造一个二部图G = ( X, Y, E ), 这里这里X = x1, x2, , xn,Y = y1,
30、 y2, , yn, 并且当且仅当工作人员并且当且仅当工作人员xi胜任工作胜任工作yj时时, xi与与yj才相邻才相邻. 于是于是, 问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配. 因为因为 |X|=|Y|, 所以完美匹配即为最大匹配所以完美匹配即为最大匹配. 二部图的匹配及其应用二部图的匹配及其应用1x2x3x4x5x1y2y3y4y5y例例17：求下图完美匹配：求下图完美匹配Hungarian算法：算法： 时终止。时终止。STSN 二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法： 解解 取初始匹配取初始匹配
31、M0 = x2 y2 , x3 y3 , x5 y5 给给X中中M0的两个非饱和点的两个非饱和点x1, ,x4都给以标号都给以标号0 0和和标记标记* * ( (如下图所示如下图所示). ). 00*二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：00 去掉去掉x1的标记的标记*, 将与将与x1邻接的两个点邻接的两个点y2, y3都给以都给以标号标号1.1. 因为因为y2, y3都是都是M0的两个饱和点的两个饱和点, ,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2, x3都给以相应的标号和标记都给以相应的标号和标记
32、*. *11*23*二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：00*11*23* 去掉去掉x2的标记的标记*, 将与将与x2邻接且尚未给标号的三邻接且尚未给标号的三个点个点y1, y4, y5都给以标号都给以标号2. 222二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：00*1123*222 因为因为y1是是M0的非饱和点的非饱和点, 逆向返回逆向返回, 直到直到x1为为0为为止止. .于是得到于是得到M0的增广路的增广路x1 y2x2 y1, 记记P = x
33、1 y2 , y2x2 , x2 y1. 取取M1 = M0P = x1 y2 , x2 y1 , x3 y3 , x5 y5, 则则M1是比是比M多一边的匹配多一边的匹配. 二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：0* 再给再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*, 然后然后去掉去掉x4的标记的标记*, 将与将与x4邻接的两个点邻接的两个点y2, y3都给以标号都给以标号4. 44二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：
34、044 因为因为y2, y3都是都是M1的两个饱和点的两个饱和点, , 所以将它们在所以将它们在M1中邻接的两个点中邻接的两个点x1, x3都给以相应的标号和标记都给以相应的标号和标记*.*23二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：044*23 去掉去掉x1的标记的标记*, 因为与因为与x1邻接的两个点邻接的两个点y2, y3都有标号都有标号4, 所以去掉所以去掉x3的标记的标记*. 而与而与x3邻接的两个点邻接的两个点y2, y3也都有标号也都有标号4, 此时此时X中所中所有有标号的点都已去掉了标记有有标号的点都已去掉
35、了标记*(如下图所示如下图所示), 因此因此M1是是G的最大匹配的最大匹配.没有完美匹配。没有完美匹配。 二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：注意到注意到S=x1,x3,x4时，时，N(S)=y1,y3, ,N SS 所以没有完美匹配。所以没有完美匹配。二部图的匹配及其应用二部图的匹配及其应用定义定义6 设设G = ( X, Y, E , F )为完备的二部赋权为完备的二部赋权图图, 若若L：X Y R + 满足：满足：对任意对任意xX, yY , L (x) + L ( y ) F (x y), 则称则称L为为G的一
36、个的一个可行点标记可行点标记, 记相应的生成记相应的生成子图为子图为GL = ( X, Y, EL , F ), 这里这里EL = x yE | L ( x ) + L ( y ) = F (x y). 定理定理3 设设L是完备的二部赋权图是完备的二部赋权图G = ( X, Y, E , F )的可行点标记的可行点标记, 若若M *是是GL的完美匹配的完美匹配, 则则M *是是G的最佳匹配的最佳匹配. (权数最大的匹配权数最大的匹配) 二部图的匹配及其应用二部图的匹配及其应用工作安排问题之二工作安排问题之二 给给n个工作人员个工作人员x1, x2, , xn安排安排n项工作项工作y1, y2,
37、 , yn. . 如果每个工作人员工作效率不同如果每个工作人员工作效率不同, 要求工作分配的要求工作分配的同时考虑同时考虑总效率最高总效率最高. 二部图的匹配及其应用二部图的匹配及其应用 我们构造一个二部赋权图我们构造一个二部赋权图G = ( X, Y, E , F ), 这里这里X = x1, x2, , xn,Y = y1, y2, , yn, F(xi yj )为工作人员为工作人员xi胜胜任工作任工作yj时的工作效率时的工作效率. 则问题转化为：求二部赋权图则问题转化为：求二部赋权图G的最佳匹配的最佳匹配. 在求在求G 的最佳匹配时的最佳匹配时, 总可以假设总可以假设G为完备二部赋权为完
38、备二部赋权图图. .若若xi与与yj不相邻不相邻, 可令可令F(xi yj )=0. 同样地同样地, 还可虚设点还可虚设点x或或y, ,使使|X|=|Y|. .如此就将如此就将G 转化为完备二部赋权图转化为完备二部赋权图, ,而且而且不会影响结果不会影响结果. 二部图的匹配及其应用二部图的匹配及其应用例例19：求赋权矩阵为：求赋权矩阵为 4124153123543263A的的完备二部赋权图完备二部赋权图G=(X,Y,E,F)的最佳匹配。的最佳匹配。可行顶点标号法：可行顶点标号法：矩阵覆盖法：矩阵覆盖法：分枝定界法：分枝定界法：二部图的匹配及其应用二部图的匹配及其应用矩阵覆盖法：矩阵覆盖法：ST
39、EP1：求等价分配矩阵。：求等价分配矩阵。STEP2：求独立零元，画上框。（非同列同行的零）：求独立零元，画上框。（非同列同行的零）STEP3：最优判别：达到：最优判别：达到n个独立零元。停。个独立零元。停。STEP4：求覆盖线：求覆盖线： 1）封锁没有画框零元的行，封锁就打）封锁没有画框零元的行，封锁就打； 2）在封锁行中未画框零元的列也封锁；）在封锁行中未画框零元的列也封锁； 3）在封锁列中画框零元的行也封锁；）在封锁列中画框零元的行也封锁； 4）未封锁行与封锁列画上覆盖线。）未封锁行与封锁列画上覆盖线。STEP5：调节分配矩阵：在未覆盖元中选取最大元：调节分配矩阵：在未覆盖元中选取最大元
40、k，未覆盖行加未覆盖行加 k ，覆盖列减，覆盖列减 k 。转。转STEP2.二部图的匹配及其应用二部图的匹配及其应用 定义定义1 设设G = ( V, E )为有向图为有向图, 在在V中指定一点称中指定一点称为为发点发点(记为记为vs ), 和另一点称为和另一点称为收点收点(记为记为vt ), 其余点叫其余点叫做做中间点中间点. 对每一条边对每一条边vivjE, 对应一个非负实数对应一个非负实数Cij, 称称为它的为它的容量容量. 这样的这样的G称为称为容量网络容量网络, 简称简称网络网络, 记作记作G = ( V, E, C ) .G中任一边中任一边vivj有流量有流量fij , 称集合称集
41、合f = fij为为网络网络G上的一个上的一个流流. 网络流问题网络流问题定义定义2 满足下述条件的流满足下述条件的流 f 称为称为可行流可行流： (容量限制条件容量限制条件) 对每一边对每一边vivj, 有有0 fij Cij ; (平衡条件平衡条件) 对于中间点对于中间点vk有有fik =fkj , 即中即中间点间点vk的输入量的输入量 = 输出量输出量.如果如果f 是可行流是可行流, 则对收、发点则对收、发点vt、vs有有fsi =fjt =Wf, 即从即从vs点发出的物质总量点发出的物质总量= vt点输入的量点输入的量. Wf称为网络称为网络流流 f的总流量的总流量.网络流问题网络流问
42、题一个可行流一个可行流 f = f ij , 当当 f ij = C ij时时, 则称流则称流 f 对边对边vivj是是饱饱和和的的; 当当f ijC ij时时, 则称流则称流 f 对边对边是非饱和是非饱和的的. 把把f ij = 0的边的边称为称为零流边零流边, f ij 0的边称为的边称为非零流边非零流边. 若若 为网络中从为网络中从vs到到vt的一条链的一条链(有向图中的路有向图中的路), 定义链的定义链的方向是从方向是从vs到到vt , 边的方向与链的方向相同称为边的方向与链的方向相同称为前向边前向边, 前前向边的全体记为向边的全体记为 + ; 边的方向与链的方向相反称为边的方向与链的
43、方向相反称为后向后向边边, 后向边的全体记为后向边的全体记为. 最大流问题最大流问题定义定义3 设设f是一个可行流是一个可行流, 是从是从vs到到vt一条链一条链. 如果满足如果满足 当当vivj+ 时时, 0 f ij Cij, 即即 + 中的每一条边都中的每一条边都非饱和边非饱和边; 当当vivj时时, 0 f ij C ij, 即即 中的每一条边都中的每一条边都非零边非零边.则称则称为从为从vs到到vt的关于的关于f 的的可增广链可增广链. 最大流问题最大流问题定义定义4 容量网络容量网络G = ( V, E, C ), 若点集若点集V被剖分为两被剖分为两个非空集合个非空集合S, S c
44、 = V S, vs, vt分属于分属于S, S c. 则把边集则把边集 (S, S c ) = vivj | vivjE, viS, vjS c 称为称为G的的割集割集 .若把一割集的边从网络中去掉若把一割集的边从网络中去掉, 则从则从vs到到vt便不在相通便不在相通, 所以割集是从所以割集是从vs到到vt的必经之路的必经之路.割集割集(S, S c )中所有边中所有边的容量之和的容量之和, 称为这个称为这个割集的容量割集的容量, 记为记为C (S, S c ). 最大流问题最大流问题定理定理1 设设 f 为网络为网络G = ( V, E, C ) 的任一可行流的任一可行流, (S, S c
45、 ) 是剖分是剖分vs , vt 的任一割集的任一割集, 则有则有Wf C (S, S c ). 若有可行流若有可行流 f 和割集和割集 (S, S c ), 使得使得Wf = C (S, S c ), 则则f 一定是一定是G的的最大流最大流, 而而 (S, S c ) 必定是必定是G中所有割集中容量小的一个中所有割集中容量小的一个, 即即最小割集最小割集. 例例20：给出网络的割。：给出网络的割。sv2v1v3vtv2343125最大流问题最大流问题定理定理2 (最大流最大流最小割定理最小割定理) 任一个网络中任一个网络中G中中, 从从vs到到vt的的最大流的流量最大流的流量等于分割等于分割
46、vs, vt的的最小割的容量最小割的容量. 推论推论 可行流可行流f是最大流的充要条件是不存在从是最大流的充要条件是不存在从vs到到vt的的(关于关于f的的)可增广链可增广链. 最大流问题最大流问题 实际问题中实际问题中, ,一个网络会出现下面两种情况：一个网络会出现下面两种情况： 发点和收点都不止一个发点和收点都不止一个. . 解决的方法是再虚设一个发点解决的方法是再虚设一个发点vs和一个收点和一个收点vt , ,发点发点vs到所有原发点边的容量都设为无穷大到所有原发点边的容量都设为无穷大, , 所有原收点到所有原收点到收点收点vt 边边的容量都设为无穷大的容量都设为无穷大. . 网络中除了
47、边有容量外网络中除了边有容量外, ,点也有容量点也有容量. . 解决的方法是将所有有容量的点分成两个点解决的方法是将所有有容量的点分成两个点, ,如点如点v有容量有容量Cv , ,将点将点v分成两个点分成两个点v和和v, ,令令C(vv ) = Cv . . 最大流问题最大流问题例例21：求网络的最大流。：求网络的最大流。sv1v2vtv探索：单向调整法：探索：单向调整法：双向调整法：双向调整法：Ford-Fulkerson算法算法最大流问题最大流问题例例22： 图图6-24表明一个网络及初始可行流表明一个网络及初始可行流, 每条每条边上的有序数表示边上的有序数表示 (C ij , f ij
48、). 求这个网络的最大求这个网络的最大流流. 标号算法：标号算法：最大流问题最大流问题一般提法：一般提法：已知网络已知网络G = ( V, E, C ) , 每条边每条边vivjE除了已给容量除了已给容量Cij外外, 还给出了单位流量的费用还给出了单位流量的费用bij (0). 所谓最小费用流所谓最小费用流问题就是求一个总流量已知的可行流问题就是求一个总流量已知的可行流f = f ij 使得总费使得总费用用最小最小. 当要求当要求f为最大流时为最大流时, 此问题即为此问题即为最小费用最大流问题最小费用最大流问题. ijEvvijfbfbji)(最小费用流问题最小费用流问题例例23：求下列网络的
49、最小费用流。：求下列网络的最小费用流。sv1v2vtv3,14,23,65,24,2负回路算法：负回路算法：迭加算法：迭加算法：最小费用流问题最小费用流问题 定义定义：一个工程由若干相互独立的活动组成，每：一个工程由若干相互独立的活动组成，每个活动称为个活动称为工序工序，我们，我们用顶点表示工序用顶点表示工序，如果工序，如果工序 i 完完成之后工序成之后工序 j 才能启动才能启动,则图中有一条有向边则图中有一条有向边(i , j ),其其权权wi 表示工序表示工序 i 所需的时间所需的时间。这样得。这样得到的赋权有向图到的赋权有向图G=（V,E）称为）称为PT图图。PT图必定不存在有向回路。图
50、必定不存在有向回路。 在在PT图中，当起点与终点不唯一时，可增加图中，当起点与终点不唯一时，可增加两个两个虚拟结点虚拟结点v0和和vn 作为新的起点与终点，作为新的起点与终点， v0和和vn表示表示虚工序虚工序，与，与v0连接的边的权为连接的边的权为0，与，与vn连接连接的边的权为原终点工序所需时间。的边的权为原终点工序所需时间。PT图图 例例24 24 一项工程由一项工程由1313道工序组成道工序组成, , 所需时间所需时间( (单位：单位：天天) )及先行工序如下表所示及先行工序如下表所示(P172).(P172).工序序号工序序号 A B C D E F G H I J K L MA B