浅析数学竞赛中的有关图论问题(2)
本文通过国内外数学竞赛中典型图论问题的研究 ，利用已有的研究结论如：文献[1]、文献[7]、文献[9]对数学竞赛中整数序列问题，赛程安排为题，人与人之间二元关系问题等有关度理论的试题进行了分析；文献[2]、文献[3]、文献[10]、文献[13]、文献[14]、文献[15]主要针对数学竞赛中的图论问题的研究背景做了论述；文献[4]相应研究了欧拉回路、欧拉图的发展以及数学竞赛中试题应用；文献[5]主要研究在平面图中的欧拉公式解决平面中简单图的最多边数问题；文献[6]分析研究了数学竞赛以及有关多人间关系的拉姆塞定理的应用；文献[8]主要解决哈密顿路、哈密顿回路解决数学竞赛试题的巧妙应用.
对于与图论相关的数学竞赛题若不启用图论知识则需要极强的空间思文记忆、构造能力，相对而言很难解决，而若运用图论的思想方法将问题进行转化，将实际问题转化为图，利用图的理论证明其结构则简化很多. 本文旨在通过分类整合数学竞赛试题中运用图论知识解决的问题，归纳总结图论中有关理论在数学竞赛中的重要应用，进而让学生更好的掌握图论知识，运用图论知识，为数学竞赛参赛者取得优异成绩打下良好的基础. 文章对数学竞赛试题的分析、阐述问题的解决过程，这对培养学生的数学洞察力、创造思文和数学机敏性；提高学习者分析问题，解决问题的能力；增强用数学的意识和能力都具有重要的意义.
1.预备知识
本文所研究的图均是无环、无重边的有限简单连通图.为了研究图论在数学竞赛中的应用，我们做了一些必要的准备工作.
定义1 图 中，与顶点 相关联的边数（每个环计算两次），称为顶点 的度，记为 ，分别用 表示 中顶点的最小度和最大度。度为零的顶点称为孤立顶点。我们把度为奇数的顶点称为奇点，度为偶数的顶点称为偶点.
定义2 如果图 中的每一对不同顶点恰有一条边连接，则称此图为完全图. 个顶点的完全图记为 .如图（2）一阶完全图 ,二阶完全图 ，三阶完全图 ，四阶完全图 .容易计算出 的边数是 .
定理1 对每一个图 ,均有 其中 表示图 的边数.
定理2 在任何图 中，奇点的个数为偶数.
定理3 非负整数序列 是某个图的度序列当且仅当 是偶数.
定理4 一个连通图 有 通路的充分必要条件是 中恰好有两个奇点.
定理5 拉姆塞（Ramsey）定理：设 ，则任何一个两色完全图 一定含有一个单色三角形.
定理6 如果 是平面图，则 .
定理7 （Euler公式）设 是一个有个 顶点、 条边和 个面的连通图，则 .
定理8 图 的顶点数为 ，且最小度 ，则 为哈密顿图.
定理9 一个非平凡连通图 是 图当且仅当图 没有奇点.
定理10 设 是 阶简单图，且对每一对顶点 有 ，则图 有哈密顿回路.
定理11 二部图 ，则 中有饱和 中的所有顶点的匹配 的充分必要条件为对 ，有 .( ).
文中涉及的符号若在预备知识中没有标注请参看文献4.
2. 图论在解数学竞赛题中的应用策略
2.1.度的相关理论在数学竞赛中的应用
问题的提出 上世纪90年代数学竞赛中经常出现的序列问题以及近几年来出现的的序列问题，近几年来出现的赛程问题、人与人之间相识与否等问题，若用图论中的度的相关理论来解决非常简单.如何在数学竞赛中，利用度的相关理论解决此类问题，提高做题的技巧、时间与效率，这是一个值得研究的问题.
上一篇：正定矩阵与矩阵的奇异值分解