08数学 080301048 李雅芳 图论
图论在数学竞赛中的应用
近年来图论问题在各种数学竞赛中频繁出现。一方面．图论研究迅猛发展，问题层出不穷；另一方面。图论问题可以用通俗的形式表达，没有太多的术语，也不需要艰深的理论。重要的是，图论灵活巧妙，作为竞赛试题最为合适。本文分别列举了图论中的度、哈密尔顿圈、哈密尔顿路在数学竞赛中的应用。 1度在数学竞赛中的应用
若干个点(称之为顶点)，有些点之间有边相连，这就构成了一个图G。而以点石为端点的边的条数称为点戈的度，记作cfG(菇)。如果图G的点可以分拆为两个点集X，Y。并且X的点之间没有边相连，Y的点之间也没有边相连。则图G称为二部图，记作G=(X，Y)。
定理1 图G中所有点的度之和等于边数的2倍。
例1 有7位男生与7位女生参加一次舞会，会后统计出各人的跳舞次数为(按从小到大的顺序)：
3，3，3，3，3，4，6，6，6，6，6，6，6，6 (1)证明其中必有错误。证明用点表示人。如果两个人跳过一次舞，就在相应的两个点之间连一条边。跳舞次数的和就是图中各点的度的和，而(1)中有5个奇数，总和为奇数。这与定理1矛盾!
例2在例1中。如果统计的跳舞次数为3，3，3，3，3，5，6，6，6，6，6，6，6，6，其中是否有错?这里约定男生不与男生跳舞。女生也不与女生跳舞。解我们用黑点表示男生，红点表示女生。在跳过舞的两个人之间用边相连(跳几次就连几次)。根据约定，黑点之间互不相连，红点之间也互不相连。所得图为二部图。显然所有黑点的度之和=所有红点的度之和=图中的边数(2)但题中给出的14个数中仅有一个数5不被3整除，这样(2)的一边被3整除；另一边恰有一个数不被3整除，从而不被3整除。矛盾
2哈密尔顿圈和哈密尔顿路在数学竞赛中的应用
如果在图G中．有一个圈经过每个顶点恰好一次．那么这个图称为哈密尔顿图，这样的圈叫做哈密尔顿圈。如果在图G中，有一条路经过每个顶点恰好一次，那么这条路称为哈密尔顿路。
定理2 图G的顶点数为v,(v≥3)，且最小度≥v/2，则G为哈密尔顿图。 例3亚瑟王在王宫中召见他的2n(n>1)位骑士。其中某些骑士之间互有怨仇。已知每个骑士的仇人不超过凡一1个，证明亚瑟王的谋士摩林能够让这些骑士围着那张著名的圆桌坐下，使得每一个骑士不与他的仇人相邻。
解 用v1,v2...v2n分别表示2n个骑士，若第i个和第j个骑士不为仇人，则连接i,j，所得图为G。因为每个骑士的仇人不超过n-1个，从而图中每个顶点的度≥(2n一1)一(n一1) =n。根据定理2可知，图G有哈密尔顿圈，即这些骑士围着圆桌坐下，使得每一个骑士不与他的仇人相邻。
除了以上举例，很多图论定理在数学竞赛中都可以编成有趣的问题，如欧拉图、生成树、竞赛图、Ramsey理论、染色等，在数学竞赛中巧妙运用。
