图的基本概念.ppt

一、涉及图论的历年数学建模题目1、93B足球队排名次2、94A逢山开路3、94B锁具装箱问题4、95B天车与冶炼炉的作业调度5、97B截断切割:最短路6、98B灾情巡视:最小生成树、Hamilton圈、、涉及图论的历年数学建模题目7、99B钻井布局:最大完全子图8、00B管道订购:最短路9、01B公交车调度10、02D赛程安排11、04A奥运会临时超市网点设计12、07乘公交,、涉及图论的历年数学建模题目13、08C地面搜索14、)98年全国大学生数学建模竞赛B题“最佳灾今年(1998年)、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、,走遍各乡(镇)、村,”中的前两个问题是这样的:.1)若分三组(路)巡视,)假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/,至少应分几组;给出这种分组下最佳的巡视路线..公路边的数字为该路段的公里数..2)问题分析:本题给出了某县的公路网络图,要求的是在不同的条件下,(镇)或村看作一个图的顶点,各乡镇、村之间的公路看作此图对应顶点间的边,各条再回到点O,使得总权(路程或时间)(或行驶时间)看作对应边上的权,所给公路网就转化为加权网络图,问题就转化图论中一类称之为旅行售货员问题,即在给定的加权网络图中寻找从给定点O出发,、图论简介图论是应用十分广泛的运筹学分支,它已广泛地应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。在实际生活、生产和科学研究中,有很多问题可以用图论的理论和方法来解决。.例如:在组织生产中,为完成某项生产任务,各工序之间怎样衔接,才能使生产任务完成得既快又好。一个邮递员送信,要走完他负责投递的全部街道,完成任务后回到邮局,应该按照怎样的路线走,所走的路程最短。各种通信网络的合理架设,交通网络的合理分布等。.图论是运筹学的一个经典和重要的分支,它起源于18世纪欧拉(Euler)对七桥问题的抽象和论证。1936年,匈牙利数学家柯尼希(König)出版了图论的第一部专著《有限图与无限图理论》,竖立了图论发展的第一座里程碑。.