数学竞赛中的图论问题(2)

[7]Harry F.图论.李慰萱译.上海：上海科学技术出版社，1980

[8]叶其孝等.大学生数学建模竞赛辅导教材.长沙：湖南教育出版社，1998 [9]李尚志，王树禾等.数学建模竞赛教程.南京：江苏教育出版社，1996 [10]学而思培优教研部.小学奥数系统总复习上册.北京：西藏人民出版社，2012 [11]学而思培优教研部.小学奥数系统总复习下册.北京：西藏人民出版社，2012 [12]黄东坡.数学培优竞赛新帮手初三年级.湖北：湖北辞书出版社，2002 [13]陈传理，刘玉翘等.高中数学竞赛名师指导第二册.武汉：华中师范大学出版社.2001

[14]钱展望，朱华伟.奥林匹克数学训练题集初二分册.武汉：湖北教育出版社，2002

[15] 钱展望，朱华伟.奥林匹克数学训练题集高一分册.武汉：湖北教育出版社，2002

摘要：随着图论问题的发展，图论的理论和方法广泛的应用于数学竞赛中. 一方面，图论研究迅猛发展，问题层出不穷；另一方面，图论问题可以用通俗的形式表达，没有太多的术语，也不需要很深的理论. 并且，图论问题灵活巧妙，作为竞赛题很合适. 因此近年来图论问题在数学竞赛中反复的出现. 本文首先给出了图论问题中的一些基本概念，再从度、欧拉回路、哈密尔顿圈与哈密尔顿路和匹配四个方面，运用相应的理论，结合数学竞赛中的试题，分别进行了讨论.

关键词： 度；欧拉回路；哈密尔顿圈；哈密尔顿路；匹配

Abstract: With the development of Graph Theory, many theories and methods of graph theory are used in the mathematics tournament. On the one hand, with the rapid development of graph theory ,many issues are emerging; on the other hand ,graph theory can be expressed in simple forms, need not too many terms and does not require deep theories. On the same time, graph theory problems are so flexible and clever that they are appropriate to be the competition titles. In recent years, graph theory problems are repeated in the Mathematics Olympiad. Firstly this article gives some basic concepts in graph theory problems, secondly the questions in the Mathematics Olympiad are discussed from the degree, Euler circuit, Hamilton cycles and Hamilton Road and matching and the use of appropriate theory.

Key words: degree; Euler cycle; Hamilton cycle; Hamilton path; matching

目 录

一、 引言·····························································1 二、 数学竞赛中的图论问题·············································1 2.1度在数学竞赛中的应用·············································3 2.1.1度的基本概念和欧拉定理·········································3 2.1.2应用举例·······················································3 2.2欧拉回路和欧拉迹在数学竞赛中的应用·································6 2.2.1通路、迹、道路、闭通路、圈和连通图的基本概念····················7 2.2.2连通图的判断定理···············································8 2.2.3欧拉回路和欧拉迹的概念········································9 2.2.4欧拉回路和欧拉迹的判断定理····································9 2.2.5应用举例·····················································10 2.3哈密尔顿圈和哈密尔顿路在数学竞赛中的应用·························13 2.3.1哈密尔顿圈和哈密尔顿路·······································13

2.3.2应用举例·····················································14 2.4匹配在数学竞赛中的应用···········································16 2.4.1匹配的概念和hall婚配定理····································16 2.4.2应用举例·····················································17 三.结束语······························································18 参考文献·······························································19 致谢···································································20

一、引言

随着近几年数学竞赛逐步制度化、规范化的发展，数学竞赛在考试内容上也随之增多，在试题的覆盖面上也随之增广. 并且，数学竞赛更加考察考生的灵活运用数学知识的能力，而图论问题蕴含了丰富的思想、漂亮的图形和巧妙的证明，而且涉及的问题多且广泛，虽然问题外表简单朴素，但是本质上却十分深刻复杂，另外解决问题的方法千变万化，非常灵活，常常是一种问题一种解法，这些特点正是数学竞赛中所要体现的. 通过图论课程的学习，理解掌握图论的基本的思想方法，对于增进我们的数学应用意识，推进数学教学改革是十分有益的. 由于图论在考察青少年的数学洞察力、创造思维和数学的机敏等方面有独到的作用，因此图论问题一直受到数学教育界的青睐，一些高层次的数学竞赛中经常出现以图论知识为背景或运用图论思想方法来处理的问题，比如国际数学奥林匹克竞赛（IMO）第6届第4题，20届第6题，21届第2题，32届第4题，33届第3题等等.

不仅如此，在很多小学竞赛试题中，也常常出现要运用图论知识来解答的试题.

例如，在某小学数学竞赛试题中，出现了这样一个题：一天，小明做完作业正在休息，收音机中播放着轻松、悦耳的音乐.他拿了支笔，信手在纸上写了“中”、“日”、“田”几个字.突然，他脑子里闪出一个念头，这几个字都能一笔写出来吗？他试着写了写，“中”和“日”可以一笔写成（没有重复的笔划），但写到“田”字，试来试去也没有成功.这是怎么回事呢？这就是典型的一笔画问题.

另外，图论问题的许多经典问题还在数学竞赛中还有很多应用.下面我们就来具体的讨论一下数学竞赛中的图论问题.

二、数学竞赛中的图论问题

顾名思义，图论就是图的理论，它的基本研究对象就是图.那么什么是图呢？平面上给定n个点一个图，记作图G，

，，

，……，??

，其中某些对点之间用边相连，得到的就是叫做图G的顶点，其集合记作

. 图

1

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