图论开题报告.docVIP

重庆三峡学院 毕业设计（论文）开题报告 设计 (论文)题目 图论及其在数学建模中的应用研究 院 系 数学与统计学院 专 业 信息与计算科学 年 级 2010级 学生学号 201006014128 学生姓名 蒋炼 指导教师 鲁祖亮 重庆三峡学院教务处 制 综述本课题研究动态、选题目的及意义 研究动态： 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。 图论起源于著名的哥尼斯堡七桥问题。在 哥尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来 问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽像 分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图”。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后来的欧拉路径和 欧拉回路。这项工作使 欧拉成为图论〔及 拓扑学〕的创始人。 选题目的： 数学模型是一种模拟，是用数学符号、数学式子、程序、图形等对实际课题本质属性的抽象而又简洁的刻划，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。数学模型一般并非现实问题的直接翻版，它的建立常常既需要人们对现实问题深入细微的观察和分析，又需要人们灵活巧妙地利用各种数学知识。而数学建模中图论方法是一种独特的方法，图论建模是指对一些客观事物进行抽象、化简,并用图来描述事物特征及内在联系的过程。图论算法在计算机科学中扮演着很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基本算法加以解决。 选题意义： 建立图论模型的目的和建立其它的数学模型一样,都是为了简化问题,突出要点,以便更深入地研究问题的本质;它的求解目标可以是最优化问题,也可以是存在性或是构造性问题。本课题的目的在于了解这方面的知识和应用，拓宽思路，掌握更多的实践知识。数学是研究现实世界数量关系和空间形式的科学，在它产生和发展的历史长河中，一直是和各种各样的应用问题紧密相关的。数学的特点不仅在于概念的抽象性、逻辑的严密性，结论的明确性和体系的完整性，而且在于它应用的广泛性，自从20世纪以来，随着科学技术的迅速发展和计算机的日益普及，人们对各种问题的要求越来越精确，使得数学的应用越来越广泛和深入，特别是在21世纪这个知识经济时代，数学科学的地位会发生巨大的变化，它正在从国家经济和科技的后备走到了前沿。经济发展的全球化、计算机的迅猛发展，数理论与方法的不断扩充使得数学已经成为当代高科技的一个重要组成部分和思想库，数学已经成为一种能够普遍实施的技术。培养学生应用数学的意识和能力已经成为数学教学的一个重要方面。而图论作为解决数学建模中的问题的重要方法之一，也是值得我们去了解及应用的。 研究基本内容、拟解决的主要问题 研究的基本内容： 1、了解为什么图论是研究事物对象在表示法中具有的特征与性质的学科及图论实际的应用方法和图论在数学建模中的应用及其作用。 2、列举图论在数学建模中需要解决的几个主要问题并查看资料和书籍，并作出相应的解答。 3、数学建模中运用了图论这一方法后，和之前未运用图论时的差别，图论在数学建模中起到的重要作用。 拟解决的主要问题： 1、查看资料及其相关文献、自我分析图论的历史及应用和图论在数学建模中的历史、应用及其相应的作用。 2、图论在数学建模中现需解决的问题有最短路问题、公路连接问题、指派问题、中国邮递员问题、旅行商问题、运输问题等几个重要的问题，通过查找相对应的题和资料并自我理解其含义，作出自己的判断和认识。 3、有哪些信誉好的足球投注网站与图论相关的历史文献，了解图论的来历及图论的在数学研究领域的发展史，之后并被逐步运用到各个数学领域，尤其是其在数学建模中的重要作用。 研究方法、步骤及措施 研究方法：