数学竞赛中的图论问题

分类号 密级 U D C 编号

本科毕业论文(设计)

题目 数学竞赛中的图论问题 所 在 院 系 数学与数量经济学院 专 业 名 称 数学与应用数学 年 级 08级 学 生 姓 名 李曼 学 号 0850410013 指 导 教 师 孙静

二 0一二年 三 月

学位论文原创性声明

本人郑重声明：所呈交的论文是本人在孙静老师的指导下独立进行研究所取得的研究成果. 除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品.本人完全意识到本声明的法律后果由本人承担.

日期：2012年3月29日

作者：

文献综述

一 综述

在18世纪30年代，一个非常有趣的问题引起了欧洲数学家的浓厚兴趣，这个问题就是著名的哥尼斯堡七桥问题，即要求遍历哥尼斯堡七桥中的每一座桥恰好一次后回到出发点. 欧拉证明这是不可能完成的. 此后，欧拉发表了著名的论文《依据集合位置的阶梯方法》，这是图论领域的第一篇论文，标志着图论的诞生. 图论的真正发展始于20世纪五六十年代之间，是一门既古老又年轻的学科.

图论极有趣味性，严格来讲，它是组合数学的一个重要分支. 虽然图论只是研究点和线的学科,但是它的应用领域十分广泛，不仅局限于数学和计算机学科，还涵盖了社会学、交通管理等. 总的来说，图论这门科学具有以下特点：

（1） 图论蕴含了丰富的思想、漂亮的图形和巧妙的证明；

（2） 涉及的问题多且广泛，问题表明上简单朴素，本质上却十分深刻复杂； （3） 解决问题的方法千变万化，非常灵活，常常是一种问题一种解法. 由以上三个特点可以看出，图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的体系和解决问题的系统. 而且图论所研究的内容非常广泛，如图的连通性、遍历性、图的着色、图的可平面性等等.

二 内容

由于图论具有蕴含了丰富的思想、漂亮的图形和巧妙的证明，涉及的问题多且广泛，问题表面上简单朴素，本质上却十分深刻复杂，解决问题的方法千变万化，非常灵活，常常是一种问题一种解法的特点. 随着数学竞赛越来越规范化，并且越来越考察考生的灵活运用知识的能力. 因此近年来，图论问题频繁的出现在数学竞赛中，如典型的一笔画问题、中国邮递员问题、旅游推销员问题、排课表问题等.

所谓一笔画问题，就是某图G中，从图中的某个点出发，用铅笔不离开纸面，一笔画出整个图. 在一笔画问题中，首先介绍欧拉迹和欧拉图的概念，然后给出图G欧拉图的充要条件是，G连通且没有奇顶点. 另外再给出一个图能够一笔画成的充要条件是，图G连通且奇顶点数为0或2. 一笔画算法即是从起点a开始，选择关联边（第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过）向前延伸，如果

到达终点b，得到a—b迹，判断路上的边数是否为图的总边数，是就终止，否则选择迹上某个关联边没有用完的顶点v，用同样方式再搜索v—v的闭迹，添加到a—b迹上，即得到a—v—v—b迹，如果这个迹的边数还没有达到总边数，则再选择迹上某个关联边没有用完的顶点······逐步扩展即可.

所谓中国邮递员问题，就是假定邮递员从邮局出发经过所投递范围内的每条街道，在递送完邮件之后，又返回邮局，问邮递员如何选择投递路线使经过的总路程最短？这个问题就是著名的中国邮递员问题.

如果把投递点作为顶点，所经过的街道作为边，梁顶点间的投递距离作为相应边的权，则得到一个非负权的连通图. 于是中国邮递员问题转化为在一个非负权连通图G中求包含G的所有边的权最小的闭通道. 最后中国邮递员问题的解就是顶点集的完全图的最小权完美匹配.

中国邮递员问题的算法是设中国邮递员问题的模型图G=（V，E）是非负权连通图，所有奇顶点的集是X.

第1步 若X= ? ，转第6步.

第2步 求出X的任意两顶点间的距离和最短路. 第3步 做出赋权完全图K（X）. 第4步 求K（X）的最小权完美匹配M.

第5步 对每条边（i，j）∈M，在G中复制最短i-j路的边，使G成为欧拉图G，，令G=G.

第6步 在欧拉图G中求欧拉闭迹即得中国邮递员问题的解.

所谓的旅游推销员问题，假设有n个城市，已知任意两个城市间的旅游费用. 今有旅游推销员从某城市出发，欲到其余（n-1）个城市去推销. 问应选择怎样的路线，使其余（n-1）个城市刚好各访问一次又回到出发城市. 其总费用最少？这个问题被称为旅行推销员问题.

在排课表问题中，在一所学校有m位教师X1，X2，······，Xm和n个班级Y1，Y2，······，Yn. 已知教师Xi给班级Yj上排课表问题.

对于此问题，设顶点集V=（X，Y），X={x1，x2，······，xm}对应m位教师，Y={y1，y2，······，yn}对应n个班级，顶点xi与yj连接着

，

节课时，要求制订一张课表使课时尽量少. 这就是

条边，于是得到一个偶图G=（X，

Y，E）.假设在同一个课时，一位教师最多上一个班的课，并且，一个班也最多由一位教师上课，因此在同一个课时的教学时间表对应偶图G的一个匹配. 反之，图G的每个匹配都对应在一个课时教师上课的一个分派. 换言之，偶图G的一个匹配与课表的一个课时正好一一对应. 因此，排课表的问题转化为求偶图的匹配，而使匹配的个数尽量少.

在图论中，有很多方面都值得研究，如染色问题、遍历性问题、图的连通性、图的可连通性等. 并且在数学竞赛，无论是小学数学竞赛、初中数学竞赛，还是高中数学竞赛，甚至很多国际的奥林匹克竞赛中有很多的应用.

本文通过介绍图论中的基本概念，通过介绍度、欧拉回路、哈密尔顿圈与哈密尔顿路和匹配的基本的定理，并结合该定理与数学竞赛中试题进行了讨论.

三 总结

图论问题蕴含了丰富的思想、巧妙的证明，而且涉及的问题多且广泛，解决的问题也十分广泛，非常灵活，常常是一种问题一种解法，因此图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的体系和解决问题的系统. 而且图论所研究的内容非常广泛，如图的连通性、遍历性、图的着色、图的可平面性等等.

文中只是简单的介绍了图的基本概念，然后结合度、欧拉回路、哈密尔顿圈与哈密尔顿路和匹配的基本定理，并结合该定理与数学竞赛中的试题进行了讨论.文中还有很多问题并没有涉及到，并且，图论问题中仍然还有许多问题并没有干净、漂亮的解决，还需要很多研究者不断的研究和发现图论问题中的奥妙.

参考文献

[1]王树禾.图论.北京：科学出版社,2009

[2]王树禾.图论及其算法.合肥：中国科学技术大学出版社，1990 [3]王树禾.从哥尼斯堡七桥问题谈起.长沙：湖南教育出版社，1999 [4]徐俊明.图论及其应用.安徽：中国科技技术大学出版社，2010 [5]王朝瑞.图论.北京：人民教育出版社，1981

[6]Andrasfai B.图论导引.郭照人译.北京：高等教育出版社，1980

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数学竞赛中的图论问题在线全文阅读。