数学建模图论模型-课件

图论模型图论模型图论模型图论模型1.图论基本概念图论基本概念2.最短路径算法最短路径算法3.最小生成树算法最小生成树算法4.遍历性问题遍历性问题5.二分图与匹配二分图与匹配6.网络流问题网络流问题7.关键路径问题关键路径问题8.系统监控模型系统监控模型9.着色模型着色模型2精品资料你怎么称呼老师？如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？你所经历的课堂，是讲座式还是讨论式？教师的教鞭“不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘”“太阳当空照，花儿对我笑，小鸟说早早早”1、图论的基本概念、图论的基本概念问题问题1(1(哥尼斯堡七桥哥尼斯堡七桥问题问题):):能否从任一陆地出发通过每座桥恰好一次而能否从任一陆地出发通过每座桥恰好一次而回到出发点？回到出发点？5欧拉指出：欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地陆地出发，必能通过每座桥恰好一次而回到出发地.6问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题问题):):十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，个城市，能否从某个城市出发在十二面体上依次经过每个能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？欧拉问题是欧拉问题是“边遍历边遍历”，哈密尔顿问题是，哈密尔顿问题是“点遍历点遍历”7问题问题3(3(四色问题四色问题):):对任何一张地图进行着色，两个共同边界的国家染不同的颜对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了色，则只需要四种颜色就够了.问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装小至组装一台机床一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这些工序相互约束这些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一个工序才能开始一个工序才能开始.即它们之间存在即它们之间存在完成的先后次序关系完成的先后次序关系,一般认为这些关系是预知的一般认为这些关系是预知的,而且也能够而且也能够预计完成每个工序所需要的时间预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目成整个工程项目,影响工程进度的要害工序是哪几个？影响工程进度的要害工序是哪几个？8图的定义图的定义 图论中的图论中的“图图”并不是通常意义下的几何图形或物体的形并不是通常意义下的几何图形或物体的形状图状图,而是以一种抽象的形式来表达一些确定的事物之间的联而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统系的一个数学系统.定义定义1一个有序二元组一个有序二元组(V,E)称为一个称为一个图图,记为记为G=(V,E),其中其中 V称为称为G的顶点集的顶点集,V,其元素称为其元素称为顶点顶点或或结点结点,简称简称点点;E称为称为G的边集的边集,其元素称为其元素称为边边,它联结它联结V 中的两个点中的两个点,如如果这两个点是无序的果这两个点是无序的,则称该边为则称该边为无向边无向边,否则否则,称为称为有向边有向边.如果如果V=v1,v2,vn是有限非空点集是有限非空点集,则称则称G为为有限图有限图或或n阶图阶图.如果如果E的每一条边都是无向边的每一条边都是无向边,则称则称G为为无向图无向图(如图如图1)1);如如果果E的每一条边都是有向边的每一条边都是有向边,则称则称G为为有向图有向图(如图如图2)2);否则否则,称称G为为混合图混合图.图图1 1 图图2 2并且常记并且常记:V=v1,v2,vn,|V|=n;E=e1,e2,em(ek=vivj),|E|=m.称点称点vi,vj为边为边vivj的的端点端点.在有向图中在有向图中,称点称点vi,vj分别为边分别为边vivj的的始点始点和和终点终点.该图称为该图称为(n,m)图图10 对于一个图对于一个图G=(V,E),人们常用图形来表示它人们常用图形来表示它,称称其为其为图解图解.凡是有向边凡是有向边,在图解上都用箭头标明其方向在图解上都用箭头标明其方向.例如例如,设设V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4,则则G=(V,E)是一个有是一个有4个顶点和个顶点和6条边的图条边的图,G的图解如下图所示的图解如下图所示.11 一个图会有许多外形不同的图解一个图会有许多外形不同的图解,下面两个图表示同一个图下面两个图表示同一个图G=(V,E)的图解的图解.这两个图互为这两个图互为同构图同构图,今后将不计较这种外形今后将不计较这种外形上的差别上的差别,而用一个容易理解的、确定的图解去表示一个图而用一个容易理解的、确定的图解去表示一个图.12 有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点,有一个公共端点的边称为有一个公共端点的边称为相相邻边邻边.边和它的端点称为边和它的端点称为互相关联互相关联.常用常用d(v)表示图表示图G中与顶点中与顶点v关联关联的边的数目的边的数目,d(v)称为顶点称为顶点v的的度数度数.对于有向图对于有向图,还有还有出度出度和和入度入度之之分分.用用N(v)表示图表示图G中所有与顶点中所有与顶点v相邻的顶点的集合相邻的顶点的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2dout(v1)=dout(v3)=dout(v4)=2,dout(v2)=1din(v1)=din(v3)=din(v4)=2,din(v2)=113握手定理握手定理握手定理：握手定理：无向图中，所有结点的度数之和等于2m。右图：推论推论1：无向图中必有偶数个度数为奇数的结点。推论推论2：有向图中所有结点的出度之和等于入度之和。d(v1)=d(v3)=d(v4)=4,d(v2)=214我们今后只讨论我们今后只讨论有限简单图有限简单图：(1)(1)顶点个数是有限的顶点个数是有限的;(2)(2)任意一条边有且只有两个不同的点与它相互关联任意一条边有且只有两个不同的点与它相互关联;(3)(3)若是无向图若是无向图,则任意两个顶点最多只有一条边与之相则任意两个顶点最多只有一条边与之相联结联结;(4)(4)若是有向图若是有向图,则任意两个顶点最多只有两条边与之相则任意两个顶点最多只有两条边与之相联结联结.当两个顶点有两条边与之相联结时，这两条边的方向当两个顶点有两条边与之相联结时，这两条边的方向相反相反.如果某个有限图不满足如果某个有限图不满足(2)(3)(4),(2)(3)(4),可在某条边上增设顶点可在某条边上增设顶点使之满足使之满足.定义定义2若将图若将图G的每一条边的每一条边e都对应一个实数都对应一个实数F(e),则称则称F(e)为该边的为该边的权权,并称图并称图G为为赋权图赋权图(网络网络),记为记为G=(V,E,F).定义定义3任意两点均有通路的图称为任意两点均有通路的图称为连通图连通图.定义定义4连通而无圈的图称为连通而无圈的图称为树树,常用常用T表示树表示树.16常用的图常用的图给定图G=和 G=是两个图，如果有 V V 和 E E,则称图G是图 G 的子子图图。若V=V 称图G是图 G 的生成生成子图子图；若将图G的每一条边e都对应一个实数F(e)，则称F(e)为该边的权，并称图G为赋赋权权图图(网网络络),记为G=。任意两点均有通路的图称为连通图。连通图。连通而无圈的图称为树，树，常用T=表示树。若图G是图 G 的生成子图，且G又是一棵树，则称G是图G 的生成树生成树。例例 Ramsey问题问问题题：任何6个人的聚会，其中总会有3个互相认识或3人互相不认识。图图论论模模型型：用红、蓝两种颜色对6个顶点的完全图K6的边边进行任意着色，则不论如何着色必然都存在一个红色的K3或一个蓝色的K3。对对应应关关系系：每每个个人人即即为为一一个个结结点点；人人与与人人之之间间的的关关系系即即为为一条边一条边例例 Ramsey问题图论证明：图论证明：用红、蓝两种颜色对K6的边边进行着色，K6的任意一个顶点均有5条边与之相连接，这5条边必有3条边的颜色是相同的，不妨设为蓝色（如图）与这3条边相关联的另外3个节点之间的3条边，若都为红色，则形成红色的红色的K3；若另外3个节点之间的3条边有一条为蓝色，则与上面的蓝色边形成蓝色的蓝色的K3；因此必然存在一个红色的K3或一个蓝色的K3。例例 Ramsey问题Ramsey数：数：R（3,3）=6；R（3,4）=9；。20例例 过河问题过河问题问问题题：一摆渡人欲将一只狼、一头羊、一篮菜从河西渡过河到河东。由于船小，一次只能带一物过河，并且狼与羊，羊与菜不能独处，给出渡河方法。这里显然不能用一个节点表示一个物体。一个物体可能在河东，也可能在河西，也可能在船上，状态表示不清楚。另外，问题也可以分成几个小问题，如：问题是否能解？有几种不同的解法？最快的解决方案是什么？例例 过河问题过河问题解解：用四维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)也是不允许的。以以可可允允许许的的10个个状状态态向向量量作作为为顶顶点点，将将可可能能互互相相转转移移的的状状态用态用边边连接起来构成一个图。连接起来构成一个图。利用图论的相关知识即可回答原问题。例例 过河问题过河问题(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西河西=(人人,狼狼,羊羊,菜菜)河东河东=(人人,狼狼,羊羊,菜菜)将10个顶点分别记为A1,A2,A10,从图中易得到两条路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.问题的转换：问题的转换：过河问题是否能解？即：图中A1到A10是否连通？有几种不同的解法？即：A1到A10之间有多少条不同的路径？最快的解决方案是什么？即：A1到A10最短路径有哪些？图的矩阵表示图的矩阵表示 邻接矩阵：邻接矩阵：邻接矩阵表示了点与点之间的邻接关邻接矩阵表示了点与点之间的邻接关系系.一个一个n阶图阶图G的邻接矩阵的邻接矩阵A=(aij)nn,其中其中 24无向图无向图G的邻接矩阵的邻接矩阵A是一个对称矩阵是一个对称矩阵.权矩阵权矩阵 一个一个n阶赋权图阶赋权图G=(V,E,F)的权矩阵的权矩阵A=(aij)nn,其中其中 有限简单图基本有限简单图基本上可用权矩阵来上可用权矩阵来表示表示.25无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵.26 关联矩阵：关联矩阵：一个有一个有m条边的条边的n阶有向图阶有向图G的关联的关联矩阵矩阵A=(aij)nm,其中其中 若若vi是是ej的始点的始点;若若vi是是ej的终点的终点;若若vi与与ej不关联不关联.有向图的关联矩阵每列的元素中有且仅有一个有向图的关联矩阵每列的元素中有且仅有一个1,1,有且仅有且仅有一个有一个-1.1.27 一个有一个有m条边的条边的n阶无向图阶无向图G的关联矩阵的关联矩阵A=(aij)nm,其其中中 若若vi与与ej关联关联;若若vi与与ej不关联不关联.无向图的关联矩阵每列的元素中有且仅有两个无向图的关联矩阵每列的元素中有且仅有两个1.1.282 2、最短路径、最短路径算法算法 定义定义1 设设P(u,v)是赋权图是赋权图G=(V,E,F)中从点中从点u到到v的路径的路径,用用E(P)表示路径表示路径P(u,v)中全部边的集合中全部边的集合,记记则称则称F(P)为路径为路径P(u,v)的的权权或或长度长度(距离距离).定义定义2 若若P0(u,v)是是G中连接中连接u,v的路径的路径,且对任意在且对任意在G中连中连接接u,v的路径的路径P(u,v)都有都有F(P0)F(P),则称则称P0(u,v)是是G中连接中连接u,v的的最短路最短路.重要性质：重要性质：若若v0v1vm 是是图图G中从中从v0到到vm的最短路的最短路,则则 1km,v0v1vk 必为必为G中从中从v0到到vk的最短路的最短路.即：最短路是一条路，且最短路的任一段也是最短路即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般用中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法算法.这两种算法均适用于有向非负赋权图这两种算法均适用于有向非负赋权图.下面分别介绍两种算法的基本过程下面分别介绍两种算法的基本过程.30Dijkstra算法算法指标指标（a为起点）为起点）设设T为为V的子集，的子集，P=V-T且且aT，对所有，对所有tT，设设l(t)表示从表示从a到到t的所有通路中距离最短的一条的长度，的所有通路中距离最短的一条的长度，且这条路径中不包含且这条路径中不包含T中其他的结点，则称中其他的结点，则称l(t)为为t关于关于集合集合P的指标，若不存在这样的路径，这记的指标，若不存在这样的路径，这记l(t)=注：注：l(t)不一定是从不一定是从a到到t的最短路径，因为最短路径中可能包含的最短路径，因为最短路径中可能包含T中其中其他的节点。他的节点。定理定理1若若t是是T中关于中关于P由最小指标的结点，则由最小指标的结点，则l(t)是是a和和t之间的最短距离。之间的最短距离。定理定理2设设T为为V的子集，的子集，P=V-T，设，设(1)对对P中的任一点中的任一点p,存在一条从存在一条从a到到p的最短路径的最短路径,这条路径仅有这条路径仅有P中的中的点构成点构成,(2)对于每一点对于每一点t,它关于它关于P的指标为的指标为l(t),令令x为最小指标所在的点为最小指标所在的点,即即:(3)令令P=PUx,T=T-x,l(t)表示表示T中结点中结点t关于关于P的指标的指标,则则31Dijkstra算法算法（求（求a点到其他点的最短路径）点到其他点的最短路径）1、初始化，、初始化，P=a，T=V-a，对每个结点，对每个结点t计算指标计算指标l(t)=w(a,t)2、设、设x为为T中关于中关于P有最小指标的点有最小指标的点,即即:l(x)=min(l(t)(tT),3、若、若T=,则算法结束则算法结束;否则否则,令令P=PUx,T=T-x按照公式按照公式l(t)=minl(t),l(x)+w(x,t),计算计算T中每一个结点中每一个结点t关于关于P的指标的指标.4、P代替代替P,T代替代替T,重复步骤重复步骤2,3（其中：其中：w(x,y)为图的权矩阵）为图的权矩阵）32改进改进Dijkstra算法算法（求（求a点到其他点的最短路径）点到其他点的最短路径）1、初始化，、初始化，P=a，T=V-a，对每个结点，对每个结点t计算指标计算指标l(t)=w(a,t),pro(t)=a;2、设、设x为为T中关于中关于P有最小指标的点有最小指标的点,即即:l(x)=min(l(t)(tT);3、若、若T=,则算法结束则算法结束;否则否则,令令P=PUx,T=T-x按照公式按照公式l(t)=minl(t),l(x)+w(x,t),计算计算T中每一个结点中每一个结点t关于关于P的指标的指标.若若l(x)+w(x,t)l(t),pro(t)=x;4、P代替代替P,T代替代替T,重复步骤重复步骤2,3（其中：其中：w(x,y)为图的权矩阵）为图的权矩阵）33例例 求下图中求下图中A A点到其他点的最短路点到其他点的最短路.34Floyd算法算法（求任意两点的最短路径）（求任意两点的最短路径）设设A=(aij)nn为赋权图为赋权图G=(V,E,F)的权矩阵的权矩阵,dij表示表示从从vi到到vj点的距离点的距离,rij表示从表示从vi到到vj点的最短路中前一个点点的最短路中前一个点的编号的编号.赋初值赋初值.对所有对所有i,j,dij=aij,rij=j.k=1.转向转向.更新更新dij,rij.对所有对所有i,j,若若dik+dk jdij,则令则令dij=dik+dkj,rij=k,转向转向;终止判断终止判断.若若k=n终止终止;否则令否则令k=k+1,转向转向.最短路线可由最短路线可由rij得到得到.例例 求下图中任意两点间的最短路求下图中任意两点间的最短路.36例例 设备更新问题设备更新问题 某企业每年年初某企业每年年初,都要作出决定都要作出决定,如果继续使用旧设备如果继续使用旧设备,要付要付维修费；若购买一台新设备维修费；若购买一台新设备,要付购买费要付购买费.试制定一个试制定一个5 5年更新计年更新计划划,使总支出最少使总支出最少.已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11,12,12,13.11,11,12,12,13.使使用不同时间设备所需的维修费分别为用不同时间设备所需的维修费分别为5,6,8,11,18.5,6,8,11,18.解解 设设bi 表示设备在第表示设备在第i 年年初的购买费年年初的购买费,ci 表示设备使用表示设备使用i 年年后的维修费后的维修费,V=v1,v2,v6,点点vi表示第表示第i 年年初购进一台新设备年年初购进一台新设备,虚设一个虚设一个点点v6表示第表示第5 5年年底年年底.E=vivj|1ij6,每条每条边边vivj表一台设备，从第表一台设备，从第i年年初购买使用年年初购买使用到第到第j年年初报废年年初报废.这样上述设备更新问题就变为：在有向赋权图这样上述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下图解如下)中求中求v1到到v6的最短路问题的最短路问题.38 由实际问题可知由实际问题可知,设备使用三年后应当更新设备使用三年后应当更新,因此删因此删除该图中除该图中v1到到v5,v1到到v6,v2到到v6的连线；又设备使用一年的连线；又设备使用一年后就更新则不划算后就更新则不划算,因此再删除该图中因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6.而这两条路都是而这两条路都是v1到到v6的最短路的最短路.393 3、最小生成树、最小生成树 由树的定义不难知道由树的定义不难知道,任意一个连通的任意一个连通的(n,m)图图G适当去掉适当去掉m-n+1条边后条边后,都可以变成树都可以变成树,这棵树称为图这棵树称为图G的的生成树生成树.设设T是图是图G的一棵生成树的一棵生成树,用用F(T)表示树表示树T中所有边的权数之和中所有边的权数之和,F(T)称为称为树树T的权的权.一个连通图一个连通图G的生成树一般不止一棵的生成树一般不止一棵,图图G的所有生成树中权的所有生成树中权数最小的生成树称为图数最小的生成树称为图G的的最小生成树最小生成树-Minimum-costSpanningTree(MST).求最小生成树问题有很广泛的实际应用求最小生成树问题有很广泛的实际应用.例如例如,把把n个乡镇用高个乡镇用高压电缆连接起来建立一个电网压电缆连接起来建立一个电网,使所用的电缆长度之和最短使所用的电缆长度之和最短,即费即费用最小用最小,就是一个求最小生成树问题就是一个求最小生成树问题.Kruskal算算法法 从未选入树中的边中选取权重最小的且不构成回路从未选入树中的边中选取权重最小的且不构成回路的边加入到树中的边加入到树中.（判断回路比较麻烦）（判断回路比较麻烦）算法过程：算法过程：1.将各边按权值从小到大进行排序将各边按权值从小到大进行排序2.找出权值最小且找出权值最小且不与已加入最小生成树集合的边构成回路不与已加入最小生成树集合的边构成回路的的边。若符合条件，则加入最小生成树的集合中。不符合条件则边。若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。继续遍历图，寻找下一个最小权值的边。3.递归重复步骤递归重复步骤1，直到找出，直到找出n-1条边为止，得到最小生成树。条边为止，得到最小生成树。时间复杂度时间复杂度只和边有关，可以证明其时间复杂度为只和边有关，可以证明其时间复杂度为O(mlogm)41求最小生成树求最小生成树42Prim算法算法 把结点分成两个集合，已加入树中的把结点分成两个集合，已加入树中的(P P)和未加入树中的和未加入树中的(Q Q)，然后每次选择一个点在，然后每次选择一个点在P P中一个点在中一个点在Q Q中的权重最小的边，加入中的权重最小的边，加入树中，并把相应点加入树中，并把相应点加入P P中。中。类似地类似地,可定义连通图可定义连通图G 的最大生成树的最大生成树.算法过程：算法过程：1：初始化：任取一个节点：初始化：任取一个节点u加入生成树加入生成树,P=u0,Q=V-u0,生成树的边集生成树的边集TE=。2：在所有：在所有uP,vQ的边的边(u,v)（称为可选边集称为可选边集）中，找一条权重最小的）中，找一条权重最小的边边(u1,v1)，将此边加进集合，将此边加进集合TE中，并将中，并将v加入加入P中。同时对与中。同时对与v关联的边，若关联的边，若另一个端点已经在另一个端点已经在P中，则从可选边集中删除，否则加入可选边集。中，则从可选边集中删除，否则加入可选边集。3：如果：如果P=V，则算法结束；否则重复步骤，则算法结束；否则重复步骤2。我们可以算出当我们可以算出当U=V时，步骤时，步骤2共执行了共执行了n1次，次，TE中也增加了中也增加了n1条条边，这边，这n1条边就是需要求出的最小生成树的边。条边就是需要求出的最小生成树的边。43例例 选址问题选址问题 现准备现准备在在n 个个居民点居民点v1,v2,vn中设置一银行中设置一银行.问问设在哪个点设在哪个点,可使最大服务距离最小可使最大服务距离最小?若设置两个银行若设置两个银行,问设在哪两个点问设在哪两个点?模型假设模型假设 假设各假设各个个居民点都有条件设置银行居民点都有条件设置银行,并并有路相连有路相连,且路长已知且路长已知.模型建立与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民居民点点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.设置一个银行设置一个银行,银行设银行设在在vi 点点的最大服务距离为的最大服务距离为求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在vk 点点,可使最大服务距离最小可使最大服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最大服务距离最小使最大服务距离最小.记记则则s,t 满足：满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？454、遍历性问题、遍历性问题一、欧拉图一、欧拉图G=(V,E)为一连通无向图经过G中每条边至少一次的回路称为巡回巡回；经过G中每条边正好一次的巡回称为欧拉巡回欧拉巡回；存在欧拉巡回的图称为欧拉图。欧拉图。二、中国邮递员问题二、中国邮递员问题（CPPchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。46解法：解法：若若本本身身就就是是欧欧拉拉图图，则则直直接接可可以以找找到到一一条条欧欧拉拉巡巡回回就就是是本问题的解。本问题的解。若若不不是是欧欧拉拉图图，必必定定有有偶偶数数个个奇奇度度数数结结点点，在在这这些些奇奇度度数数点点之之间间添添加加一一些些边边，使使之之变变成成欧欧拉拉图图，再再找找出出一一个个欧欧拉巡回。拉巡回。具具体体解解法法：Fleury算算法法+Edmonds最最小小对对集集算算法法47三、哈密尔顿图三、哈密尔顿图G=(V,E)为一连通无向图经过G中每点一次且正好一次的路径称为哈密尔顿路径哈密尔顿路径；经过G中每点一次且正好一次的回路称为哈密尔顿回路哈密尔顿回路；存在哈密尔顿回路的图称为哈密尔顿图。哈密尔顿图。四、旅行商问题四、旅行商问题（TSPTraveling Salesman Problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线？即：从驻地出发，经过每个城市恰好一次，最后返回驻地（最最小小哈哈密尔顿回路）密尔顿回路）对于n个节点的旅行商问题，n个节点的任意一个全排列都是问题的一个可能解（假设任意两个点之间都有边）。G个节点的全排列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路。TSP问题的解法属于NPNP完全问题完全问题，一般只研究其近似解法48最邻近算法最邻近算法(1)选取任意一个点作为起始点,找出与该点相关联的权重最小的边,形成一条初始路径.(2)找出与最新加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路.(3)重复(2)直到所有的结点都加入到路径中.(4)将起点和最后加入的结点之间的边加入到路径中,形成Hamilton回路.其他数值算法：其他数值算法：人工神经元方法，遗传算法等等495 5、二分图与匹配、二分图与匹配 定义定义1 1 设设X,Y 都是非空有限集都是非空有限集,且且XY=,E xy|xX,yY,称称G=(X,Y,E)为为二部图二部图.二部图可认为是有限简单无向图二部图可认为是有限简单无向图.如果如果X中的每个点都与中的每个点都与Y中的每个点邻接中的每个点邻接,则称则称G=(X,Y,E)为为完备二部图完备二部图.若若F：ER+,则称则称G=(X,Y,E,F)为为二部赋权图二部赋权图.二部赋权图的权矩阵一般记作二部赋权图的权矩阵一般记作A=(aij)|X|Y|,其中其中aij=F(xi yj).定义定义2 2 设设G=(X,Y,E)为二部图为二部图,且且M E.若若M中任意两条边中任意两条边在在G中均不邻接中均不邻接,则称则称M是是二部图二部图G的一个的一个匹配匹配.定义定义3 3 设设M是二部图是二部图G的一个匹配的一个匹配,如果如果G的每一个点都是的每一个点都是M中边的顶中边的顶点点,则称则称M是二部图是二部图G的的完美匹配完美匹配；如果如果G中没有另外的匹配中没有另外的匹配M0,使使|M0|M|,|,则称则称M是二部图是二部图G的的最大匹配最大匹配.在二部赋权图在二部赋权图G=(X,Y,E,F)中中,权数最大的最大匹配权数最大的最大匹配M称为称为二部赋权图二部赋权图G的的最佳匹配最佳匹配.显然显然,每个完美匹配都是最大匹配每个完美匹配都是最大匹配,反之不一定成立反之不一定成立.51工作安排问题之一工作安排问题之一 给给n个工作人员个工作人员x1,x2,xn安排安排n项工作项工作y1,y2,yn.n个工作人员中每个人能胜任一项或几项工作个工作人员中每个人能胜任一项或几项工作,但并但并不是所有不是所有工作人员都能从事任何一项工作工作人员都能从事任何一项工作.比如比如x1能做能做y1,y2工作工作,x2能能做做y2,y3,y4工作等工作等.这样便提出一个问题这样便提出一个问题,对所有的工作人员能不能都分配对所有的工作人员能不能都分配一件他所能胜任的工作？一件他所能胜任的工作？我们构造一个二部图我们构造一个二部图G=(X,Y,E),这里这里X=x1,x2,xn,Y=y1,y2,yn,并且当且仅当工作人员并且当且仅当工作人员xi胜任工作胜任工作yj时时,xi与与yj才相邻才相邻.于是于是,问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配.因为因为|X|=|Y|,所以完美匹配即为最大匹配所以完美匹配即为最大匹配.52 求二部图求二部图G=(X,Y,E)的最大匹配算法的最大匹配算法(匈牙利算法匈牙利算法,交替链算交替链算法法)迭代步骤迭代步骤:从从G的任意匹配的任意匹配M开始开始.将将X中中M的所有的所有非饱和点非饱和点都给以标号都给以标号0 0和标记和标记*,转向转向.M的非饱和点即非的非饱和点即非M的某条边的顶点的某条边的顶点.若若X中所有有标号的点都已去掉了标记中所有有标号的点都已去掉了标记*,则则M是是G的最大的最大匹配匹配.否则任取否则任取X中一个既有标号又有标记中一个既有标号又有标记*的点的点xi,去掉去掉xi的标的标记记*,转向转向.找出在找出在G中所有与中所有与xi邻接的点邻接的点yj,若所有这样的若所有这样的yj都已有标都已有标号号,则转向则转向,否则转向否则转向.53 对与对与xi邻接且尚未给标号的邻接且尚未给标号的yj都给定标号都给定标号i.若所有的若所有的yj 都是都是M的的饱和点饱和点,则转向则转向,否则逆向返回否则逆向返回.即由即由其中其中M的任一个非饱和点的任一个非饱和点yj 的标号的标号i 找到找到xi,再由再由xi 的标号的标号k 找到找到yk,最后由最后由yt 的标号的标号s找到标号为找到标号为0 0的的xs时结束时结束,获得获得M-增广路增广路xs ytxi yj,记记P=xs yt,xi yj ,重新记重新记M为为M P,转向转向.不必理会不必理会M-增广路增广路的定义的定义.M P=MP MP,是对称差是对称差.将将yj在在M中与之邻接的点中与之邻接的点xk,给以标号给以标号j 和标记和标记*,转向转向.54例例 求下图所示二部图求下图所示二部图G的最大匹配的最大匹配解解 取初始匹配取初始匹配M0=x2y2,x3y3,x5y5(上图粗线所示上图粗线所示).).给给X中中M0的两个非饱和点的两个非饱和点x1,x4都给以标号都给以标号0 0和标记和标记*(如如下图所示下图所示).).去掉去掉x1的标记的标记*,将与将与x1邻接的两个点邻接的两个点y2,y3都给以标号都给以标号1.1.因因为为y2,y3都是都是M0的两个饱和点的两个饱和点,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2,x3都给以相应的标号和标记都给以相应的标号和标记*(如下图所示如下图所示).55 去掉去掉x2的标记的标记*,将与将与x2邻接且尚未给标号的三个点邻接且尚未给标号的三个点y1,y4,y5都给以标号都给以标号2(如下图所示如下图所示).因为因为y1是是M0的非饱和点的非饱和点,所以顺着标号逆向返回依次得到所以顺着标号逆向返回依次得到x2,y2,直到直到x1为为0为止为止.于是得到于是得到M0的增广路的增广路x1 y2x2 y1,记记P=x1 y2,y2x2,x2 y1.取取M1=M0P=x1 y2,x2 y1,x3y3,x5y5,则则M1是比是比M多一边的匹配多一边的匹配(如下图所示如下图所示).56 再给再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*,然后去掉然后去掉x4的的标记标记*,将与将与x4邻接的两个点邻接的两个点y2,y3都给以标号都给以标号4.因为因为y2,y3都是都是M1的两个饱和点的两个饱和点,所以将它们在所以将它们在M1中邻接的两中邻接的两个点个点x1,x3都给以相应的标号和标记都给以相应的标号和标记*(如下图所示如下图所示).去掉去掉x1的标记的标记*,因为与因为与x1邻接的两个点邻接的两个点y2,y3都有标号都有标号4,所所以去掉以去掉x3的标记的标记*.而与而与x3邻接的两个点邻接的两个点y2,y3也都有标号也都有标号4,此时此时X中所有有标号中所有有标号的点都已去掉了标记的点都已去掉了标记*(如下图所示如下图所示),因此因此M1是是G的最大匹配的最大匹配.G不存在饱和不存在饱和X的每个点的匹配的每个点的匹配,当然也不存在完美匹配当然也不存在完美匹配.57工作安排问题之二工作安排问题之二 给给n个工作人员个工作人员x1,x2,xn安排安排n项工作项工作y1,y2,yn.如如果每个工作人员工作效率不同果每个工作人员工作效率不同,要求工作分配的同时考虑总效要求工作分配的同时考虑总效率最高率最高.我们构造一个二部赋权图我们构造一个二部赋权图G=(X,Y,E,F),这里这里X=x1,x2,xn,Y=y1,y2,yn,F(xiyj)为工作人员为工作人员xi胜任工作胜任工作yj时的工作效率时的工作效率.则问题转化为：求二部赋权图则问题转化为：求二部赋权图G的最佳匹配的最佳匹配.在求在求G的最佳匹配时的最佳匹配时,总可以假设总可以假设G为完备二部赋权图为完备二部赋权图.若若xi与与yj不相邻不相邻,可令可令F(xiyj)=0.同样地同样地,还可虚设点还可虚设点x或或y,使使|X|=|Y|.如此就将如此就将G转化为完备二部赋权图转化为完备二部赋权图,而且不会影响结果而且不会影响结果.58 定义定义 设设G=(X,Y,E,F)为完备的二部赋权图为完备的二部赋权图,若若L：X Y R+满足：满足：xX,yY,L(x)+L(y)F(xy),则称则称L为为G的一个的一个可行点标记可行点标记,记相应的生成子图为记相应的生成子图为GL=(X,Y,EL,F),),这里这里EL=xyE|L(x)+L(y)=F(xy).求完备二部赋权图求完备二部赋权图G=(X,Y,E,F)的最佳匹配算法迭代步骤：的最佳匹配算法迭代步骤：设设G=(X,Y,E,F)为完备的二部赋权图为完备的二部赋权图,L是其一个初始可是其一个初始可行点标记行点标记,通常取通常取 L(x)=max F(x y)|yY,xX,L(y)=0,yY.59M是是GL的一个匹配的一个匹配.若若X的每个点都是饱和的的每个点都是饱和的,则则M是最佳匹配是最佳匹配.否则取否则取M的非饱和点的非饱和点uX,令令S=u,T=,转向转向.记记NL(S)=v|uS,uvGL.若若NL(S)=T,则则GL没有完美匹配没有完美匹配,转向转向.否则转向否则转向.调整标记调整标记,计算计算aL=minL(x)+L(y)-F(xy)|xS,yYT.由此得新的可行点标记由此得新的可行点标记 令令L=H,GL=GH,重新给出重新给出GL的一个匹配的一个匹配M,转向转向.取取yNL(S)T,若若y是是M的饱和点的饱和点,转向转向.否则否则,转向转向.设设x yM,则令则令S=S x,T=T y,转向转向.在在GL中的中的u-y路是路是M-增广路增广路,设为设为P,并令并令M=M P,转向转向.606 6、网络流问题、网络流问题 定义定义1 1 设设G=(V,E)为有向图为有向图,在在V中指定一点称为中指定一点称为发点发点(记为记为vs),),和另一点称为和另一点称为收点收点(记为记为vt),),其余点叫做中间点其余点叫做中间点.对每一条边对每一条边vivjE,对应一个非负实数对应一个非负实数Cij,称为它的称为它的容量容量.这样的这样的G称为称为容量网容量网络络,简称简称网络网络,记作记作G=(V,E,C).定义定义2 2 网络网络G=(V,E,C)中任一条边中任一条边vivj有流量有流量fij,称集合称集合f=fij 为网络为网络G上的一个上的一个流流.满足下述条件的流满足下述条件的流f 称为称为可行流可行流：(限制条件限制条件)对每一边对每一边vivj,有有0fij Cij;(平衡条件平衡条件)对于中间点对于中间点vk有有fik=fkj ,即中间点即中间点vk的输入的输入量量=输出输出量量.61 如果如果f 是可行流是可行流,则对收、发点则对收、发点vt、vs有有fsi=fjt=Wf,即从即从vs点发出的物质总量点发出的物质总量=vt点输入的量点输入的量.Wf 称为网络流称为网络流f 的总流量的总流量.上述概念可以这样来理解上述概念可以这样来理解,如如G是一个运输网络是一个运输网络,则发点则发点vs表示表示发送站发送站,收点收点vt表示接收站表示接收站,中间点中间点vk表示中间转运站表示中间转运站,可行流可行流fij 表表示某条运输线上通过的运输量示某条运输线上通过的运输量,容量容量Cij表示某条运输线能承担的最表示某条运输线能承担的最大运输量大运输量,Wf 表示运输总量表示运输总量.可行流总是存在的可行流总是存在的.比如所有边的流量比如所有边的流量fij=0就是一个可行流就是一个可行流(称为零流称为零流).).62 所谓所谓最大流问题最大流问题就是在容量网络中就是在容量网络中,寻找流量最大的可行流寻找流量最大的可行流.实际问题中实际问题中,一个网络会出现下面两种情况：一个网络会出现下面两种情况：发点和收点都不止一个发点和收点都不止一个.解决的方法是再虚设一个发点解决的方法是再虚设一个发点vs和一个收点和一个收点vt,发点发点vs到所有到所有原发点边的容量都设为无穷大原发点边的容量都设为无穷大,所有原收点到收点所有原收点到收点vt 边的容量都边的容量都设为无穷大设为无穷大.网络中除了边有容量外网络中除了边有容量外,点也有容量点也有容量.解决的方法是将所有有容量的点分成两个点解决的方法是将所有有容量的点分成两个点,如点如点v有容量有容量Cv,将点将点v分成两个点分成两个点v和和v,令令C(vv)=Cv.63最小费用流问题最小费用流问题 这里我们要进一步探讨不仅要使网上的流达到最大这里我们要进一步探讨不仅要使网上的流达到最大,或者达或者达到要求的预定值到要求的预定值,而且还要使运输流的费用是最小的而且还要使运输流的费用是最小的,这就是最小这就是最小费用流问题费用流问题.最小费用流问题的一般提法：最小费用流问题的一般提法：已知网络已知网络G=(V,E,C),每条边每条边vivjE 除了已给容量除了已给容量Cij外外,还给还给出了单位流量的费用出了单位流量的费用bij(0).).所谓最小费用流问题就是求一个总流量已知的可行流所谓最小费用流问题就是求一个总流量已知的可行流f=f ij 使得总费用使得总费用最小最小.64 特别地特别地,当要求当要求f 为最大流时为最大流时,即为即为最小费用最大流问题最小费用最大流问题.设网络设网络G=(V,E,C),取初始可行流取初始可行流f 为零流为零流,求解最小费用流求解最小费用流问题的迭代步骤：问题的迭代步骤：构造有向赋权图构造有向赋权图Gf=(V,Ef,F),),对于任意的对于任意的vivjE,Ef,F 的的定义如下：定义如下：当当f ij=0时时,vivjEf,F(vivj)=bij;当当f ij=Cij时时,vjviEf,F(vjvi)=-bij;当当0f ijCij时时,vivjEf,F(vivj)=bij,vjviEf,F(vjvi)=-bij.然后然后转向转向.65 求出含有负权的有向赋权图求出含有负权的有向赋权图Gf=(V,Ef,F)中发点中发点vs到收点到收点vt的最短路的最短路 ,若最若最短路短路 存在转向存在转向;否则否则f是所求的最小费用最大是所求的最小费用最大流流,停止停止.增流增流.vivj与与 相同相同,vivj与与 相反相反.令令=min ij|vivj ,重新定义流重新定义流f=f ij 为为其它情况不变其它情况不变.如果如果Wf 大于或等于预定的流量值大于或等于预定的流量值,则适当减少则适当减少 值值,使使Wf 等等于预定的流量值于预定的流量值,那么那么f 是是所求的最小费用流所求的最小费用流,停止停止;否则转向否则转向.66 下面介绍求解有向赋权图下面介绍求解有向赋权图G=(V,E,F)中含有负权的最短路中含有负权的最短路的的Ford算法算法.设边的权设边的权vivj为为wij,v1到到vi的路长记为的路长记为 (i).Ford算法的迭代步骤：算法的迭代步骤：赋初值赋初值 (1)=0,(i)=,i=2,3,n.更新更新 (i),i=2,3,n.(i)=min (i),min (j)+wji|ji.若所有的若所有的 (i)都无变化都无变化,停止停止;否则转向否则转向.在算法的每一步在算法的每一步,(i)都是从都是从v1到到vi的最短路长度的上界的最短路长度的上界.若不若不存在负长回路存在负长回路,则从则从v1到到vi的最短路长度是的最短路长度是 (i)的下界的下界,经过经过n-1次次迭代后迭代后 (i)将保持不变将保持不变.若在第若在第n次迭代后次迭代后 (i)仍在变化时仍在变化时,说明说明存在负长回路存在负长回路.677 7、关键路径问题（拓扑排序）、关键路径问题（拓扑排序）一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装小至组装一台机床一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这些工序相互约束这些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一个工序才能开始一个工序才能开始.即它们之间存在即它们之间存在完成的先后次序关系完成的先后次序关系,一般认为这些关系是预知的一般认为这些关系是预知的,而且也能够而且也能够预计完成每个工序所需要的时间预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目成整个工程项目,影响工程进度的要害工序是哪几个？影响工程进度的要害工序是哪几个？68PT(Potentialtaskgraph)图图 在在PT(Potentialtaskgraph)图中图中,用结点表示工序用结点表示工序,如果工序如果工序i 完成之后工序完成之后工序j 才能启动才能启动,则图中有一条有向边则图中有一条有向边(i,j),),其长度其长度wi 表示工序表示工序i 所需的时间所需的时间.这种图必定不存在有向回路这种图必定不存在有向回路,否则某些工序将在自身完成之后否则某些工序将在自身完成之后才能开始才能开始,这显然不符合实际情况这显然不符合实际情况.在在PT图中增加两个虚拟结点图中增加两个虚拟结点v0和和vn,使所有仅为始点的结点都使所有仅为始点的结点都直接与直接与v0联结联结,v0为新增边的始点为新增边的始点,这些新增边的权都设为这些新增边的权都设为0;使所有使所有仅为终点的结点都直接与仅为终点的结点都直接与vn联结联结,vn为新增边的终点为新增边的终点.这样得到的这样得到的图图G仍然不存在有向回路仍然不存在有向回路.69 例例 一项工程由一项工程由1313道工序组成道工序组成,所需时间所需时间(单位：天单位：天)及先行工及先行工序如下表所示序如下表所示(P172).(P172).工序序号工序序号 A B C D E F G H IA B C D E F G H I所需时间所需时间 2 6 3 2 4 3 8 4 22 6 3 2 4 3 8 4 2先行工序先行工序 A A B C,D D D D G,H A A B C,D D D D G,H工序序号工序序号 J K L MJ K L M所需时间所需时间 3 8 5 63 8 5 6先行工序先行工序 G H,E J K G H,E J K 试问这项工程至少需要多少天才能完成试问这项工程至少需要多少天才能完成?那些工程不能延误那些工程不能延误?那些工程可以延误那些工程可以延误?最多可延误多少天最多可延误多少天?70 先作出该工程的先作出该工程的PT图图.由于除了工序由于除了工序A A外，均有先行工序外，均有先行工序,因因此不必虚设虚拟结点此不必虚设虚拟结点v0.A AB B2 22 2C C6 6D D3 3E E2 2F F2 2G G2 2H H2 2K K4 4N N3 3I I8 8J J8 84 44 42 2L L3 3M M8 85 56 6 在在PT图中图中,容易看出各工序先后完成的顺序及时间容易看出各工序先后完成的顺序及时间.虚拟结点虚拟结点71A AB B2 22 2C C6 6D D3 3E E2 2F F2 2G G2 2H H2 2K K4 4N N3 3I I8 8J J8 84 44 42 2L L3 3M M8 85 56 6 这项工程至少需这项工程至少需要多少天才能完成要多少天才能完成?就是要求就是要求A A到到N N的最长路的最长路,此路径称为此路径称为关键路径关键路径.那些工程不能延误那些工程不能延误?那些工程可以延误那些工程可以延误?最多可延误多少天最多可延误多少天?关键路径上的那些工程不能延误关键路径上的那些工程不能延误.72关键路径关键路径(最长路径最长路径)算法算法 定理定理 若有向图若有向图G中中不存在有向回路不存在有向回路,则可以将则可以将G 的结点重新编的结点重新编号为号为u1,u2,un,使得对任意的边使得对任意的边ui ujE(G),),都有都有ij.各工序最早启动时间算法步骤：各工序最早启动时间算法步骤：根据定理根据定理对结点重新编号为对结点重新编号为u1,u2,un.赋初值赋初值 (u1)=0.依次更新依次更新 (uj),),j=2,3,n.(uj)=max (ui)+)+(ui,uj)|)|uiujE(G).).结束结束.其中其中(uj)表示工序表示工序uj 最早启动时间最早启动时间,而而(un)即即(vn)是整个工程是整个工程完工所需的最短时间完工所需的最短时间.73A AB B2 22 2C C6 6D D3 3E E2 2F F2 2G G2 2H H2 2K K4 4N N3 3I I8 8J J8 84 44 42 2L L3 3M M8 85 56 6此例不必重此例不必重新编号，只新编号，只要按字母顺要按字母顺序即可序即可.(A)=0,(A)=0,(B)=(B)=(C)=2,(C)=2,(D)=8,(D)=8,(E)=(E)=max2+3,8+2=10,2+3,8+2=10,(F)=(F)=(G)=(G)=(H)=(H)=(D)+2=10,(D)+2=10,(I)=(I)=max (G)+8,(G)+8,(H)+4=18,(H)+4=18,(J)=(J)=(G)+8=18,(G)+8=18,(K)=(K)=max (E)+4,(E)+4,(H)+4=14,(H)+4=14,(L)=(L)=(J)+3=21,(J)+3=21,(M)=(M)=(K)+8=22,(K)+8=22,(N)=(N)=max (F)+3,(F)+3,(I)+2,(I)+2,(L)+5,(L)+5,(M)+6=28.(M)+6=28.关键路径关键路径?74通过以上计算表明：通过以上计算表明：这项工程至少需要这项工程至少需要2828天才能完成天才能完成.关键路径关键路径(最长路径最长路径):):ABDEKMNABDEKMNABDHKMNABDHKMN 工序工序A,B,D,E,H,K,MA,B,D,E,H,K,M不能延误不能延误,否则将影响工程的完成否则将影响工程的完成.但是对于不在关键路径上的工序但是对于不在关键路径上的工序,是否允许延误？如果允许是否允许延误？如果允许,最多能够延误多长时间呢？最多能够延误多长时间呢？各工序允许延误时间各工序允许延误时间t(uj)等于各工序最晚启动时间等于各工序最晚启动时间(uj)减去减去各工序最早启动时间各工序最早启动时间(uj).).即即 t(uj)=)=(uj)-)-(uj).).75最晚启动时间算法步骤最晚启动时间算法步骤(已知结点重新编号已知结点重新编号)：赋初值赋初值 (un)=)=(un).).更新更新 (uj),),j=n-1,n-2,1.(uj)=min (ui)-)-(ui,uj)|)|uiujE(G).).结束结束.顺便提一句顺便提一句,根据工序根据工序uj允许延误时间允许延误时间