数学建模图论模型(1)课件

单击此处编辑母版标题样式,下,回,停,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,数学建模图论模型,(1),有图有真相，有你更精彩,数学与统计学院 李书选,shuxuanli,2012/07/17,数学建模图论模型(1)有图有真相，有你更精彩 数学与统计,不积硅步，无以至千里,-,荀子,劝学,不积硅步，无以至千里,1.,几个引例,2.,基本概念,1.,基本概念,3.,最短路问题及算法,4.,简单应用,1. 几个引例2. 基本概念 1. 基本概念 3,A,B,C,D,哥尼斯堡七桥示意图,问题,1:,七桥问题,能否从任一陆地出发通过每座桥恰好一次而回到出发点？,1.,几个引例,ABCD哥尼斯堡七桥示意图问题1:七桥问题 1. 几个引例,七桥问题模拟图,A,B,D,C,欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。,七桥问题模拟图ABDC欧拉指出：如果每块陆地所连接的桥都是偶,莱昂哈德,欧拉,(Leonhard Euler,，,1707.4.5-1783.9.18),瑞士的数学家和物理学家。他被称为历史上最伟大的两位数学家之一（另一位是卡尔,弗里德里克,高斯）。欧拉出生于瑞士，在那里受教育。他是一位数学神童。作为数学教授，他先后任教于圣彼得堡,(1727-1741),和柏林，尔后再返圣彼得堡,(1766),。,欧拉的一生很虔诚。然而，那个广泛流传的传说却不是真的。传说中说到，欧拉在叶卡捷琳娜二世的宫廷里，挑战德尼,狄德罗：,“,先生，,(,a,+,b,),n,/,n,=,x,；所以上帝存在，这是回答！,”,欧拉的离世也很特别：据说当时正是下午茶时间，正在逗孙儿玩的时候，被一块蛋糕卡在喉头窒息而死。,欧拉是第一个使用,“,函数,”,一词来描述包含各种参数的表达式的人，例如：,y,=,F,(,x,) (,函数的定义由莱布尼兹在,1694,年给出,),。他是把微积分应用于物理学的先驱者之一。欧拉是有史以来最多产的数学家，他的全集共计,75,卷。欧拉实际上支配了,18,世纪的数学，对于当时新发明的微积分，他推导出了很多结果。在他生命的最后,7,年中，欧拉的双目完全失明，尽管如此，他还是以惊人的速度产出了生平一半的著作。,小行星欧拉,2002,是为了纪念欧拉而命名的。,莱昂哈德,欧拉,莱昂哈德欧拉,问题,2:,哈密顿圈（环球旅行游戏）,十二面体的,20,个顶点代表世界上,20,个城市，能,否从某个城市出发在十二面体上依次经过每个,城市恰好一次最后回到出发点？,问题2:哈密顿圈（环球旅行游戏）,问题,3:,四色问题,对任何一张地图进行着色，两个共同边界的,国家染不同的颜色，则只需要四种颜色就够了。,德,摩尔根致哈密顿的信（,1852,年,10,月,23,日）,我的一位学生今天请我解释一个我过去不知道，现在仍不甚,了了的事实。他说如果任意划分一,个图形并给各部分着上颜色，使任,何具有公共边界的部分颜色不同，,那么需要且仅需要四种颜色就够了,。下图是需要四种颜色的例子,（图,1,）。,问题3:四色问题 对任何一张地图进行着色，两个共同,问题,4(,关键路径问题,),一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序,.,这些工序相互约束,只有在某些工序完成之后,一个工序才能开始,.,即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间,.,这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？,问题4(关键路径问题),2.,图论的基本概念,1),图的概念,2),赋权图与子图,3),图的矩阵表示,4),图的顶点度,5),路和连通,2.图论的基本概念1) 图的概念2) 赋权图与子图3) 图的,1),图的概念,定义,一个,图,G,是指一个二元组,(V(G),E(G),，其中,:,其中元素称为图,G,的,顶点,.,组成的集合，即称为,边集,其中元素称为,边,.,定义,图,G,的,阶,是指图的顶点数,|,V(G)|,用,来表示；,图的边的数目,|,E(G)|,用,来表示,.,也用,来表示边,是非空有限集，称为,顶,点集,，,1),2),E(G,),是顶点集,V(G),中的无序或有序的元素偶对,表示图，,简记,用,1) 图的概念 定义 一个图G是指一个二元组(V(G),定义,若一个图的顶点集和边集都是有限集，则称,其为,有限图,.,只有一个顶点的图称为,平凡图,，其他的,所有图都称为,非平凡图,.,定义 若一个图的顶点集和边集都是有限集，则称 其为,定义,若,图,G,中的边均为有序偶对,称,G,为,有向,边 为,无向边,，称,e,连接,和 ，顶点 和 称,图,.,称边,为,有向边,或,弧,称,是从,连接,，称 为,e,的,尾,，称 为,e,的,头,.,若图,G,中的边均为无序偶对 ，称,G,为,无向图,.,称,为,e,的,端点,.,既有无向边又有有向边的图称为,混合图,.,定义若图G中的边均为有序偶对,称G为有向边,常用术语,1),边和它的两端点称为互相,关联,.,2),与同一条边关联的两个端点称,为,相邻,的顶点，与同一个顶点,点关联的两条边称为,相邻,的边,.,3),端点重合为一点的边称为,环,，,端点不相同的边称为,连杆,.,4),若一对顶点之间有两条以上的边联结，则这些边,称为,重边,5),既没有环也没有重边的图，称为,简单图,常用术语1) 边和它的两端点称为互相关联.2)与同一,常用术语,6),任意两顶点都相邻的简单图,称为完全图,.,记为,K,v.,7),若 ，,，,且,X,中任意两顶点不,，,相邻，,Y,中任意两顶点不相邻，则称为,二部图,或,偶图,；若,X,中每一顶点皆与,Y,中一切顶点相邻,称为,完全二部图,或,完全偶图,记为,(,m=|X|,n=|Y|,),8),图 叫做,星,.,二部图,常用术语6) 任意两顶点都相邻的简单图,称为完全图.,2),赋权图与子图,定义,若图 的每一条边,e,都赋以,一个实数,w(e),，称,w(e),为边,e,的,权,，,G,连同边上的权,称为,赋权图,.,定义,设 和 是两个图,.,1),若,称 是 的一个,子图,记,2),若 ， ，则称 是 的,生成子图,.,3),若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,为 的,由 导出的子图,，记为,.,4),若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的,由 导出的,边导出的子图,，记为,.,2) 赋权图与子图 定义 若图,3),若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,4),若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的,由 导出的,边导出的子图,，记为,.,为 的,由 导出的子图,，记为,.,3) 若 ，且 ，以,3),图的矩阵表示,邻接矩阵,:,1),对无向图 ，其邻接矩阵 ，其中：,(,以下均假设图为简单图,).,3) 图的矩阵表示 邻接矩阵:1) 对无向图 ，其邻接矩,2),对有向图,其邻接矩阵,其中：,2) 对有向图 ,其邻接矩阵,其中：,3),对有向赋权图,其邻接矩阵,对于无向赋权图的邻接矩阵可类似定义,.,其中：3) 对有向赋权图 ,关联矩阵,1),对无向图 ，其关联矩阵,其中：,关联矩阵 1) 对无向图 ，,2),对有向图 ，其关联矩阵,其中：,2) 对有向图 ，其关联矩阵,邻接矩阵,A,= (,a,ij,),n,n,例 写出右图的邻接矩阵,解：,图的矩阵表示, 邻接矩阵 A = (aij )nn , 例 写,权矩阵,A,= (,a,ij,),n,n,例 写出右图的权矩阵：,解：,图的矩阵表示, 权矩阵A = (aij ) nn 例 写出右,4),图的顶点度,定义,1),在无向图,G,中，与顶点,v,关联的边的数目,(,环,算两次,),称为顶点,v,的,度,或,次数,，记为,d(v),或,d,G,(v,).,称度为奇数的顶点为,奇点,，度为偶数的顶点为,偶点,.,2),在有向图中，从顶点,v,引出的边的数目称为顶点,v,的,出度,，记为,d,+,(v),，从顶点,v,引入的边的数目称为,v,的,入度,，记为,d,-,(v),.,称,d(v)= d,+,(v)+d,-,(v),为顶点,v,的,度,或,次数,定理,的个数为偶数,推论,任何图中奇点,4) 图的顶点度定义 1) 在无向图G中，与顶点v关联的边的,5),路和连通,定义,1),无向图,G,的一条,途径,（或,通道,或,链,）是指,一个有限非空序列 ，它的项交替,地为顶点和边，使得对 ， 的端点是 和,称,W,是从 到 的一条,途径,，或一条,途径,.,整,数,k,称为,W,的,长,.,顶点 和 分别称为的,起点,和,终点,而 称为,W,的,内部顶点,.,2),若途径,W,的边互不相同但顶点可重复，则称,W,为,迹,或,简单链,.,3),若途径,W,的顶点和边均互不相同，则称,W,为,路,或,路径,.,一条起点为,终点为 的路称为,路,记为,5) 路和连通 定义1) 无向图G的一条途径（或通道或,定义,1),途径 中由相继项构成子序列,称为途径,W,的,节,.,2),起点与终点重合的途径称为,闭途径,.,3),起点与终点重合的的路称为,圈,(,或,回路,),，长,为,k,的圈称为,k,阶圈,，记为,C,k,.,4),若在图,G,中存在,(,u,v,),路，则称顶点,u,和,v,在图,G,中,连通,.,5),若在图,G,中顶点,u,和,v,是连通的，则顶点,u,和,v,之,之间的,距离,d,(,u,v,),是指图,G,中最短,(,u,v,),路的长；若没,没有路连接,u,和,v,，则定义为无穷大,.,定义 1) 途径,6),图,G,中任意两点皆连通的图称为,连通图,7),对于有向图,G,，若 ，且 有,类似地，可定义,有向迹,，,有向路,和,有向圈,.,头 和尾 ，则称,W,为,有向途径,.,例,在右图中：,途径或链：,迹或简单链：,路或路径：,圈或回路：,6) 图G中任意两点皆连通的图称为连通图,例 一摆渡人欲将一只狼，一头羊，一篮菜从,河西渡过河到河东，由于船小，一次只能带一物,过河，并且，狼与羊，羊与菜不能独处，给出渡,河方法。,例 一摆渡人欲将一只狼，一头羊，一篮菜从,解：,用四维,0-1,向量表示（人，狼，羊，菜）的在西岸,状态，（在西岸则分量取,1,，否则取,0.,）,共,2,4,=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),也是,不允许的，,图论的基本概念,解：用四维0-1向量表示（人，狼，羊，菜）的在西岸共24=1,人在河西：,（,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,1,1,1）（1,1,1,0）（1,1,0,3,最短路问题及算法,最短路问题是图论应用的基本问题，很多实际,问题，如线路的布设、运输安排、运输网络最小费,用流等问题,都可通过建立最短路问题模型来求解,.,最短路的定义,最短路问题的两种方法：,Dijkstra,和,Floyd,算法,.,1),求赋权图中从给定点到其余顶点的最短路,.,2),求赋权图中任意两点间的最短路,.,3最短路问题及算法 最短路问题是图论应用的基本问,2),在赋权图,G,中，从顶点,u,到顶点,v,的具有最小权,定义,1),若,H,是赋权图,G,的一个子图，则称,H,的各,边的权和 为,H,的,权,.,类似地，若,称为路,P,的,权,若,P,(,u,v,),是赋权图,G,中从,u,到,v,的路,称,的路,P*,(,u,v,),，称为,u,到,v,的,最短路,3),把赋权图,G,中一条路的权称为它的,长,，把,(,u,v,),路的最小权称为,u,和,v,之间的,距离,，并记作,d,(,u,v,).,2) 在赋权图G中，从顶点u到顶点v的具有最小权,1),赋权图中从给定点到其余顶点的最短路,假设,G,为赋权有向图或无向图，,G,边上的权均非,负若 ，则规定,最短路是一条路，且最短路的任一节也是最短路,求下面赋权图中顶点,u,0,到其余顶点的最短路,1) 赋权图中从给定点到其余顶点的最短路 假设G为赋,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.,数学建模图论模型(1)课件,定义,根据顶点,v,的标号,l(v),的取值途径，使 到,v,的最短路中与,v,相邻的前一个顶点,w,，称为,v,的,先驱,点,，记为,z,(,v,),即,z,(,v,)=,w,.,先驱点可用于追踪最短路径,.,例,5,的标号过程也,可按如下方式进行：,首先写出左图带权邻接矩阵,因,G,是无向图，故,W,是对称阵,定义 根据顶点v的标号l(v)的取值途径，使 到v的最,数学建模图论模型(1)课件,数学建模图论模型(1)课件,Dijkstra,算法：,求,G,中从顶点,u,0,到其余顶点的最短路,设,G,为赋权有向图或无向图，,G,边上的权均均非负,.,对每个顶点，定义两个标记（,l(v),，,z(v),），其中,:,l(v),：,表从顶点,u,0,到,v,的一条路的权,z(v),：,v,的先驱点，用以确定最短路的路线,.,l(v),为从顶点,u,0,到,v,的最短路的权,算法的过程就是在每一步改进这两个标记，使最终,S,：具有永久标号的顶点集,.,输入,:,G,的带权邻接矩阵,w(u,v),备用,-,将求最短路与最短路径结合起来,:,Dijkstra算法：求G中从顶点u0到其余顶点的最短路设G,算法步骤：,l(v),u,0,v,l(u),u,w(u,v),算法步骤：l(v)u0vl(u)uw(u,v),首先写出带权邻接矩阵,例 求下图从顶点,u,0,到其余顶点的最短路,因,G,是无向图，故,W,是对称阵,首先写出带权邻接矩阵例 求下图从顶点u0到其余顶点的最短路,数学建模图论模型(1)课件,数学建模图论模型(1)课件,2),求赋权图中任意两顶点间的最短路,算法的基本思想,（,I,）求距离矩阵的方法,.,（,II,）求路径矩阵的方法,.,（,III,）查找最短路路径的方法,.,Floyd,算法：求任意两顶点间的最短路,.,举例说明,2) 求赋权图中任意两顶点间的最短路算法的基本思想 （I）求,算法的基本思想,算法的基本思想,（,I,）求距离矩阵的方法,.,（I）求距离矩阵的方法.,（,II,）求路径矩阵的方法,.,在建立距离矩阵的同时可建立路径矩阵,R,（II）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵,（,III,）查找最短路路径的方法,.,然后用同样的方法再分头查找若：,（III）查找最短路路径的方法.然后用同样的方法再分头查找,（,IV,）,Floyd,算法：求任意两顶点间的最短路,.,（IV）Floyd算法：求任意两顶点间的最短路.,例,求下图中加权图的任意两点间的距离与路径,.,例 求下图中加权图的任意两点间的距离与路径.,插入点,v,1,，,得：,矩阵中带“,=,”,的项为经迭代比较以后有变化的元素,.,插入点 v1，得：矩阵中带“=”的项为经迭代比较以后有变化的,插入点,v,2,，,得：,矩阵中带“,=,”,的项为经迭代比较以后有变化的元素,.,插入点 v2，得：矩阵中带“=”的项为经迭代比较以后有变化的,插入点,v,3,，,得：,插入点 v3，得：,插入点,v,4,，,得：,插入点,v,5,，,得：,插入点 v4，得：插入点 v5，得：,插入点,v,6,，,得：,插入点 v6，得：,故从,v,5,到,v,2,的最短路为,8,由,v,6,向,v,5,追溯,:,由,v,6,向,v,2,追溯,:,所以从到的最短路径为：,故从v5到v2的最短路为8 由v6向v5追溯: 由v6向v2,学而时习之，不亦说乎,-,论语,学而,学而时习之，不亦说乎,4,最短路问题的简单应用,4最短路问题的简单应用,返回,返回,选址问题,-,中心问题,选址问题-中心问题,S,(,v,1,)=10,S,(,v,2,)=7,S,(,v,3,)=6,S,(,v,4,)=8.5,S,(,v,5,)=7,S,(,v,6,)=7,S,(,v,7,)=8.5,S,(,v,3,)=6,故应将消防站设在,v,3,处,.,返回,S(v1)=10, S(v2)=7, S(v3)=6, S(,选址问题,-,重心问题,返回,选址问题-重心问题返回,祝各位同学大展宏“图”！,谢谢！,祝各位同学大展宏“图”！谢谢！,