2014数学中国中学生数学建模竞赛培训讲义xin

图论模型数学中国网站站长：马壮本讲的主要内容图论的一些简单实例图论基础图论的应用、图论的基本概念ABCD哥尼斯堡七桥示意图问题1(哥尼斯堡七桥问题):能否从任一陆地出发通过每座桥恰好一次而回到出发点？七桥问题模拟图欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地.、一个简单的例子印刷电路板将布线区域划分为n×m个方格阵列精确的电路板布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。布线时电路只能沿直线或直角布线。为避免线路相交，已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。、引例现有6个人，任意两人之间或者相互认识，或者相互不认识，证明这6个人中，或者有3个人彼此都认识，或者有3个人彼此不认识个人，人数非常少，可以枚举任意两人之间的关系，然后判断每一种情况是否符合题意。如果所有情况都满足，则命题成立。虽然只有6个人，但是这样做的时间复杂度可不低，枚举次数为215只能借助计算机了。。。有没有人可以直接证明的办法呢？思路二有了图论这个强大的工具，我们还是像往常一样，以人为顶点，关系为边，建图。但是为了以后的直观，这里图的建立有一点小小的不同：如果两个人之间相互认识，则在这两个人(顶点)间连一条红色边，如果两个人不认识，则在这两个人(顶点)间连一条蓝色边(下面会看到这样做的好处)那么这样我们就得到了一个由红边和蓝边组成的6阶完全图我们实际上要证明的就是这个图中或者存在一个红三角形(认识)，或者存在一个蓝三角形(不认识)，由它连出5条边到其它的顶点，这五条边只有红色和蓝色两种根据抽屉原理，肯定有一种颜色的边有3条或3条以上,不妨设为红色viv0vjvk如果vi,vj,vk之间的边都是蓝边，则图中存在一个蓝三角形如果至少有1条为红边，那么它总会与v0发出的两条红边组成一个红三角形。这样就证明了这个命题。、商人们怎样安全过河问题(智力游戏)3名商人3名随从随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货.但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?问题分析多步决策过程决策~每一步(此岸到彼岸或彼岸到此岸)船上的人员要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.河小船(至多2人)~第k次渡河前此岸的商人数yk~第k次渡河前此岸的随从数xk,yk=0,1,2,3;k=1,2,sk=(xk,yk)~过程的状态S={(x,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}S~允许状态集合uk~第k次渡船上的商人数vk~第k次渡船上的随从数dk=(uk,vk)~决策D={(u,v)u+v=1,2}~允许决策集合uk,vk=0,1,2;k=1,2,sk+1=skdk+(-1)k~状态转移律求dkD(k=1,2,n),使skS,并按转移律由s1=(3,3)到达sn+1=(0,0).多步决策问题•穷举法~编程上机•图解法状态s=(x,y)~16个格点~10个点允许决策~移动1或2格;k奇,左下移;k偶,右上移.s1sn+1d1,，d11给出安全渡河方案评注和思考规格化方法,易于推广考虑4名商人各带一随从的情况d1d11允许状态S={(x,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}图的定义图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.定义1一个有序二元组(V,E)称为一个图,记为G=(V,E),其中①V称为G的顶点集,V≠,其元素称为顶点或结点,简称点;②E称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.如果V={v1,v2,…,vn}是有限非空点集,则称G为有限图或n阶图.的每一条边都是无向边,则称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)图=(V,E),人们常用图形来表示它,称其为图解.凡是有向边,在图解上都用箭头标明其方向.例如,设V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},则G=(V,E)是一个有4个顶点和6条边的图,G的图解如下图所示.一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E)的图解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.这两个图互为同构图,今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图.有边联结的两个点称为相邻的点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.对于有向图,还有出度和入度之分.用N(v)表示图G中所有与顶点v相邻的顶点的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.mvdnii2)(1握手定理：我们今后只讨论有限简单图：(1)顶点个数是有限的;(2)任意一条边有且只有两个不同的点与它相互关联;(3)若是无向图,则任意两个顶点最多只有一条边与之相联结;(4)若是有向图,则任意两个顶点最多只有两条边与之相联结.当两个顶点有两条边与之相联结时，这两条边的方向相反.如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).定义3任意两点均有通路的图称为连通图.定义4连通而无圈的图称为树,常用T表示树.例一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法.解：用四维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到A10的路.从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.图的矩阵表示⑴邻接矩阵邻接矩阵表示了点与点之间的邻接关系.一个n阶图G的邻接矩阵A=(aij)n×n,其中.,0;,1EvEvaijijij0101100101001010A是一个对称矩阵.0101101101011110A⑵权矩阵一个n阶赋权图G=(V,E,F)的权矩阵A=(aij)n×n,其中.,;;0),(EvjiEvvvFaijijjiij有限简单图基本上可用权矩阵来表示.05420370860A无向图G的权矩阵A是一个对称矩阵.02420737064360A⑶关联矩阵一个有m条边的n阶有向图G的关联矩阵A=(aij)n×m,其中若vi是ej的始点;若vi是ej的终点;若vi与ej不关联.,0,1,1ija有向图的关联矩阵每列的元素中有且仅有一个1,有且仅有一个-1.1101100011011000000111011001A一个有m条边的n阶无向图G的关联矩阵A=(aij)n×m,其中若vi与ej关联;若vi与ej不关联.,0,1ija无向图的关联矩阵每列的元素中有且仅有两个1.110100101010011001000111A、最短路径算法定义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的最短路.重要性质：若v0v1…vm是图G中从v0到vm的最短路,则1≤k≤m,v0v1…vk必为G中从v0到vk的最短路.即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.下面分别介绍两种算法的基本过程.算法指标（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)对