利用图论知识解决实际问题精选.docVIP

淮北师范大学 201届学士学位论文 学院、专业 数学科学学院 数学与应用数学 研 究 方 向 离散数学 学 生 姓 名 学 号 指导教师姓名 指导教师职称 2013年3月25日 摘 要 图论是数学的一个分支,是近年来发展迅速而又应用广泛的一门新兴学科 关键词 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 illustrate the application of graph theory knowledge in daily life and production. Keywords Graph theory, Eulerian graph, Hamiltonian graph, shortest paths,coloring, application 目 录 引 言 1 （一） 1 1 图的基本概念 1 2 通路与回路 4 3 图的连通性 6 4 图的矩阵表示 8 欧拉图与哈密顿图 10 1 欧拉图 10 2 哈密顿图. 10 3 最短路问题与货郎担问题. 13 （三）着色 16 1 点着色 16 2 边着色 16 （四）图论知识在实际生活、生产中的应