《数学建模图论模型.ppt》由会员分享，可在线阅读，更多相关《数学建模图论模型.ppt（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模图论模型数学建模图论模型1.图论基本概念图论基本概念2.最短路径算法最短路径算法3.最小生成树算法最小生成树算法4.遍历性问题遍历性问题5.二分图与匹配二分图与匹配6.网络流问题网络流问题7.关键路径问题关键路径问题8.系统监控模型系统监控模型9.着色模型着色模型数学建模图论模型数学建模图论模型问题问题1(1(哥尼斯堡七桥哥尼斯堡七桥问题问题):):能否从任一陆地出发通过每座桥恰好一次而能否从任一陆地出发通过每座桥恰好一次而回到出发点？回到出发点？欧拉指出：欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回
2、到出发地陆地出发，必能通过每座桥恰好一次而回到出发地.问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题问题):):十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，个城市，能否从某个城市出发在十二面体上依次经过每个能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？欧拉问题是欧拉问题是“边遍历边遍历”，哈密尔顿问题是，哈密尔顿问题是“点遍历点遍历”问题问题3(3(四色问题四色问题):):对任何一张地图进行着色，两个共同边界的国家染不同的颜对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了色，则只
3、需要四种颜色就够了.问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装小至组装一台机床一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这些工序相互约束这些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一个工序才能开始一个工序才能开始.即它们之间存在即它们之间存在完成的先后次序关系完成的先后次序关系,一般认为这些关系是预知的一般认为这些关系是预知的,而且也能够而且也能够预计完成每个工序所需要的时间预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能
4、够完这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目成整个工程项目,影响工程进度的要害工序是哪几个？影响工程进度的要害工序是哪几个？数学建模图论模型 图论中的图论中的“图图”并不是通常意义下的几何图形或物体的形并不是通常意义下的几何图形或物体的形状图状图,而是以一种抽象的形式来表达一些确定的事物之间的联而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统系的一个数学系统.定义定义1一个有序二元组一个有序二元组(V,E)称为一个称为一个图图,记为记为G=(V,E),其中其中 V称为称为G的顶点集的顶点集,V,其元素称为其元素称为顶点顶点或或结点结点,简称简称点点;E
5、称为称为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;
6、E=e1,e2,em(ek=vivj),|E|=m.称点称点vi,vj为边为边vivj的的端点端点.在有向图中在有向图中,称点称点vi,vj分别为边分别为边vivj的的始点始点和和终点终点.该图称为该图称为(n,m)图图 对于一个图对于一个图G=(V,E),人们常用图形来表示它人们常用图形来表示它,称称其为其为图解图解.凡是有向边凡是有向边,在图解上都用箭头标明其方向在图解上都用箭头标明其方向.例如例如,设设V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4,则则G=(V,E)是一个有是一个有4个顶点和个顶点和6条边的图条边的图,G的图解如下图所示的图解
7、如下图所示.一个图会有许多外形不同的图解一个图会有许多外形不同的图解,下面两个图表示同一个图下面两个图表示同一个图G=(V,E)的图解的图解.这两个图互为这两个图互为同构图同构图,今后将不计较这种外形今后将不计较这种外形上的差别上的差别,而用一个容易理解的、确定的图解去表示一个图而用一个容易理解的、确定的图解去表示一个图.有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点,有一个公共端点的边称为有一个公共端点的边称为相相邻边邻边.边和它的端点称为边和它的端点称为互相关联互相关联.常用常用d(v)表示图表示图G中与顶点中与顶点v关联关联的边的数目的边的数目,d(v)称为顶点称为顶点v的的度
8、数度数.对于有向图对于有向图,还有还有出度出度和和入度入度之之分分.用用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)=1握手定理握手定理：无向图中，所有结点的度数之和等于2m。右图：推论1：无向图中必有偶数个度数为奇数的结点。推论2：有向图中所有结点的出度之和等于入度之和。d(v1)=d(v3)=d(v4)=4,d(v2)=2数学建模图论模型 (1)(1)顶点个
9、数是有限的顶点个数是有限的;(2)(2)任意一条边有且只有两个不同的点与它相互关联任意一条边有且只有两个不同的点与它相互关联;(3)(3)若是无向图若是无向图,则任意两个顶点最多只有一条边与之相则任意两个顶点最多只有一条边与之相联结联结;(4)(4)若是有向图若是有向图,则任意两个顶点最多只有两条边与之相则任意两个顶点最多只有两条边与之相联结联结.当两个顶点有两条边与之相联结时，这两条边的方向当两个顶点有两条边与之相联结时，这两条边的方向相反相反.如果某个有限图不满足如果某个有限图不满足(2)(3)(4),(2)(3)(4),可在某条边上增设顶点可在某条边上增设顶点使之满足使之满足.定义定义2
10、若将图若将图G的每一条边的每一条边e都对应一个实数都对应一个实数F(e),则称则称F(e)为该边的为该边的权权,并称图并称图G为为赋权图赋权图(网络网络),记为记为G=(V,E,F).定义定义3任意两点均有通路的图称为任意两点均有通路的图称为连通图连通图.定义定义4连通而无圈的图称为连通而无圈的图称为树树,常用常用T表示树表示树.数学建模图论模型给定图G=和 G=是两个图，如果有 V V 和 E E,则称图G是图 G 的子子图图。若V=V 称图G是图 G 的生成生成子子图图；若将图G的每一条边e都对应一个实数F(e)，则称F(e)为该边的权，并称图G为赋赋权权图图(网网络络),记为G=。任意两
11、点均有通路的图称为连连通通图图。连通而无圈的图称为树树，常用T=表示树。若图G是图 G 的生成子图，且G又是一棵树，则称G是图G 的生成生成树树。数学建模图论模型问问题题：任何6个人的聚会，其中总会有3个互相认识或3人互相不认识。图图论论模模型型：用红、蓝两种颜色对6个顶点的完全图K6的边边进行任意着色，则不论如何着色必然都存在一个红色的K3或一个蓝色的K3。对应关系：每个人即为一个结点；人与人之间的关系即为一条边数学建模图论模型图论证明：用红、蓝两种颜色对K6的边边进行着色，K6的任意一个顶点均有5条边与之相连接，这5条边必有3条边的颜色是相同的，不妨设为蓝色（如图）与这3条边相关联的另外3
12、个节点之间的3条边，若都为红色，则形成红红色的色的K3；若另外3个节点之间的3条边有一条为蓝色，则与上面的蓝色边形成蓝蓝色的色的K3；因此必然存在一个红色的K3或一个蓝色的K3。数学建模图论模型Ramsey数：R（3,3）=6；R（3,4）=9；。数学建模图论模型问题：一摆渡人欲将一只狼、一头羊、一篮菜从河西渡过河到河东。由于船小，一次只能带一物过河，并且狼与羊，羊与菜不能独处，给出渡河方法。这里显然不能用一个节点表示一个物体。一个物体可能在河东，也可能在河西，也可能在船上，状态表示不清楚。另外，问题也可以分成几个小问题，如：问题是否能解？有几种不同的解法？最快的解决方案是什么？数学建模图论模
13、型解解：用四维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)(
14、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之间有
15、多少条不同的路径？最快的解决方案是什么？即：A1到A10最短路径有哪些？数学建模图论模数学建模图论模型型 邻接矩阵：邻接矩阵：邻接矩阵表示了点与点之间的邻接关邻接矩阵表示了点与点之间的邻接关系系.一个一个n阶图阶图G的邻接矩阵的邻接矩阵A=(aij)nn,其中其中 无向图无向图G的邻接矩阵的邻接矩阵A是一个对称矩阵是一个对称矩阵.权矩阵权矩阵 一个一个n阶赋权图阶赋权图G=(V,E,F)的权矩阵的权矩阵A=(aij)nn,其中其中 有限简单图基本有限简单图基本上可用权矩阵来上可用权矩阵来表示表示.无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵.关联矩阵：关联矩阵：一个有一个有m条
16、边的条边的n阶有向图阶有向图G的关联的关联矩阵矩阵A=(aij)nm,其中其中 若若vi是是ej的始点的始点;若若vi是是ej的终点的终点;若若vi与与ej不关联不关联.有向图的关联矩阵每列的元素中有且仅有一个有向图的关联矩阵每列的元素中有且仅有一个1,1,有且仅有且仅有一个有一个-1.1.一个有一个有m条边的条边的n阶无向图阶无向图G的关联矩阵的关联矩阵A=(aij)nm,其中其中 若若vi与与ej关联关联;若若vi与与ej不关联不关联.无向图的关联矩阵每列的元素中有且仅有两个无向图的关联矩阵每列的元素中有且仅有两个1.1.数学建模图论模型 定义定义1 设设P(u,v)是赋权图是赋权图G=(
17、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的最短路的最短路.即：最短路是一条路，
18、且最短路的任一段也是最短路即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般用中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法算法.这两种算法均适用于有向非负赋权图这两种算法均适用于有向非负赋权图.下面分别介绍两种算法的基本过程下面分别介绍两种算法的基本过程.数学建模图论模型指标（a为为起点）起点）设设T为为V的子集，的子集，P=V-T且且aT，对对所有所有tT，设设l(t)表示从表示从a到到t的所有通路中距离最短的一条的的所有
19、通路中距离最短的一条的长长度，度，且且这这条路径中不包含条路径中不包含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到到
20、p的最短路径的最短路径,这这条路径条路径仅仅有有P中的中的点构成点构成,(2)对对于每一点于每一点t,它关于它关于P的指的指标为标为l(t),令令x为为最小指最小指标标所在的点所在的点,即即:(3)令令P=PUx,T=T-x,l(t)表示表示T中中结结点点t关于关于P的指的指标标,则则数学建模图论模型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按照公式按照公式
21、l(t)=minl(t),l(x)+w(x,t),计算计算T中每一个结点中每一个结点t关于关于P的指标的指标.4、P代替代替P,T代替代替T,重复步骤重复步骤2,3（其中：其中：w(x,y)为图的权矩阵）为图的权矩阵）数学建模图论模型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)
22、,计算计算T中每一个结点中每一个结点t关于关于P的指标的指标.若若l(x)+w(x,t)l(t),pro(t)=x;4、P代替代替P,T代替代替T,重复步骤重复步骤2,3（其中：其中：w(x,y)为图的权矩阵）为图的权矩阵）数学建模图论模型数学建模图论模型 设设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+
23、dk jdij,则令则令dij=dik+dkj,rij=k,转向转向;终止判断终止判断.若若k=n终止终止;否则令否则令k=k+1,转向转向.最短路线可由最短路线可由rij得到得到.数学建模图论模型数学建模图论模型 某企业每年年初某企业每年年初,都要作出决定都要作出决定,如果继续使用旧设备如果继续使用旧设备,要付要付维修费；若购买一台新设备维修费；若购买一台新设备,要付购买费要付购买费.试制定一个试制定一个5 5年更新计年更新计划划,使总支出最少使总支出最少.已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11,12,12,13.11,11,12,12,13.使使用不同时
24、间设备所需的维修费分别为用不同时间设备所需的维修费分别为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年年初报废年年初报废.这样上述设备更新问题就变为：在有向赋权图这样上述设备更新问题就变为：在有向赋权图
25、G=(V,E,F)(图解如下图解如下)中求中求v1到到v6的最短路问题的最短路问题.由实际问题可知由实际问题可知,设备使用三年后应当更新设备使用三年后应当更新,因此删因此删除该图中除该图中v1到到v5,v1到到v6,v2到到v6的连线；又设备使用一年的连线；又设备使用一年后就更新则不划算后就更新则不划算,因此再删除该图中因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6.而这两条路都是而这两条路都是v1到到v6的最短路的最短路.数学建模图论模型 由树的定义不
26、难知道由树的定义不难知道,任意一个连通的任意一个连通的(n,m)图图G适当去掉适当去掉m-n+1条边后条边后,都可以变成树都可以变成树,这棵树称为图这棵树称为图G的的生成树生成树.设设T是图是图G的一棵生成树的一棵生成树,用用F(T)表示树表示树T中所有边的权数之和中所有边的权数之和,F(T)称为称为树树T的权的权.一个连通图一个连通图G的生成树一般不止一棵的生成树一般不止一棵,图图G的所有生成树中权的所有生成树中权数最小的生成树称为图数最小的生成树称为图G的的最小生成树最小生成树-Minimum-costSpanningTree(MST).求最小生成树问题有很广泛的实际应用求最小生成树问题有
27、很广泛的实际应用.例如例如,把把n个乡镇用高个乡镇用高压电缆连接起来建立一个电网压电缆连接起来建立一个电网,使所用的电缆长度之和最短使所用的电缆长度之和最短,即费即费用最小用最小,就是一个求最小生成树问题就是一个求最小生成树问题.数学建模图论模型 从未选入树中的边中选取权重最小的且不构成回路从未选入树中的边中选取权重最小的且不构成回路的边加入到树中的边加入到树中.（判断回路比较麻烦）（判断回路比较麻烦）算法过程：算法过程：1.将各边按权值从小到大进行排序将各边按权值从小到大进行排序2.找出权值最小且找出权值最小且不与已加入最小生成树集合的边构成回路不与已加入最小生成树集合的边构成回路的的边。若
28、符合条件，则加入最小生成树的集合中。不符合条件则边。若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。继续遍历图，寻找下一个最小权值的边。3.递归重复步骤递归重复步骤1，直到找出，直到找出n-1条边为止，得到最小生成树。条边为止，得到最小生成树。时间复杂度时间复杂度只和边有关，可以证明其时间复杂度为只和边有关，可以证明其时间复杂度为O(mlogm)数学建模图论模型数学建模图论模型 把结点分成两个集合，已加入树中的把结点分成两个集合，已加入树中的(P P)和未加入树中的和未加入树中的(Q Q)，然后每次选择一个点在，然后每次选择一个点在P P中一个点在中一个点
29、在Q Q中的权重最小的边，加入中的权重最小的边，加入树中，并把相应点加入树中，并把相应点加入P P中。中。类似地类似地,可定义连通图可定义连通图G 的最大生成树的最大生成树.算法算法过过程：程：1：初始化：任取一个：初始化：任取一个节节点点u加入生成加入生成树树,P=u0,Q=V-u0,生成生成树树的的边边集集TE=。2：在所有：在所有uP,vQ的的边边(u,v)（称称为为可可选边选边集集）中，找一条）中，找一条权权重最小的重最小的边边(u1,v1)，将此，将此边边加加进进集合集合TE中，并将中，并将v加入加入P中。同中。同时对时对与与v关关联联的的边边，若，若另一个端点已另一个端点已经经在在
30、P中，中，则则从可从可选边选边集中集中删删除，否除，否则则加入可加入可选边选边集。集。3：如果：如果P=V，则则算法算法结结束；否束；否则则重复步重复步骤骤2。我我们们可以算出当可以算出当U=V时时，步，步骤骤2共共执执行了行了n1次，次，TE中也增加了中也增加了n1条条边边，这这n1条条边边就是需要求出的最小生成就是需要求出的最小生成树树的的边边。数学建模图论模型 现准备现准备在在n 个个居民点居民点v1,v2,vn中设置一银行中设置一银行.问问设在哪个点设在哪个点,可使最大服务距离最小可使最大服务距离最小?若设置两个银行若设置两个银行,问设在哪两个点问设在哪两个点?模型假设模型假设 假设各
31、假设各个个居民点都有条件设置银行居民点都有条件设置银行,并并有路相连有路相连,且路长已知且路长已知.模型建立与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民居民点点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.设置一个银行设置一个银行,银行设银行设在在vi 点点的最大服务距离为的最大服务距离为求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在vk 点点,可使最大服务距离最小可使最大服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最大服务距离最小使最大服务距离最小.记记则则s,t 满足：满足：进一步
32、进一步,若设置多个银行呢？若设置多个银行呢？数学建模图论模型一、欧拉图G=(V,E)为一连通无向图经过G中每条边至少一次的回路称为巡回；经过G中每条边正好一次的巡回称为欧拉巡回；存在欧拉巡回的图称为欧拉图。二、中国邮递员问题（CPPchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。解法：若若本本身身就就是是欧欧拉拉图图，则则直直接接可可以以找找到到一一条条欧欧拉拉巡巡回回就就是是本问题的解。本问题
33、的解。若若不不是是欧欧拉拉图图，必必定定有有偶偶数数个个奇奇度度数数结结点点，在在这这些些奇奇度度数数点点之之间间添添加加一一些些边边，使使之之变变成成欧欧拉拉图图，再再找找出出一一个个欧欧拉巡回。拉巡回。具体解法：Fleury算法+Edmonds最小对集算法三、哈密尔顿图G=(V,E)为一连通无向图经过G中每点一次且正好一次的路径称为哈密尔顿路径；经过G中每点一次且正好一次的回路称为哈密尔顿回路；存在哈密尔顿回路的图称为哈密尔顿图。四、旅行商问题（TSPTraveling Salesman Problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线？即：从驻地出
34、发，经过每个城市恰好一次，最后返回驻地（最小哈密尔顿回路）对于n个节点的旅行商问题，n个节点的任意一个全排列都是问题的一个可能解（假设任意两个点之间都有边）。G个节点的全排列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路。TSP问题的解法属于NPNP完全问题，一般只研究其近似解法最邻近算法(1)选取任意一个点作为起始点,找出与该点相关联的权重最小的边,形成一条初始路径.(2)找出与最新加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路.(3)重复(2)直到所有的结点都加入到路径中.(4)将起点和最后加入的结点之间的边加入到路径中,形成Hamilton
35、回路.其他数值算法：人工神经元方法，遗传算法等等数学建模图论模型 定义定义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)
36、为二部图为二部图,且且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的的最佳匹配最佳匹配.显然显然,每个完美匹配都是
37、最大匹配每个完美匹配都是最大匹配,反之不一定成立反之不一定成立.数学建模图论模型 给给n个工作人员个工作人员x1,x2,xn安排安排n项工作项工作y1,y2,yn.n个工作人员中每个人能胜任一项或几项工作个工作人员中每个人能胜任一项或几项工作,但并但并不是所有不是所有工作人员都能从事任何一项工作工作人员都能从事任何一项工作.比如比如x1能做能做y1,y2工作工作,x2能能做做y2,y3,y4工作等工作等.这样便提出一个问题这样便提出一个问题,对所有的工作人员能不能都分配对所有的工作人员能不能都分配一件他所能胜任的工作？一件他所能胜任的工作？我们构造一个二部图我们构造一个二部图G=(X,Y,E)
38、,这里这里X=x1,x2,xn,Y=y1,y2,yn,并且当且仅当工作人员并且当且仅当工作人员xi胜任工作胜任工作yj时时,xi与与yj才相邻才相邻.于是于是,问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配.因为因为|X|=|Y|,所以完美匹配即为最大匹配所以完美匹配即为最大匹配.数学建模图论模型 从从G的任意匹配的任意匹配M开始开始.将将X中中M的所有的所有非饱和点非饱和点都给以标号都给以标号0 0和标记和标记*,转向转向.M的非饱和点即非的非饱和点即非M的某条边的顶点的某条边的顶点.若若X中所有有标号的点都已去掉了标记中所有有标号的点都已去掉了标记*,则则M是是G的最大的
39、最大匹配匹配.否则任取否则任取X中一个既有标号又有标记中一个既有标号又有标记*的点的点xi,去掉去掉xi的标的标记记*,转向转向.找出在找出在G中所有与中所有与xi邻接的点邻接的点yj,若所有这样的若所有这样的yj都已有标都已有标号号,则转向则转向,否则转向否则转向.对与对与xi邻接且尚未给标号的邻接且尚未给标号的yj都给定标号都给定标号i.若所有的若所有的yj 都是都是M的的饱和点饱和点,则转向则转向,否则逆向返回否则逆向返回.即由即由其中其中M的任一个非饱和点的任一个非饱和点yj 的标号的标号i 找到找到xi,再由再由xi 的标号的标号k 找到找到yk,最后由最后由yt 的标号的标号s找到
40、标号为找到标号为0 0的的xs时结束时结束,获得获得M-增广路增广路xs ytxi yj,记记P=xs yt,xi yj ,重新记重新记M为为M P,转向转向.不必理会不必理会M-增广路增广路的定义的定义.M P=MP MP,是对称差是对称差.将将yj在在M中与之邻接的点中与之邻接的点xk,给以标号给以标号j 和标记和标记*,转向转向.数学建模图论模型解解 取初始匹配取初始匹配M0=x2y2,x3y3,x5y5(上图粗线所示上图粗线所示).).给给X中中M0的两个非饱和点的两个非饱和点x1,x4都给以标号都给以标号0 0和标记和标记*(如如下图所示下图所示).).去掉去掉x1的标记的标记*,将
41、与将与x1邻接的两个点邻接的两个点y2,y3都给以标号都给以标号1.1.因因为为y2,y3都是都是M0的两个饱和点的两个饱和点,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2,x3都给以相应的标号和标记都给以相应的标号和标记*(如下图所示如下图所示).去掉去掉x2的标记的标记*,将与将与x2邻接且尚未给标号的三个点邻接且尚未给标号的三个点y1,y4,y5都给以标号都给以标号2(如下图所示如下图所示).因为因为y1是是M0的非饱和点的非饱和点,所以顺着标号逆向返回依次得到所以顺着标号逆向返回依次得到x2,y2,直到直到x1为为0为止为止.于是得到于是得到M0的增广路的增广路x1 y
42、2x2 y1,记记P=x1 y2,y2x2,x2 y1.取取M1=M0P=x1 y2,x2 y1,x3y3,x5y5,则则M1是比是比M多一边的匹配多一边的匹配(如下图所示如下图所示).再给再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*,然后去掉然后去掉x4的的标记标记*,将与将与x4邻接的两个点邻接的两个点y2,y3都给以标号都给以标号4.因为因为y2,y3都是都是M1的两个饱和点的两个饱和点,所以将它们在所以将它们在M1中邻接的两中邻接的两个点个点x1,x3都给以相应的标号和标记都给以相应的标号和标记*(如下图所示如下图所示).去掉去掉x1的标记的标记*,因为与因为
43、与x1邻接的两个点邻接的两个点y2,y3都有标号都有标号4,所所以去掉以去掉x3的标记的标记*.而与而与x3邻接的两个点邻接的两个点y2,y3也都有标号也都有标号4,此时此时X中所有有标号中所有有标号的点都已去掉了标记的点都已去掉了标记*(如下图所示如下图所示),因此因此M1是是G的最大匹配的最大匹配.G不存在饱和不存在饱和X的每个点的匹配的每个点的匹配,当然也不存在完美匹配当然也不存在完美匹配.数学建模图论模型 给给n个工作人员个工作人员x1,x2,xn安排安排n项工作项工作y1,y2,yn.如如果每个工作人员工作效率不同果每个工作人员工作效率不同,要求工作分配的同时考虑总效要求工作分配的同
44、时考虑总效率最高率最高.我们构造一个二部赋权图我们构造一个二部赋权图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转化为完备二部赋权图转化为完备二部赋权图,而且不会影响结果而且不
45、会影响结果.定义定义 设设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,x
46、X,L(y)=0,yY.M是是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的饱和点的饱和点,转向转向.否则否则,转向转向.设
47、设x yM,则令则令S=S x,T=T y,转向转向.在在GL中的中的u-y路是路是M-增广路增广路,设为设为P,并令并令M=M P,转向转向.数学建模图论模型 定义定义1 1 设设G=(V,E)为有向图为有向图,在在V中指定一点称为中指定一点称为发点发点(记为记为vs),),和另一点称为和另一点称为收点收点(记为记为vt),),其余点叫做中间点其余点叫做中间点.对每一条边对每一条边vivjE,对应一个非负实数对应一个非负实数Cij,称为它的称为它的容量容量.这样的这样的G称为称为容量网容量网络络,简称简称网络网络,记作记作G=(V,E,C).定义定义2 2 网络网络G=(V,E,C)中任一条
48、边中任一条边vivj有流量有流量fij,称集合称集合f=fij 为网络为网络G上的一个上的一个流流.满足下述条件的流满足下述条件的流f 称为称为可行流可行流：(限制条件限制条件)对每一边对每一边vivj,有有0fij Cij;(平衡条件平衡条件)对于中间点对于中间点vk有有fik=fkj ,即中间点即中间点vk的输入的输入量量=输出输出量量.如果如果f 是可行流是可行流,则对收、发点则对收、发点vt、vs有有fsi=fjt=Wf,即从即从vs点发出的物质总量点发出的物质总量=vt点输入的量点输入的量.Wf 称为网络流称为网络流f 的总流量的总流量.上述概念可以这样来理解上述概念可以这样来理解,
49、如如G是一个运输网络是一个运输网络,则发点则发点vs表示表示发送站发送站,收点收点vt表示接收站表示接收站,中间点中间点vk表示中间转运站表示中间转运站,可行流可行流fij 表表示某条运输线上通过的运输量示某条运输线上通过的运输量,容量容量Cij表示某条运输线能承担的最表示某条运输线能承担的最大运输量大运输量,Wf 表示运输总量表示运输总量.可行流总是存在的可行流总是存在的.比如所有边的流量比如所有边的流量fij=0就是一个可行流就是一个可行流(称为零流称为零流).).所谓所谓最大流问题最大流问题就是在容量网络中就是在容量网络中,寻找流量最大的可行流寻找流量最大的可行流.实际问题中实际问题中,
50、一个网络会出现下面两种情况：一个网络会出现下面两种情况：发点和收点都不止一个发点和收点都不止一个.解决的方法是再虚设一个发点解决的方法是再虚设一个发点vs和一个收点和一个收点vt,发点发点vs到所有到所有原发点边的容量都设为无穷大原发点边的容量都设为无穷大,所有原收点到收点所有原收点到收点vt 边的容量都边的容量都设为无穷大设为无穷大.网络中除了边有容量外网络中除了边有容量外,点也有容量点也有容量.解决的方法是将所有有容量的点分成两个点解决的方法是将所有有容量的点分成两个点,如点如点v有容量有容量Cv,将点将点v分成两个点分成两个点v和和v,令令C(vv)=Cv.数学建模图论模型 这里我们要进