图论开题报告

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