数学建模图论模型.pptx

数学建模数学建模图论模型模型图论模型图论模型1.图论基本概念图论基本概念2.最短路径算法最短路径算法3.最小生成树算法最小生成树算法4.遍历性问题遍历性问题5.二分图与匹配二分图与匹配6.网络流问题网络流问题7.关键路径问题关键路径问题8.系统监控模型系统监控模型9.着色模型着色模型21、图论的基本概念、图论的基本概念问题问题1(1(哥尼斯堡七桥哥尼斯堡七桥问题问题):):能否从任一陆地出发通过每座桥恰好一次而回到出发点？能否从任一陆地出发通过每座桥恰好一次而回到出发点？3欧拉指出：欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地.4问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题问题):):十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？最后回到出发点？欧拉问题是欧拉问题是“边遍历边遍历”，哈密尔顿问题是，哈密尔顿问题是“点遍历点遍历”5问题问题3(3(四色问题四色问题):):对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这些这些工序相互约束工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一个工序才能开始一个工序才能开始.即它们之间存在完成的先后次序关系即它们之间存在完成的先后次序关系,一般认为一般认为这些关系是预知的这些关系是预知的,而且也能够预计完成每个工序所需要的时间而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是影响工程进度的要害工序是哪几个？哪几个？6图的定义图的定义 图论中的图论中的“图图”并不是通常意义下的几何图形或物体的形状图并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统的事物之间的联系的一个数学系统.定义定义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)图图8 对于一个图对于一个图G=(V,E),人们常用图形来表示它人们常用图形来表示它,称其为图解称其为图解.凡是有向边凡是有向边,在图解上都用箭头标明其方向在图解上都用箭头标明其方向.例如例如,设设V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4,则则G=(V,E)是一个有是一个有4个顶点和个顶点和6条边的图条边的图G的图解如下图所示的图解如下图所示.9 一个图会有许多外形不同的图解一个图会有许多外形不同的图解,下面两个图表示同一个图下面两个图表示同一个图G=(V,E)的图解的图解.这两个图互为这两个图互为同构图同构图,今后将今后将不计较这种外形上的差别不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图而用一个容易理解的、确定的图解去表示一个图.10 有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点,有一个公共端点的边称为有一个公共端点的边称为相邻边相邻边.边和它的端点称为边和它的端点称为互相关联互相关联.常用常用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)=111握手定理握手定理握手定理：握手定理：无向图中，所有结点的度数之和等于2m。右图：推论推论1：无向图中必有偶数个度数为奇数的结点。推论推论2：有向图中所有结点的出度之和等于入度之和。d(v1)=d(v3)=d(v4)=4,d(v2)=212我们今后只讨论有限简单图：我们今后只讨论有限简单图：(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表示树表示树.14常用的图常用的图给定图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；。18例例 过河问题过河问题问问题题：一摆渡人欲将一只狼、一头羊、一篮菜从河西渡过河到河东。由于船小，一次只能带一物过河，并且狼与羊，羊与菜不能独处，给出渡河方法。这里显然不能用一个节点表示一个物体。一个物体可能在河东，也可能在河西，也可能在船上，状态表示不清楚。另外，问题也可以分成几个小问题，如：问题是否能解？有几种不同的解法？最快的解决方案是什么？例例 过河问题过河问题解解：用四维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,A2A10,从图中易得到两条路：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,其中其中 22无向图无向图G的邻接矩阵的邻接矩阵A是一个对称矩阵是一个对称矩阵.权矩阵权矩阵 一个一个n阶赋权图阶赋权图G=(V,E,F)的权矩阵的权矩阵A=(aij)nn,其中其中 有限简单图基本上可用权矩阵来有限简单图基本上可用权矩阵来表示表示.23无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵.24 关联矩阵：一个有关联矩阵：一个有m条边的条边的n阶有向图阶有向图G的关联矩阵的关联矩阵A=(aij)nm,其中其中 若若vi是是ej的始点的始点;若若vi是是ej的终点的终点;若若vi与与ej不关联不关联.有向图的关联矩阵每列的元素中有且仅有一个有向图的关联矩阵每列的元素中有且仅有一个1,1,有且仅有一个有且仅有一个-1.1.25 一个有一个有m条边的条边的n阶无向图阶无向图G的关联矩阵的关联矩阵A=(aij)nm,其中其中 若若vi与与ej关联关联;若若vi与与ej不关联不关联.无向图的关联矩阵每列的元素中有且仅有两个无向图的关联矩阵每列的元素中有且仅有两个1.1.262 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算法算法.这两种算法均适用于有向非负赋权图这两种算法均适用于有向非负赋权图.下面分别介绍两种算法的基本过程下面分别介绍两种算法的基本过程.28Dijkstra算法算法指标指标（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的指标的指标,则则29Dijkstra算法（求算法（求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)为图的权矩阵）为图的权矩阵）30改进改进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)为图的权矩阵）为图的权矩阵）31例例 求下图中求下图中A A点到其他点的最短路点到其他点的最短路.32Floyd算法（求任意两点的最短路径）算法（求任意两点的最短路径）设设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得到得到.例例 求下图中任意两点间的最短路求下图中任意两点间的最短路.34例例 设备更新问题设备更新问题 某企业每年年初某企业每年年初,都要作出决定都要作出决定,如果继续使用旧设备如果继续使用旧设备,要付维修费；若购买一台新设备要付维修费；若购买一台新设备,要付购买费要付购买费.试制试制定一个定一个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的最短路问题的最短路问题.36 由实际问题可知由实际问题可知,设备使用三年后应当更新设备使用三年后应当更新,因此删除该图中因此删除该图中v1到到v5,v1到到v6,v2到到v6的连线；又设备使用一年的连线；又设备使用一年后就更新则不划算后就更新则不划算,因此再删除该图中因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6.而这两条路都是而这两条路都是v1到到v6的最短路的最短路.373 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)39求最小生成树求最小生成树40Prim算法算法 把结点分成两个集合，已加入树中的把结点分成两个集合，已加入树中的(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条边就是需要求出的条边就是需要求出的最小生成树的边。最小生成树的边。41例例 选址问题选址问题 现准备现准备在在n 个个居民点居民点v1,v2,vn中设置一银行中设置一银行.问设在哪个点问设在哪个点,可使最大服务距离最小可使最大服务距离最小?若设置两个银行若设置两个银行,问问设在哪两个点设在哪两个点?模型假设模型假设 假设各假设各个个居民点都有条件设置银行居民点都有条件设置银行,并有路相连并有路相连,且路长已知且路长已知.模型建立与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民点居民点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.设置一个银行设置一个银行,银行设银行设在在vi 点点的最大服务距离为的最大服务距离为求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在vk 点点,可使最大服务距离最小可使最大服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最大服务距离最小使最大服务距离最小.记记则则s,t 满足：满足：进一步进一步,若设置多个银行呢？若设置多个银行呢？434、遍历性问题、遍历性问题一、欧拉图一、欧拉图G=(V,E)为一连通无向图经过G中每条边至少一次的回路称为巡回巡回；经过G中每条边正好一次的巡回称为欧拉巡回欧拉巡回；存在欧拉巡回的图称为欧拉图。欧拉图。二、中国邮递员问题二、中国邮递员问题（CPPchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。44解法：解法：若本身就是欧拉图，则直接可以找到一条欧拉巡回就是本问题的解。若本身就是欧拉图，则直接可以找到一条欧拉巡回就是本问题的解。若若不不是是欧欧拉拉图图，必必定定有有偶偶数数个个奇奇度度数数结结点点，在在这这些些奇奇度度数数点点之之间间添添加加一一些些边边，使使之之变变成成欧欧拉拉图图，再找出一个欧拉巡回。再找出一个欧拉巡回。具体解法：具体解法：Fleury算法算法+Edmonds最小对集算法最小对集算法45三、哈密尔顿图三、哈密尔顿图G=(V,E)为一连通无向图经过G中每点一次且正好一次的路径称为哈密尔顿路径哈密尔顿路径；经过G中每点一次且正好一次的回路称为哈密尔顿回路哈密尔顿回路；存在哈密尔顿回路的图称为哈密尔顿图。哈密尔顿图。四、旅行商问题（四、旅行商问题（TSPTraveling Salesman Problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线？即：从驻地出发，经过每个城市恰好一次，最后返回驻地（最小哈密尔顿回路）（最小哈密尔顿回路）对于n个节点的旅行商问题，n个节点的任意一个全排列都是问题的一个可能解（假设任意两个点之间都有边）。G个节点的全排列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路。TSP问题的解法属于NPNP完全问题完全问题，一般只研究其近似解法46最邻近算法最邻近算法(1)选取任意一个点作为起始点,找出与该点相关联的权重最小的边,形成一条初始路径.(2)找出与最新加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路.(3)重复(2)直到所有的结点都加入到路径中.(4)将起点和最后加入的结点之间的边加入到路径中,形成Hamilton回路.其他数值算法：其他数值算法：人工神经元方法，遗传算法等等475 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的的最佳匹配最佳匹配.显然显然,每个完美匹配都是最大匹配每个完美匹配都是最大匹配,反之不一定成立反之不一定成立.49工作安排问题之一工作安排问题之一 给给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|,所以完美匹配即为最大匹配所以完美匹配即为最大匹配.50 求二部图求二部图G=(X,Y,E)的最大匹配算法的最大匹配算法(匈牙利算法匈牙利算法,交替链算法交替链算法)迭代步骤迭代步骤:从从G的任意匹配的任意匹配M开始开始.将将X中中M的所有非饱和点都给以标号的所有非饱和点都给以标号0 0和标记和标记*,转向转向.M的非饱和点即非的非饱和点即非M的某条边的顶点的某条边的顶点.若若X中所有有标号的点都已去掉了标记中所有有标号的点都已去掉了标记*,则则M是是G的最大匹配的最大匹配.否则任取否则任取X中一个既有标号又有标记中一个既有标号又有标记*的的点点xi,去掉去掉xi的标记的标记*,转向转向.找出在找出在G中所有与中所有与xi邻接的点邻接的点yj,若所有这样的若所有这样的yj都已有标号都已有标号,则转向则转向,否则转向否则转向.51 对与对与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 和标记和标记*,转向转向.52例例 求下图所示二部图求下图所示二部图G的最大匹配的最大匹配解解 取初始匹配取初始匹配M0=x2y2,x3y3,x5y5(上图粗线所示上图粗线所示).).给给X中中M0的两个非饱和点的两个非饱和点x1,x4都给以标号都给以标号0 0和标记和标记*(如下图所示如下图所示).).去掉去掉x1的标记的标记*,将与将与x1邻接的两个点邻接的两个点y2,y3都给以标号都给以标号1.1.因为因为y2,y3都是都是M0的两个饱和点的两个饱和点,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2,x3都给以相应的标号和标记都给以相应的标号和标记*(如下图所示如下图所示).53 去掉去掉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多一边的匹配多一边的匹配(如下图所示如下图所示).54 再给再给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的每个点的匹配的每个点的匹配,当然也不存在完美匹配当然也不存在完美匹配.55工作安排问题之二工作安排问题之二 给给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转化为完备二部赋权图转化为完备二部赋权图,而且不会影响结果而且不会影响结果.56 定义定义 设设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.57M是是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,转向转向.586 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的输入的输入量量=输出输出量量.59 如果如果f 是可行流是可行流,则对收、发点则对收、发点vt、vs有有fsi=fjt=Wf,即从即从vs点发出的物质总量点发出的物质总量=vt点输入的量点输入的量.Wf 称为网络流称为网络流f 的总流量的总流量.上述概念可以这样来理解上述概念可以这样来理解,如如G是一个运输网络是一个运