分类号 密级 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
[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
G所含的顶点个数n叫做图G的阶. 若干个点（称之为顶点）有些点之间有边相连，这就构成了一个图G. 而以点x为端点的边的条数称为点x的度，也叫顶x的次数，记作
v1 v2 v5 v1 e2 e3 e4 v2 v3 v4 v4 v3.
e1 图（1） x1
x2
x3
图（2）
K3，3
y1 y2 y3 y4 y5
图（3）
在图（2）中，连接顶点v1，v3的边共有三条：e1，e2，e3. 这样的边称为重边.在图里，有的边的两个端点重合，这样的边叫做环，例如图（2）中，边e4就是一个环.无环、无重边的图叫做简单图.例如图（1）和图（3）就是简单图，而图（2）则不是简单图.
设G是一个图，v是图G的一个顶点.图G中所有和v相邻的顶点的集合记作N（v），它叫做顶点v的邻域.所有以v为一端点的边数叫做顶点v的度，记作的d（v）.例如，图（1）中v1，v2，v3，v4，v5的度都为4，图（2）中，v1的度为6.注意环的度要算成2.对于简单图中任意顶点v，恒有0≤d（v）≤n-1.
设G是n阶简单图，如果G的任意两个顶点都相邻，则G叫做n阶完全图，记作Kn.例如图（1）就是5阶完全图K5.很显然，Kn的每个顶点的度都是n-1.顶点的度都是k的图叫做k正则图.
对简单图G，它的顶点集合V（G）可以划分为两个子集X和Y，使得X的
2
顶点之间以及Y的顶点之间都不相邻，而每条边的端点，一个在X中，另一个在Y中，则图G叫做二部图.例如，图（3）就是一个二部图.
设G是二部图，它的顶点集合V（G）可以划分为两个子集X和Y，使得X中每个顶点和Y的所有顶点都相邻，而X的顶点之间以及Y的顶点之间都不相邻，则G叫做完全二部图.如果X与Y所含顶点个数分别是|X|=n，|Y|=m，则记完全二部图G为Kn，m.例如图（3）就是完全二部图K3,5.
图的基本概念是从客观世界中抽象出来的.它提供了一种熟悉模型.在现实生活中可以找到很多图的例子.例如，在一个舞会上，参加舞会的任意两个人，要么相互认识，要么互不认识.要描述参加舞会的人民之间的相互认识关系就可以用图的概念.把参加舞会的人视为顶点，其集合记为V，对于u，v∈V，如果u和v所代表的两个人认识，则在顶点u和v之间连一条边，如果u和v所代表的两个人互不认识，则u和v之间不连边.这样就得到了图.
在熟悉了图的概念之后，就可以具体的介绍图论中的基本定理.
2.1度在数学竞赛中的应用
2.1.1 度的基本概念和欧拉定理
前面已经介绍了图论中的基本概念，因此，这里不再重复度的概念了.设图G是n阶图，在图G中得到的度和边数之间存在着密切的联系，即有下面的定理和推论.
定理1图G中所有点的度之和等于边数的2倍.
定理1是图论中最早出现的一个基本定理，它最早出现在著名数学家欧拉为解决哥尼斯堡七桥问题而撰写并于1736年发表的论文里，是解决哥尼斯堡七桥问题的主要依据.这个定理有许多重要的应用，因此，它是解决数学竞赛中有关问题的一个有力工具.
推论 图中奇次顶总数是偶数.
2.1.2 应用举例
例1 n人聚会，n>3，其中至少有一人没有和其他所有人握手.聚会中可能和
3
每个人都握手的人数之最大值是多少？（“希望杯”邀请赛试题）
解 由题意，把参加聚会的人视为顶点，其集合记作V，对于
，v∈V，如
果u和v所表示的两个人握了手，则令u和v相邻，得到n阶简单图记作G.则图G中至少有一个顶点u，使得
.这表明，图G不是完全图.
要求的是，聚会中和其他所有的人都握手的人数的最大值，即求图G中度为n-1的顶点个数之最大值.于是即求所有n阶非完全的简单图G中度为n-1的顶点个数之最大值m.
由于图G是非完全图，所以至少有两个顶点u和v是不相邻的，因此d(u)≤n-2，d(v)≤n-2.这表明，m≤n-2.
取一个n-2阶完全图Kn-2，另取两个顶点u和v.令Kn-2中每个顶点都和u与v相邻，而u与v不相邻，得到的图记作Kn-2+u+v.很明显，图Kn-2+u+v不是完全图，而且d(u)=d(v)=n-2，并且对除u，v外任意的顶点x均有d（x）=n-1.这表明m=n-2.即聚会中和每个人都握手的人数之最大值是n-2.
例2 有一个团体，由1982个人组成，其中任意四个人中都至少有一个人认识其他三个人.问该团体中认识其他所有人的成员最少有多少？（上海市竞赛题）
解 把该团体的成员视为顶点，其集合记作V.对于u，v∈V，如果u，v所表示的两名成员彼此认识，则令u和v相邻，否则令u和v不相邻，得到的是一个1982阶简单图G.由已知条件可知，如果1982阶简单图G的任意四个顶点中都至少有一个顶点和其他三个顶点相邻.求图G中至少有多少个度为1981的顶点？
当图G为完全图时，图G的每个顶点的度都是1981.所以有1982个度为1981的顶点.
当图G为非完全图时，图G中必有两个不相邻的顶点u和v，显然有d（u）≤1980，d（v）≤1980.因此，图G中度为1981的顶点的个数≤1980.如果图G中除u和v外还有两个顶点x和y不相邻，则u，v，x和y中不存在和其他三个顶点都相邻的顶点，与图G所具有的性质矛盾.因此图G中除u和v外任意两个顶点都相邻.这说明，对G中除u和v外的任意顶点x，都有d（x）≥1979.如果G中除u和v外的任意顶点x都和u与v相邻，则d（x）=1981.此时，G中度为1981的顶点个数为1980.设G中除u和v外有个顶点x和u与v不都相邻，则
4
有题意，G中除u，v和x之外的任意顶点y和u、v与x都相邻.因此，（u）d≤1980，d（v）≤1980，d（x）≤1980，且d（y）=1981.所以G中度为1981的顶点个数为1879,.这表明，如果1982阶简单图G中任意四个顶点中必有一个顶点和其他三个顶点都相邻，则G中至少有1979个度为1981的顶点.
所以，该团体中认识其他所有人的成员最少是1979.
例3 有7为男生与7为女生参加一次舞会，会后统计出各人的跳舞次数为（按从小到大的顺序）：
3，3，3，3，3，4，6，6，6，6，6，6，6，6 （1） 证明其中必有错误.（北京市竞赛题）
证明 用点表示人，如果两个人跳过一次舞，就在相应的两个点之间连一条线.跳舞次数的和就是图中各点的度的和，而（1）中有5个奇数，总和为奇数，这与定理1矛盾！
例4 在例3 中，如果统计的跳舞次数为3，3，3，3，3，5，6， 6，6，6，6，6，6，6，其中是否有错？这里约定男生不与男生跳舞，女生也不与女生跳舞.（北京市竞赛题）
解 我们用黑点表示男生，红点表示女生.在跳过舞的两个人之间用边相连（跳几次就连几次）.根据约定，黑点之间互不相连，红点之间也互不相连.所得的图为二部图，显然
所有黑点的度之和=所有红点的度之和=图中的边数 （2） 但题中给出的14个数中仅有一个数5不被3整除，这样（2）的一边被3整除；另一边恰有一个数不被3整除，从而不被3整除.矛盾！
例5晚会上大家握手言欢，试证握过奇次手的人数是偶数.（全国初中数学竞赛试题）
证 构作一图，以参加晚会的人为顶，仅当二人握手之时，在相应的二项间加一条边.于是没人握手的次数即为所造的图的相应顶之次数.由定理1的推论，奇次顶的个数是偶数，所以握过手的人数为偶数.
例6 大于7公斤的整公斤的重量都可以仅有一些3公斤和5公斤的两种砝码来称量.（《学校报》公开赛试题）
证 只需证明对任意给定的自然数n，存在二部图G(n)，其中X顶子集有n
5
个顶点，每顶都只有一次，Y顶子集中的项是3次或5次的.
下面用数学归纳法证明之：
当n=8时，结论显然成立，如图（4）
x1 x2 x3 x4 x5 x6 x7 x8 y1 y2
假设对于此，在
的
,结论以成立，顶子集中添加一项
图（4）
. 以下证明对，结论仍成立. 为
的
中顶是3
；由归纳法假设，在
次或5次的，分以下两种情形讨论：
(i)若
中皆三次顶，去
，
，,将其重合成一个顶
,再于
与
之间连一条边，最后把劈开成两个5次顶，则得满足要求的
(ii)若Y中有5次顶，设d(yi)?5，在yi与xk?1之间连一边，再把yi劈开成两个3次顶，则得满足要求的二分图G?k?1?.证毕.
2.2欧拉回路和欧拉迹在数学竞赛中的应用
在上节已经提到，度的概念和欧拉定理是著名数学家欧拉为解决所谓哥尼斯堡七桥问题而提出的.古城哥尼斯堡位于普瑞格尔河的两岸及河中的两个岛上，城市的各个部分由七座桥连接.十八世纪，哥尼斯堡属于东普鲁士（纤维苏联的加里宁格勒）.那时候，哥尼斯堡市民生活富足.每到星期天，市民们喜欢四处散布.于是便产生了这样的问题：是否可以设计一种方案，使得人们从家里出发，经过每座桥恰好一次，最后回到家里.尽管许多人试图解决这个问题，但是谁也
6
没有答案.
哥尼斯堡七桥问题引起了欧拉的兴趣.他从人们的失败中敏锐地领悟到，也许那样的方案根本就不存在.1736年，年方二十九岁的欧拉终于解决了这个问题，并在彼得堡科学院报告了自己的结果.欧拉的文章不仅仅是解决了一个难题，而且标志着一个新的数学分支——图论的创立.这一部分将介绍欧拉的研究结果.为此，我先来介绍一些基本的术语.
2.2.1 通路、迹、道路、闭通路、圈和连通图的基本概念
x1 e1 x2 e8 e2 x3 e5 e6 e7 e3 x5
e4 图（5）
x4
设G是一个图，x0，x1，···，xk是图G的某些顶点.如果图G含有边e1=x0x1，e2=x1x2，···，ek=xk-1xk，则由x0，x1，···，xk和e1，e2，···ek组成的点边交错序列（x0，e1，x1，e2，x2，···，xk-1，ek，xk）叫做图G的一条长为k的通路，记作x0x1x2···xk.如果一条通路中所有的边都不同，则称它是一条迹，如图（5），x1e1x2e8x2x4就是一条迹.如果通路中所有的顶点都不同，则称它是一条道路，则图（5）中x1e1x2x4x5是一条道路，始点和终点重合的通路叫做闭通路，则图（5）中x1e1x2e8x2x4x5e5x1是一条闭通路，如果一条闭通路除始点和终点相重合外，其他顶点都不相同，则称它为圈，则图（5）中x1e1x2x4x5e5x1是圈.
设G是一个图，如果图G是一阶图，或者图G的阶大于1，并且对图G中任意两个顶点u和v，总有一条以u为始点且以v为终点的通路，则图G叫做连通图，否则图G叫做不连通的.图（5）就是一个不连通的
根据直观感受，可以想到，对给定的图G，它的顶点的度越大，它的边数也
7
就越大，任意两个顶点之间的通路相连接的可能性就越大，因此图G越有可能是连通的.当然，这仅仅是一种直观的想象.事实上，图G的连通性和它的顶点的度之间确实存在密切的联系.
2.2.2 连通图的判断定理
定理2设G是n阶简单图.如果图G中顶点的最小度则图G是连通的.
例7 有2n部电话交换台，每部电话交换台都至少和n部电话交换台有直接线路连接.证明，其中任意两部电话交换台都可以进场一次通话（允许通过别的交换台）.（“希望杯”邀请赛试题）
证明：用顶点表示交换台，其集合记作V.对于u，v∈V，当且仅当u和v表示的两部交换台有直通线连接时令u和v相邻，得到的是2n阶简单图.
由于每部交换机都至少和n部交换台连接直通线路，所以图G中每个顶点的度至少是n.即图G的顶点的最小度
.由定理2，图G是连通的.
满足
，
于是由定义，对图G中任意两个顶点u和v，总有一条以u为起点且以v为终点的通路x0x1···xk，其中x0=u，xk=v，由于连接顶点xi+1和xi（i=1，2，···，k）的边即是交换台xi+1和xi的直通线路，所以只要接线人员按照直通线路x0x1，x1x2，···，xk-1xk的顺序接线，则交换台u和v就可以实现一次通话.
例8 圆周上有13个点，能否用自然数1，2，3，···，13给这些点编号，使得任意两个相邻的点的号码之差的绝对值至少是3，最多是5？（1986年匈牙利数学竞赛试题）
解 答案是“不能”.现在用反证法证明之.
假设存在一种编号方法，使得任意两个相邻的点的号码之差的绝对值至少是3，最多是5，把圆周上13个点视为13个顶点，其集合记作V.对于顶点u和v，当且仅当u和v所表示的两个点相邻时令顶点u和v相邻，得到的是一个长为13的圈C13.很明显，C13是连通的.用顶点所表示的点的编号表示顶点.将顶点集合V分划为两个子集X={1，2，3，11，12，13}和Y={4，5，6，7，8，9，10}.
由于C13是一个圈，所以每个顶点的度都是2，又集合X中任意两个顶点都
8
不相邻，所以X的顶点和Y的顶点之间恰连有12条边，而C13恰有13条边.因此Y的顶点之间必有一条边.Y中的顶点4在X中只和顶点1相邻，由于顶点4的度为2，所以顶点4必和Y中另一个顶点相邻.同理.Y中顶点10必和Y中另一个顶点相邻.但是顶点4和10不相邻.这表明，Y中顶点之间至少连有两条边，矛盾.因此不存在合乎条件的编号方式.
2.2.3 欧拉回路和欧拉迹的概念
在熟悉了图的连通概念之后，现在再来谈谈欧拉关于哥尼斯堡七桥问题的研究.首先，把哥尼斯堡管辖只下的四个城区A，B，C，D视为4个顶点，连接城区的没做桥都视为边，得到的是4阶图G（图（6））.于是问题化为：从图G中每个顶点出发，能否存在一条通路，经过每条边恰好一次，然后回到原来的顶点.换句话说，图G中是否含有图G所有的边的回路.
D
A C
B
图（6）
一般来说，n阶图G中含有所有边的回路叫做欧拉回路.具有欧拉回路的图G叫做欧拉图.则问题进一步转化为：图（6）中的四阶图是否是欧拉图.
欧拉图和所谓的一笔画问题有着密切的联系.所谓一笔画问题就是，纸面上给定的一个图G,能否从图G的一个顶点出发，笔不离开纸，而且连续地沿着每条边恰好一次，然后回到原来的顶点，从而画出整个图G？很显然，如果图G是欧拉图，则可以一笔画出整个图G，否则就不能.图（6）不是欧拉图，则不能一笔画出整个图G.
2.2.4欧拉回路和欧拉迹的判断定理
定理3 设G是连通图，则G为欧拉图的充分必要条件是，图G中的每个顶点的度是偶数.
9
有了定理3，哥尼斯堡七桥问题的答案就是显而易见的.从图（6）可以看出，其中的图G是连通的，而且图G中每个顶点都不是偶顶点，因此，由定理3，图G不是欧拉图，也就是说，哥尼斯堡七桥问题的答案是：不可能.
既然哥尼斯堡七桥问题不能得到肯定的答案，那么是否可以退而求其次呢？即考虑如下的问题：能否从哥尼斯堡某个城区出发，经每座桥恰好一次，然后达到另一个城区？
那么这个问题就相当于是对于给定一个图G，对其中某个顶点u，是否存在以u为端点的一条迹，使得图G中每条边恰好在其中出现一次.如果这样的迹存在，则称它为图G的一条欧拉迹.欧拉迹和欧拉回路的差别在于，欧拉回路是一条闭通路.
定理4 设u和v是连通图G的两个不同顶点，则图G具有一条连接顶点u和v的欧拉迹的充分必有条件是，u和v是奇顶点，其他所有顶点都是欧拉点.
综合定理3和定理4，可得到以下的推论.
推论 有限图G 可以一笔画成的充要条件是G是连通的,且奇顶点的个数为0或2. 当且仅当奇顶点个数为0时,连通图G是一个圈.
由推论可以看出，所谓的退而求其次形式的哥尼斯堡七桥问题的答案也是否定的，因为图（6）中的图G中不含有偶顶点.
2.2.5应用举例
例9一天，小明做完作业正在休息，收音机中播放着轻松、悦耳的音乐.他拿了支笔，信手在纸上写了“中”、“日”、“田”几个字.突然，他脑子里闪出一个念头，这几个字都能一笔写出来吗？他试着写了写，“中”和“日”可以一笔写成（没有重复的笔划），但写到“田”字，试来试去也没有成功.这是怎么回事呢？（小学奥林匹配竞赛试题） a c b g a b a c d b c f d d e h f g e h i e 图（7）
f 图（9）
10
图（8） 解 把“中”这个字的每一个重合的地方看作顶点，如图（7）所示，分别把各个顶点记作a、b、c、d、e、f、g、h.由图可知，各个顶点的度依次为2、4、2、2、4、2、1、1，则可以知道它其中的6个顶点的度为偶数，另外两个为奇数，即奇顶点的个数为2，由推论可知，“中”字可以一笔画成，且起点和终点分别为g和h（或h和g），则可按图（10）所示方法一笔画成（方法不唯一）,即从g b c f e d a b e h.
a d 图（10） e h f d e h f d e h f g b c a g b c a b c g 同样的，把“日”的每一个重合的地方看作顶点，如图（8）所示，分别把各个顶点记作a、b、c、d、e、f.由图所知，各个顶点的度依次为2、2、3、3、2、2，则可以知道它的各个顶点中有两个奇顶点和四个偶顶点，由推论可知，“日”可以一笔画出，且起点和终点分别为c和d（或d和c），则可按图（11）所示方法一笔画出（方法不唯一）,即c a b d c e f d.
a c b d a c b d c a b d e
f e 图（11）
f e f 把“田”这个字的每一个重合的地方看做顶点，如图（9）所示，分别把各个顶点记作a、b、c、d、e、f、g、h、i.由图所知，各个顶点的度依次为2、3、2、3、4、3、2、3、2，则可以知道它的各个顶点中有四个奇顶点和五个偶顶点，由图论可知，“田”不能一笔画出.
11
例10指出图（12），图（13）和图（14）中哪一个图，可以从图中的某个点出发，用铅笔不离开纸面，一笔画出整个图？
A
x
B
F
D
E
y
C
图（12）
图（13）
x
A z
w y
B F
图（14） C D
E
图（15）
解 把图（12）中圆周的交点视为顶点，其集合记V.对于顶点u，v∈V，当
且仅当交点u和v有圆弧相连接时令顶点u和v相邻，得到的是6阶图G1（图（15））.图G1中每个顶点的度都是4，由定理3，图G1具有欧拉回路.因此，可以从图（12）中的某个交点出发，按照一条欧拉回路上顶点的顺序，沿着圆弧，一笔画出整个图，最后回到原来的交点上.
把图（13）中的交点视为顶点.当且仅当交点间有线段连接时，令相应的顶点相邻，得到的图记作G2,.图G2中恰有两个3度顶点x和y，其他顶点都是偶顶点，有定理4，图G2含有一条以x和y为端点的欧拉迹，于是，从点x出发，按照这条欧拉迹中顶点的顺序，一笔画出整个图，最后到达点y.
和图（13）相似，图（14）中含有四个奇顶点x，y，z和w，因此不能一笔画出图（14）.
例11 圆周上有n个点，n>2，其中任意两点都用线段连接.能否一笔画出所
12
有这些线段，使得第一条线段的终点和第二条线段的始点相重合，第二条线段的终点和第三条线段的始点相重合，等等，而且最后一条线段的终点和最初的一条线段的起点相重合？
解 把圆周上给定的n个点视为n个顶点，任意两个顶点都相邻，得到的是一个n阶完全图Kn，Kn中每个顶点的度都是n-1，当n为奇数时，Kn中的每个顶点都是偶顶点.因此，有定理3，完全图Kn含有欧拉回路，因此，从Kn中某个顶点出发，按照这条欧拉回路上顶点的顺序，即可一笔画出整个图Kn，最后回到原来的顶点上.当n为偶数时，Kn中每个顶点都是奇顶点，由定理3和定理4，完全图Kn不含欧拉回路和欧拉迹.因此，偶数阶完全图Kn不能用一笔画出所有线段.
2.3哈密尔顿圈和哈密尔顿路在数学竞赛中的应用
哈密尔顿是十九世纪英国著名数学家.1859年，他发明了一种游戏.这种游戏使用一个实心的正十二面体，在它的二十个顶点上标注着世界上二十个著名城市的名字：阿姆斯特丹，安亚伯，柏林，布达佩斯，都柏林，爱丁堡，耶路撒冷，伦敦，墨尔本，莫斯科，新西伯利亚，纽约，巴黎，北京，布拉格，里约热内卢，罗马，旧金山，东京和华沙，要求游戏者寻找一条环路，使得从某个城市出发，能够沿着正十二面体的棱前进，经过每座城市恰好一次，然后回到原来的城市.
这种游戏可以抽象为图论问题，把正十二面体的顶点视为图G的顶点，把正十二面体的棱视为图G的边，得到一个图G.于是，此游戏相当于，在图G中寻找一条道路，使得从图G中某个顶点出发，沿着图G的边，经过图G的每个顶点恰好一次，然后回到原来的顶点，也就是寻找一个经过每个顶点恰好一次的圈.这样的圈叫做图G的哈密尔顿圈.
下面我们就来介绍一下哈密尔顿圈和哈密尔顿路的基本概念.
2.3.1哈密尔顿圈和哈密尔顿路
如果在图G中，有一个圈经过每个顶点恰好一次，那么这个图称为哈密尔顿图. 这样的圈叫做哈密尔顿圈. 如果在图G，有一条路经过每个顶点恰好一次，那么这条路称为哈密尔顿路.
哈密尔顿提出了图论研究的一个重要课题，即如何判断一个图是否是哈密尔
13
顿图.表面上看，哈密尔顿圈和一笔画很相似，其实质却迥然不同，对于图G的哈密尔顿圈C，只要求图G的每个顶点都在圈C上出现，而且只出现一次.至于图G的边，则不作任何要求，即允许在圈C上出现，也可以再圈C上不出现.对于图G的欧拉回路C*，则正相反，它要求图G的每条边都要在回路C*上出现一次，而且只出现一次，而对图G的顶点，则不计其出现与否.前面已经知道判断一个图是否是欧拉图问题已经彻底、干净的解决了.但判断一个图是否是哈密尔顿图问题，至今仍未解决.它是图论问题的一个难题，是世界各国许多图论专家所关注的研究课题之一.在这里，我只介绍一个比较简单、比较实用的定理.
定理5 设G是n阶简单图.如果对图G中任意两个不相邻顶点u和v，均有
, （3）
则图G是哈密尔顿图.
推论 图G的顶点数为
,且最小度
,G为哈密尔顿图.
2.3.2应用举例
例12 传说英国有一位国王，叫亚瑟王，在王宫中召见他的2n名骑士，其中某些骑士之间互有仇怨.已知每名骑士的仇人不超过n-1个.证明，亚瑟王的谋士摩尔林一定有办法让这2n名骑士围着圆桌入座，使得每名骑士都不和他的仇人坐在一起.（波兰数学竞赛试题）
证 用顶点表示骑士，当且仅当骑士x和y互不成仇时顶点x和y相邻，得到的2n阶简单图记作G.由于每名骑士的仇人不超过n-1个，所以图G中每个顶点的度都至少是n.由定理5的推论，图G是哈密尔顿图，即图G具有哈密尔顿圈.于是只要让这2n名骑士按照这条哈密尔顿圈的顶点顺序就座，每名骑士两旁就座的就不是他的仇人.
例13 有n个人，围圆周入座，n≥5.证明，可以调整这n个人的座位，使得每个人的两旁就座的是原来不坐在一起的人.（“祖冲之杯”邀请赛试题）
证 假设围着圆桌入座的n个人按逆时针的顺序是v1，v2，···，vn，（图（16））.把n个人v1，v2，···，vn视为n个顶点，对于顶点u，v∈V，当且仅当u和v不坐在一起时令u和v相邻，得到的是n阶简单图G.
14
v1
v2
vn
v1
v3 vn-1 v2
v5
v3
v4
图（17）
图（16）
很显然，图G中每个顶点的度是n-3.当n≥3时，n-3≥n-= 因此由定理5的推论，图G具有哈密尔顿圈.于是，只要让这n个人按照这条哈密尔顿圈上的顶点顺序就座即可.当n=5时，图G如图（17），很显然，图G具有哈密尔顿圈v1v3v5v2v4v1，此时只要让这5个人按照顶点顺序v1，v3，v5，v2，v4入座即可.
例14举行一个国际会议，有A，B，C，D，E，F，G 7个人.已知下列事实： A会讲英语； B会讲英语和汉语；
C会讲英语、意大利语和俄语； D会讲日语和汉语； E会讲德语和意大利语； F会讲法语、日语和俄语； G会讲法语和德语.
试问这7个人应该如何安排座位，才能使每个人都能和他身边的人交谈？（小学奥林匹克数学竞赛试题）
解 依据已知条件建立一个图的模型，我们用点表示人，于是得到点集V={A，B，C，D，E，F，G}.对于任意两点，若有共同语言，就在他们之间连一条线，可以得到边集E，则图G=（V，E），如图（18）：
15
A
B
C
E
D
F
G
图（18）
如何排座位使每个人都能喝他身边的人进行交谈？则问题转化为：在图G
中找一条哈密尔顿回路的问题.而A-B-D-F-G-E-C-A即是图中的一条哈密尔顿回路.照这个顺序安排座位就可以解决问题.
2.4匹配在数学竞赛中的应用
2.4.1匹配的概念和hall婚配定理
有个工厂，用六种颜色的纱生产双色布，每种颜色至少和其他三种颜色搭配.要求证明，一定可以找出三种不同的双色布，它们包含全部六种颜色.也就是说，按照所找到的三种不同双色布，每种颜色可以和另一种颜色配对，使得配对的对子不含相同颜色，这样就使每种颜色和跟它配成对子的颜色相匹配.用图论语言来说，就是要证明：如果6阶简单图G中每个顶点的度至少是3，则图G含有三条边，其中任意两条边都没有公共端点.设图G的三条边是e1，e2，e3，边ei的端点分别是u2i-1，u2i，i=1，2，3.则图G的6个顶点u1，u2，···，u6便按照e1，e2，e3配成对子：（u1，u2），（u3，u4），（u5，u6）.于是顶点u2i-1，u2i是匹配的，i=1，2，3.
一般的说，设G是n阶简单图，M是图G的某些边组成的集合.如果集合M中任意两条边都没有公共端点，则集合M叫做图G的一个边无关集.设u和v是图G的顶点.如果u和v是边无关集M的某条边的两个端点，则说顶点u和v在边无关集M下是匹配的.对于图G的一个匹配M，如果图G的每个顶点都在M下和另一个顶点匹配，则M叫做图G的完全匹配.如何判断一个简单图是否具有完美匹配，是匹配理论的中心问题之一.在匹配问题中，主要关心的是二部分图.具体地说，设图G是二部分图，X和Y是图G的顶点集合V的一个划分，
16
其中X中顶点之间以及Y中顶点之间都不连边.如果图G具有匹配M，使得X中每个顶点在M下都和Y中顶点匹配，则说X可以匹配到Y中，对给定的二部分图G，如何判断集合X是否可以匹配到集合Y中呢？下面给出匹配问题的判定定理.
定理6（hall婚配定理） 设G是二部图，顶集的二部图划分为X和Y，即V（G）=X∪Y，X∩Y= ? ,X中无邻顶对，Y中亦然，存在把X中顶皆许配的匹配的充分表条件是成的所谓S的邻集.
推论 k次正则二部图有完备匹配，k>0.
匹配理论有着广泛的应用.在数学竞赛例经常遇到它.
SX，|N（S）|≥|S|，其中N（S）是S中每个顶的邻顶组
2.4.2应用举例
例15 动物运动会进行归途100m×2赛跑，每只乌龟认识10只兔子，每只兔子认识10只乌龟.乌龟们都要求和自己朋友（相识者）组队（每对一龟一兔），参赛，问是否能如愿？若能如愿，这种比赛能进行几轮，使得每轮比赛每只龟兔都去参赛，且每对龟兔至多只许参赛一次.（湖北省黄冈市竞赛题）
解 以兔组成X集，龟组成Y集.仅当龟兔认识时，在相应的顶间连一条边，构成一个10次正则二部图.由推论，G中有完备匹配M1，按M1的匹配方式组队进行第一轮比赛.把M1的边从G中删除，得9次正则图G1，同理可组织第二轮比赛.依次类推，可组织10轮比赛，每对龟兔朋友都合作过一次.
例16 有n位绅士和n为太太参加一次舞会，每位绅士恰好认识位太太，每位太太也恰好认识位绅士.证明可以适当安排，使得每位太太均与他认识的绅士跳舞.（“五羊杯”竞赛试题）
解 绅士、太太均用点表示，分别组成点集X，Y，在相识的人之间连线，得二部图G（X，Y），每个点的度数均为
，且可知G（X，Y）是一个正则二
部图，要使每位太太与她认识的绅士跳舞，即转化为证明G中存在一个完备匹配M.由推论4，G（X，Y）中必存在一个完备匹配.
例17有一个谍报小组，共有5名成员，他们的满足分别是：abc，bc，dab，df和fe.现在要问，能否从每个人的名字里各取出一个字母，作为彼此联络的代
17
号？（“新蕾杯”数学竞赛试题）
解 把5个名字看出5个顶点，其集合记作X.把5个名字中所以的字母也都看成顶点，其集合为Y.对集合X中的顶点x和集合Y中的顶点y，当且仅当字母y出现在名字x中时，令顶点x和y相邻同一个集合的顶点之间不相邻，得到的二部图记作G（图（19））.
图G中边e1，e2，e3，e4和e5（图（14）中的粗线边）组成图G的一个匹配M.在M下，名字ace，bc，dab，df和fe依次与字母a、b、d、e和f相匹配.因此可以用字母a、b、
d、e和f分别作为名字ace、bc、dab、df和fe的代号.
df fc
e4
e5
ace bc dab
e3 e2 e1
a b
c d e f
图（19）
三、结束语
文中只是简单的介绍了图的基本概念，然后结合度、欧拉回路、哈密尔顿圈与哈密尔顿路和匹配的基本定理，并结合该定理与数学竞赛中的试题进行了讨论. 除了以上的举例之外，还有很多图论定理在数学竞赛中都可以变成有趣的问题，如生成树，竞赛图，染色等，在数学竞赛中都有巧妙的运用，这些问题在文中并没有涉及到.并且，图论问题中仍然还有许多问题并没有干净、漂亮的解决，还需要很多研究者不断的研究和发现图论问题中的奥妙.
18
参考文献
[1]王树禾.图论.北京：科学出版社,2009
[2]王树禾.图论及其算法.合肥：中国科学技术大学出版社，1990 [3]王树禾.从哥尼斯堡七桥问题谈起.长沙：湖南教育出版社，1999 [4]徐俊明.图论及其应用.安徽：中国科技技术大学出版社，2010 [5]王朝瑞.图论.北京：人民教育出版社，1981
[6]Andrasfai B.图论导引.郭照人译.北京：高等教育出版社，1980 [7]Harry F.图论.李慰萱译.上海：上海科学技术出版社，1980
[8]叶其孝等.大学生数学建模竞赛辅导教材.长沙：湖南教育出版社，1998 [9]李尚志，王树禾等.数学建模竞赛教程.南京：江苏教育出版社，1996 [10]学而思培优教研部.小学奥数系统总复习上册.北京：西藏人民出版社，2012
[11] 学而思培优教研部.小学奥数系统总复习下册.北京：西藏人民出版社，2012
[12]黄东坡.数学培优竞赛新帮手初三年级.湖北：湖北辞书出版社，2002 [13]陈传理，刘玉翘等.高中数学竞赛名师指导第二册.武汉：华中师范大学出版社.2001
[14]钱展望，朱华伟.奥林匹克数学训练题集初二分册.武汉：湖北教育出版社，2002
[15] 钱展望，朱华伟.奥林匹克数学训练题集高一分册.武汉：湖北教育出版社，2002
19
致谢
在本论文完成之际，我要向所有帮助过我的老师、同学表示衷心的感谢！我要特别感谢我的指导老师孙静老师的热情关怀和悉心指导.在我撰写论文的过程中，孙静老师倾注了大量的心血和汗水.从开题报告的修改、论文的架构拟定到最终定稿，她给予了殷切的指导，提出了许多宝贵的意见.无论是在论文的选题、构思和资料的收集方面，还是在论文的研究方法以及成文定稿方面，我都得到了孙静老师悉心细致的教诲和无私的帮助，特别是她广博的学识、严谨的治学精神和一丝不苟的工作作风使我受益匪浅，在此表示真诚地感谢和深深的谢意.
20