数学建模图论模型

图论模型图论模型1.图论基本概念2.最短路径算法3.最小生成树算法4.遍历性问题5.二分图与匹配26.网络流问题7.关键路径问题8.系统监控模型9.着色模型1、图论的基本概念问题1(哥尼斯堡七桥问题):能否从任一陆地出发通过每座桥恰好一次而回到出发点？34欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地.5问题2(哈密顿环球旅行问题):十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？欧拉问题是“边遍历”，哈密尔顿问题是“点遍历”6问题3(四色问题):对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.问题4(关键路径问题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？图的定义图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.定义1一个有序二元组(V,E)称为一个图,记为G=(V,E),其中①V称为G的顶点集,V≠,其元素称为顶点或结点,简称点;②E称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.如果V={v1,v2,…,vn}是有限非空点集,则称G为有限图或n阶图.8如果E的每一条边都是无向边,则称G为无向图(如图1);如果E的每一条边都是有向边,则称G为有向图(如图2);否则,称G为混合图.图1图2并且常记:V={v1,v2,…,vn},|V|=n;E={e1,e2,…,em}(ek=vivj),|E|=m.称点vi,vj为边vivj的端点.在有向图中,称点vi,vj分别为边vivj的始点和终点.该图称为(n,m)图9对于一个图G=(V,E),人们常用图形来表示它,称其为图解.凡是有向边,在图解上都用箭头标明其方向.例如,设V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},则G=(V,E)是一个有4个顶点和6条边的图,G的图解如下图所示.10一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E)的图解.这两个图互为同构图,今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图.11有边联结的两个点称为相邻的点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.常用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)=112握手定理握手定理：无向图中，所有结点的度数之和等于2m。右图：推论1：无向图中必有偶数个度数为奇数的结点。推论2：有向图中所有结点的出度之和等于入度之和。d(v1)=d(v3)=d(v4)=4,d(v2)=2mvdnii2)(1147*2)(1niivd我们今后只讨论有限简单图：(1)顶点个数是有限的;(2)任意一条边有且只有两个不同的点与它相互关联;(3)若是无向图,则任意两个顶点最多只有一条边与之相联结;(4)若是有向图,则任意两个顶点最多只有两条边与之相联结.当两个顶点有两条边与之相联结时，这两条边的方向相反.如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.14定义2若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).定义3任意两点均有通路的图称为连通图.定义4连通而无圈的图称为树,常用T表示树.常用的图给定图G=V,E和G’=V’,E’是两个图，如果有V’⊆V和E’⊆E,则称图G’是图G的子图。若V’=V称图G’是图G的生成子图；若将图G的每一条边e都对应一个实数F(e)，则称F(e)为该边的权，并称图G为赋权图(网络),记为G=V,E,F。任意两点均有通路的图称为连通图。连通而无圈的图称为树，常用T=V,E表示树。若图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,A2,…,A10,从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.问题的转换：过河问题是否能解？即：图中A1到A10是否连通？有几种不同的解法？即：A1到A10之间有多少条不同的路径？最快的解决方案是什么？即：A1到A10最短路径有哪些？图的矩阵表示⑴邻接矩阵：邻接矩阵表示了点与点之间的邻接关系.一个n阶图G的邻接矩阵A=(aij)n×n,其中.,0;,1EvEvaijijij0101100101001010A2223无向图G的邻接矩阵A是一个对称矩阵.0101101101011110A⑵权矩阵一个n阶赋权图G=(V,E,F)的权矩阵A=(aij)n×n,其中.,;;0),(EvjiEvvvFaijijjiij有限简单图基本上可用权矩阵来表示.2405420370860A无向图G的权矩阵A是一个对称矩阵.02420737064360A25⑶关联矩阵：一个有m条边的n阶有向图G的关联矩阵A=(aij)n×m,其中若vi是ej的始点;若vi是ej的终点;若vi与ej不关联.,0,1,1ija有向图的关联矩阵每列的元素中有且仅有一个1,有且仅有一个-1.1101100011011000000111011001A26一个有m条边的n阶无向图G的关联矩阵A=(aij)n×m,其中若vi与ej关联;若vi与ej不关联.,0,1ija无向图的关联矩阵每列的元素中有且仅有两个1.110100101010011001000111A2、最短路径算法定义1设P(u,v)是赋权图G=(V,E,F)中从点u到v的路径,用E(P)表示路径P(u,v)中全部边的集合,记)()()(PEeeFPF则称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的最短路.28重要性质：若v0v1…vm是图G中从v0到vm的最短路,则1≤k≤m,v0v1…vk必为G中从v0到vk的最短路.即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.下面分别介绍两种算法的基本过程.Dijkstra算法指标（a为起点）设T为V的子集，P=V-T且a∈T，对所有t∈T，设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’=PU{x},T’=T-{x},l’(t)表示T'中结点t关于P'的指标,则29)},()(),(min{)('txwxltltlTttlxl)},(min{)(Dijkstra算法（求a点到其他点的最短路径）1、初始化，P={a}，T=V-{a}，对每个结点t计算指标l(t)=w(a,t)2、设x为T中关于P有最小指标的点,即:l(x)=min(l(t))(t∈T),3、若T=Ф,则算法结束;否则,令P'=PU{x},T'=T-{x}按照公式l'(t)=min{l(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))(t∈T);3、若T=Ф,则算法结束;否则,令P‘=PU{x},T’=T-{x}按照公式l‘(t)=min{l(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点到其他点的最短路.32Floyd算法（求