《数学建模图论》PPT课件

--数学建模基地系列课件--数学建模图论方法专题七桥问题能否从任一陆地出发通过每座桥恰好一次而回到出发点？图论的基本概念华中农业大学数学建模基地七桥问题模拟图:ABDC欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。图论的基本概念哈密顿圈（环球旅行游戏）十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？图论的基本概念四色问题对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了。德·摩尔根致哈密顿的信（1852年10月23日）我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。……图论的基本概念(关键路径问题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？图论的基本概念一个有序二元组(V,E)称为一个图,记为G=(V,E),其中①V或V(G)称为G的顶点集,V≠Φ,其元素称为顶点或结点,简称点;②E或E(G)称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.的顶点数和边数。表示图或可以用GEV图论的基本概念={v1,v2,…,vn}是有限非空点集,则称G为有限图或n阶图.如果E的每一条边都是无向边,则称G为无向图;如果E的每一条边都是有向边,则称G为有向图;否则,称G为混合图.记E={e1,e2,…,em}(ek=vivj).图论的基本概念=(V,E),人们常用图形来表示它,称其为图解.凡是有向边,在图解上都用箭头标明其方向.称点vi,vj为边vivj的端点.有边联结的两个点称为相邻顶点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.有向图中的关联又分出关联和入关联。图论的基本概念(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.与顶点v出关联的边的数目称为出度，记作d+(v),与顶点v入关联的边的数目称为入度，记作d-(v)。用N(v)表示图G中所有与顶点v相邻的顶点的集合.图论的基本概念任意两顶点都相临的简单图称为完全图.有n个顶点的完全图记为Kn。华中农业大学数学建模基地几个基本定理：.21EvdEVGVv，有，、对图数个。、度为奇数的顶点有偶2.3EvdvdEVGVvVv则是有向图，，、设图论的基本概念、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。图论的基本概念华中农业大学数学建模基地解：用四维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)也是不允许的，图论的基本概念华中农业大学数学建模基地人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。图论的基本概念、考虑中国象棋的如下问题：（1）下过奇数盘棋的人数是偶数个。（2）马有多少种跳法？（3）马跳出后又跳回起点，证明马跳了偶数步。（4）红方的马能不能在自己一方的棋盘上不重复的跳遍每一点，最后跳回起点？图论的基本概念、证明：在任意6人的集会上，总有3人互相认识，或总有3人互相不认识。解：以顶点表示人，以边表示认识，得6个顶点的简单图G。问题：3人互相认识即G包含K3为子图，3人互相不认识即G包含（3,0）图为子图。图论的基本概念华中农业大学数学建模基地为子图。包含点不相邻，则点至少、这图为子图。包含点两两相邻，则、这。这又包含两种情况：点不相邻个顶即至少与另外个顶点相邻至多与另外）（为子图。包含点相邻，则点至少、这图为子图。包含点互不相邻，则、这两种情况：个顶点相邻，这又包含至少与另外则有两种情况：任取0,323231)3(222320,33131,33GKGvKGGvGVv图论的基本概念(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).定义3设G=(V,E)是一个图,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,则称v0v1…vk是G的一条通路.图论的基本概念如果通路中没有相同的顶点,则称此通路为路径,简称路.始点和终点相同的路称为圈或回路.称为连通的，如果存在u-v通路，任二顶点都连通的图称为连通图，否则，称为不连通图。极大连通子图称为连通支。图论的基本概念定义5连通而无圈的图称为树,常用T表示树.树中最长路的长称为树的高。树的度为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。设G是有向图，如果G的基础图是树，则称G是有向树，也简称树。华中农业大学数学建模基地⑴邻接矩阵A=(aij)n×n,EvvEvvajijiij,0,1例4：写出右图的邻接矩阵：0101100101001010A解：图的矩阵表示华中农业大学数学建模基地⑵权矩阵A=(aij)n×nEvvjiEvvvvFajijijiij,,0,例5：写出右图的权矩阵：05420370860A解：图的矩阵表示华中农业大学数学建模基地⑶关联矩阵A=(aij)n×m不关联与若的终点是若的始点是若iiiiiiijeveveva,0,1,1有向图：无向图：不关联与若关联与若jijiijvvvva,0,1图的矩阵表示：写出右图与其基本图的关联矩阵解：分别为：1101100011011000000111011001A1101100011011000000111011001A图的矩阵表示(u,v)是赋权图G=(V,E,F)中从点u到v的路径,用E(P)表示路径P(u,v)中全部边的集合,记F(P)=,则称F(P)为路径P(u,v)的权或长度(距离).)()(PEeeF定义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的最短路.即：最短路是一条路，且最短路的任一段也是最短路。最短路到其余顶点的最短路。0v2v1v3v4v5v1445642537最短路算法：求某一顶点到其余顶点的最短路的最短距离，最短路到踪）的紧前顶点（作逆向追树中的距离到集表示生长到树中的顶点表示用其对应下标数记号：顶点iiiikkvvPdvirvvklSGVSSkv0000:,::\:SjjrSjjiajllSstep,0,,,00,0:13:,4,,,,,2stepifSthensteporelsejSifljlkakjthenljlkakjrjkturnstep04:,;0,,,,,iojstepifljthendliPrririi0v2v1v3v4v5v14456425370v2v1v3v4v5v14456425372:min,4,steplkljjSiflkthensteporelseSSk最短路－523－374例8：求下列任意两点的最短路和距离。最短路算法:求任意两顶点的最短路设A=(aij)n×n为赋权图G=(V,E,F)的权矩阵,dij表示从vi到vj点的距离,rij表示从vi到vj点的最短路中一个点的编号.①赋初值.对所有i,j,dij=aij,rij=j.k=1.转向②.②更新dij,rij.对所有i,j,若dik+dkj＜dij,则令dij=dik+dkj,rij=k,转向③;③终止判断.若k=n终止;否则令k=k+1,转向②.最短路线可由rij得到.1v3v2v4v5v68－523－3741v3v2v4v5v68－523－374最短路中某一点到其它各点最短路，一般用Dijkstra标号算法；Dijkstra标号算法只适用于全部权为非负情况。求非负赋权图上任意两点间的最短路，一般用Floyd算法.Floyd算法可以适用于有负权的情况，还能判断是否有负回路。这两种算法均适用于有向赋权图.最短路华中农业大学数学建模基地由树的定义不难知道,任意一个连通的(p,q)图G适当去掉q-p+1条边后,都可以变成树,这棵树称为图G的生成树.设T是图G的一棵生成树,用F(T)表示树T中所有边的权数之和,F(T)称为树T的权.一个连通图G的生成树一般不止一棵,图G的所有生成树中权数最小的生成树称为图G的最小生成树.最小生成