论文总字数：6281字

摘 要

图论是应用数学的一部分，主要研究离散结构的相互关系及性质. 图论的知识点在中学数竞赛中有很广的应用. 论文主要介绍了图论中一些重要结论及其在中学数学竞赛中的应用. 对数学竞赛中图论知识点的应用有一定的指导与参考价值.

关键词：图论，中学数学竞赛，握手定理，图的关联矩阵

Abstract： Graph theory is a part of applied mathematics, which mainly studies the relations and properties of discrete structures. The knowledge of graph theory is widely used in the number contest of middle school. This paper mainly introduces some important conclusions of graph theory and its application in middle school mathematics competition. It has certain guidance and reference value to the application of graph theory knowledge points in mathematics competition.

Keywords： graph theory, middle school mathematics competition, handshake theorem,

incidence matrix of a graph

目录

1．前言 4

1.1研究背景 4

1.2研究意义 4

1.3研究方法 4

2．图论的特点 4

2.1图论简约性 4

2.2图论加“权”性 4

2.3图论的趣味性 4

3.图论的相关概念 5

3.1图 5

3.2度 5

3.3中学数学竞赛中的握手定理 5

3.4图的关联矩阵 7

3.5关联矩阵与中学数学竞赛 8

3.6二部图及匹配 9

结 论 12

参 考 文 献 13

致谢 14

1．前言

1.1研究背景

图论是应用数学的一个分支，它在很多领域都有应用比如计算机科学，运筹学，物理化学等等. 图论在当代逐渐成为一个热门学科，各大高校也将图论纳入了教程^[2].

1.2研究意义

掌握了图论的相关知识，对于数学的学习将会起到事半功倍的作用，也可以解决生活中的一些分配问题^[5].

1.3研究方法

（1）文献资料法.通过参考，学习大量相关的文献资料，从而找出与课题相关的研究成果.

（2）比较研究法.对比研究是一种重要的研究方法，有对比才能充分认识哪一种方法好.

2．图论的特点

2.1图论简约性

图论的简约性是将数学问题转化为“有向图”来思考,使抽象的问题具体化以便学生更好的理解 ,在中学数学的学习中数形结合就是典型证明，一般我们拿到一道题不知怎么样下手时，若把问题转化为图则很容易解决，但学生不容易想起这个方法，教师需要加强培养. 2.2图论加“权”性

.

.

2.3图论的趣味性

早期的图论问题都是十分的有趣就比如我们大家所知道的著名的“七桥问题”，“四色问题”等等，这些问题比较经典较容易解决，而且又乐趣十足，很适合培养学生的思维能力、构图能力和动手能力^[1].

3.图论的相关概念

3.1图

将点,,,用连线,,,,连接起来就构成了一张图（如图一），这些点称为顶点,连线称为边,用代表图,

,,

则可用表示该图.

3.2度

出度:与顶点相连的边数称为该定点的度数,以该定点为始边的边数为出度,入度:以该定点为终边的边数为入度.

3.3中学数学竞赛中的握手定理

定理1：设是阶图，则中个顶点的度之和等于边数的两倍. 即 (为边数)^[4].

定理1：又可以叫做“握手定理”，关于“握手定理”我们可以用它来解决一个实际问题，下面举一个实例.

例1：某班一个小组有4个人，每两个同学握手一次，则一共握手一次、

分析:将这四个人标号记为

方法一:将这些同学的握手次数列举出来则有：,所以一共握手6次.

方法二:数形结合，将4个人看做四边形的四个顶点然后连接，如图所示：

总结：从这两种方法可以看出对于简单的握手问题列举法与数形结合都可以，都可以很快的解决问题,但是对于复杂的握手问题，列举法可能就不是那么好用了，下面看个例子.

例2：林氏夫妇邀请另外两队夫妇来聚餐，餐会上林先生说假设每个人都不和自己握手，不和自己的配偶握手，每个人最多同时和一个人握手一次，吃完饭后，林先生问大家握了几次手，每个人答案都不一样，那请问究竟林太太握了几次手？

解：分析：根据这个问题我们发现如果直接想林太太握了几次手，那不容易想出来且答案不一定对，为此我们可以建立一个模型，这个模型的建立需要根据问题。在这个问题中一共有6个人，去除林先生还有5个人，在这5个人中最多握手4次，这5个人的握手次数把它统计在下表中.

剩余5人的握手次数分布表

根据这个表分析，因为夫妻之间不握手而且握手次数最多，因而可以知道和是一对夫妻，排除一对夫妻后在剩下的3个人中找林太太，剩余3个人每个人的握手次数都应该减少一次，握手结果有下表可知.

剩余3个人的握手次数分布表

由这张表可以看出来和是一对夫妻，由此可以知道是林太太，所以林太太握了两次手.

例3：一位先生说；“前段时间我与太太一起参加了一个派对，派对上还有另外四对夫妇，出于礼貌大家见面相互握手，我们假设没有人同自己的太太握手，自己也不会跟自己握手，而且不能跟同一个人握两次手，在握完手之后，我问大家各握了几次手，然而每个人答案都不一样？”那么究竟这位先生太太握了几次手.

剩余内容已隐藏，请支付后下载全文，论文总字数：6281字