资源描述：
《2010数模培训》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、全国数学建模竞赛培训这是一场艰苦的战役。需要不怕苦和不怕累的精神，要有坚忍不拔的毅力。7/18/2021可能面临酷暑、内容多、强度大的困难。7/18/2021数学建模暑期培训纪律不允许缺课，迟到和早退的现象发生。每一个队每一次培训或讲评，必须是三人到齐。教练会对每一次活动考勤，并与相关学院联系，对缺课学生予以相应处罚。7/18/2021图论算法参考教材：数学建模与数学实验（赵静、但琦编）数学建模导论（陈理荣编）图论及其算法（殷剑宏、吴开亚编）集合论与图论（耿素云编）7/18/2021图论算法１.最短路问题２.中国邮递员问题和ＴＳＰ问题３.匹配7/18/2
2、021图论算法（１）－最短路问题1．图论的基本概念2．最短路问题及其算法3．最短路的应用4．建模案例：最优截断切割问题5．实例应用7/18/2021图论的基本概念一、图的概念1．图的定义2．顶点的次数3．子图二、图的矩阵表示1．关联矩阵2．邻接矩阵返回7/18/2021定义有序三元组G=(V,E,)称为一个图,如果：图的定义7/18/2021定义定义7/18/20217/18/2021返回7/18/2021顶点的次数（度数）7/18/2021例在一次聚会中，认识奇数个人的人数一定是偶数.返回7/18/2021子图返回7/18/2021关联矩阵注：假设图为
3、简单图返回7/18/2021邻接矩阵注：假设图为简单图7/18/2021返回7/18/2021最短路问题及其算法一、基本概念二、固定起点的最短路三、每对顶点之间的最短路返回7/18/2021基本概念7/18/2021返回7/18/2021固定起点的最短路-Dijkstra算法最短路是一条路径，且最短路的任一段也是最短路．假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树．因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．7/18/2021Dijkstra算法思想Dijkstra算法:这是荷兰计算机科学教授Edsg
4、erW.Dijkstra(1930-)在1959年发现的一个算法.他在1972年获得计算机协会授予的图灵奖,这是计算机科学中最具声望的奖项.Dijkstra算法是求出一个连通加权简单图中从结点a到结点z的最短路.边{i,j}的权(i,j)>0,且结点x的标号为L(x),结束时,L(z)是从x到z的最短路的长度.7/18/20217/18/2021算法步骤：7/18/2021TOMATLAB(road1)7/18/20217/18/202112345678返回7/18/2021每对顶点之间的最短路-Floyd算法1．求距离矩阵的方法2．求路径矩阵的方法3
5、．查找最短路路径的方法（一）算法的基本思想（三）算法步骤返回7/18/2021算法的基本思想返回7/18/2021算法原理——求距离矩阵的方法返回7/18/2021算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．返回)(nR7/18/2021ij算法原理——查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：返回7/18/2021算法步骤7/18/2021TOMATLAB(road2(floyd))返回7/
6、18/2021一、可化为最短路问题的多阶段决策问题二、选址问题1．中心问题2．重心问题返回7/18/2021可化为最短路问题的多阶段决策问题7/18/20217/18/20217/18/2021返回7/18/2021选址问题--中心问题TOMATLAB(road3(floyd))7/18/2021S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处.返回7/18/2021选址问题--重心问题返回7/18/2021图论算法（２）－中国邮递员问题和ＴＳＰ
7、问题7/18/2021邮路问题及ＴＳＰ问题一、中国邮递员问题二、推销员问题三、建模案例：最佳灾情巡视路线（一）欧拉图（二）中国邮递员问题（一）哈密尔顿图（二）推销员问题7/18/20217312341245566789割边G的边是割边的充要条件是不含在G的圈中．割边的定义：设G连通，E(G),若从G中删除边后，图G-{}不连通，则称边为图G的割边．7/18/2021e3v1v2v3v4e1e2e4e5e6欧拉图e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v
8、3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v17/18/202
