利用图论知识解决实际问题.doc

淮北师范大学 2013届学士学位论文 利用图论知识解决实际问题的方法探究 学院、专业 数学科学学院 数学与应用数学 研 究 方 向 离散数学 学 生 姓 名 杨 波 学 号 20091101179 指导教师姓名 刘楠楠 指导教师职称 讲 师 2013年3月25日 利用图论知识解决实际问题的方法探究 杨 波 （淮北师范大学数学科学学院，淮北，235000） 摘 要 图论是数学的一个分支,是近年来发展迅速而又应用广泛的一门新兴学科。随着科学的进步，图论知识越来越贴近于生产和生活，所以利用图论知识来解决实际问题又成为当今的一大热点。着色、绘图、运输最短路径、集合等都与图论知识离不开。本课题将重点利用图论知识来解决实际生活、生产中的问题。 本文首先介绍了图的基本概念，对图论所涉及的基本知识进行简单的阐述，使读者对图论知识有一定的了解；再介绍图论中两种特殊的图形：欧拉图和哈密顿图，并用它们分析如何解决最短路问题和货郎担问题；然后介绍着色问题以及其与实际生活的联系；最后通过实例来说明图论知识在日常生产、生活中的运用。 关键词 图论，欧拉图，哈密顿图，最短路径，着色问题, 应用 The method of using graph theory knowledge to solve practical problems Yang Bo （College of Mathematical Science, Huaibei Normal University, Huaibei, 235000） Abstract Graph theory is a branch of mathematics that has been developed rapidly and used widely in recent years. With the progress of science, graph theory is increasingly close to the production and life, so using the knowledge of graph theory to solve practical problems has become a focus today. Coloring, drawing, the shortest path of transportation cannot be separated from graph theory knowledge. The article lays press on the using of graph theory to solve the practical problems in production knowledge in real life. This article first introduces the basic concept of graph, and make a further introduction to the basic knowledge of graph theory which involved a simple elaboration, then the reader can have a certain knowledge of graph theory knowledge; Then two kinds of special graphics are referred to: the Eulerian graph and Hamiltonian graph, along with their analysis of how to solve the problem of the short circuit and traveling salesman problem. Then the article discuss the coloring problem and its links with real life; Finally by an example to illustra