论文部分内容阅读
【摘要】 图论作为一门数学分支历史悠久，从哥尼斯堡城的七桥问题至今，发展迅速，也受到数学竞赛的青睐。本文从2016年数学联赛的第三题谈起，介绍了图论的相关概念及一般的解题方法，最后再给出该题的较为简便的解法。
【关键词】图论问题 数学竞赛 解题方法
【中图分类号】G633.6 【文献标识码】A 【文章编号】2095-3089（2017）07-0123-02
圖论作为一个重要的数学分支，几千年前，我国的河图、洛书就已经涉及到一些简单有趣的图论问题。18世纪，哥尼斯堡七桥问题使得图论作为一门真正的学科进入学者们的视野。而近二十年来，由于计算机科学、编码理论、规划论、数字通讯、实验设计等学科的迅猛发展，提出了一系列的需要离散数学解决的理论和实际问题，使得图论的研究更为活跃。由于图论蕴含的数学思想丰富，图形简洁美观，证明巧妙，方法千变万化，非常灵活，因而备受数学竞赛的青睐。今年的高中数学联赛加试第三道题就是一道以图论为背景的题：
给定空间中10个点，其中任意四点不在一个平面上，将某些点之间用线段相连，若得到的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大值。
在解决这道图论问题前，我们先来介绍一下图论的一些定义和概念：
一、图论相关的基本定义和基本概念
图由一个点集合V和一个连接某些点对的线段的集合E构成的图形称为图。记作G（V，E）.其中，V中的点称为顶点，E中的线段（不一定是直线段）称为边。通常|V|和|E|表示顶点个数和边的数量。有n个顶点的图称为n阶图。值得注意的是图中顶点一定不能为空，而边可以为空。
为了研究图的相关性质，我们还需要一些图的相关概念：
度：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d（v）
平行边：若有若干条边连着相同的两个顶点，则称这些边是平行边
环：两端连接着同一端点的边称为环
简单图：既不含平行边也不含环的图称为简单图
完全图：任意两个顶点间都有边相连的简单图称为完全图，n阶完全图记为Kn
在高中数学竞赛中，常见的都是简单图。
二、解决图论问题的基本方法
在常见的图论问题中，我们主要研究一个图的边数，顶点数，这自然离不开计数方法的运用，使用最频繁的当属富比尼原理，这通常通过对顶点的度与图的边数的两次计数来实现。而其他如反证法、数学归纳法、抽屉原理等方法在图论中也有丰富的应用。
例题：
例1（1985年全国高中数学联赛试题）某足球邀请赛有十六个城市参加，每市派出甲、乙两个队，根据比赛规则，比赛若干天后进行统计，发现除A市甲队外，其它各队已比赛过的场数各不相同.问A市乙队已赛过多少场？请证明你的结论。
证明：用32个点表示这32个队，如果某两队比赛了一场，则在表示这两个队的点间连一条线，否则就不连线。
由于，这些队比赛场次最多30场，最少0场，共有31种情况，现除A市甲队外还有31个队，这31个队的比赛场次互不相同，故这31个队比赛的场次恰好为0到30场，就在表示每个队的点旁注上这队的比赛场次。
考虑比赛场次为30的队，这个队除自己与同城的队外，与不同城有队都进行了比赛，于是，它只可能与比赛0场的队同城；去掉这两支队伍以及这两支队伍的比赛场次（即这时候其他队伍的比赛场次都减少1），在剩下的30支队伍中，再考虑比赛28（29-1）场的队伍，这个队除与同城队不比赛外，与其他队伍都比赛过了，原先赛了1场的队此时记为0场了，同理，它和赛了29场的是一个城市的；依次类推，知比赛k场的队与比赛30-k场的队同城，这样，把各城都配对后，只有比赛15场的队没有与其余的队同城，故比赛15场的队就是A城乙队。即A城乙队比赛了15场。
该题是一道典型的顶点的度的应用，转化成图论问题之后，使我们对条件的理解更加直观，清晰了解题思路。
例2：证明任意六个人中，必有三个人相互认识或三个人相互不认识？
这道题将它用图论的语言转述即为：将一个6阶的图用两种颜色把其中的点两两连线（认识和不认识分别代表两种颜色），必有一个同色三角形。这就是著名的Ramsey定理。一种较为常见证明的过程是对由一个顶点出发对同色边的条数运用抽屉原理进行讨论，在此不再赘述。有趣的是，如果转而对同色角的个数去讨论，我们能得到一个更强的结论：
对K6完全图二染色，一定存在两个同色三角形
证明：由一个顶点出发，引出5条边，则以每个顶点可做出C个角，至少有4个两边同色的角，故图.K6中至少有24个同色角。而每个同色三角形有3个同色角，不同色的三角形有1个同色角。K6中一共有20个三角形。因此，至少有两个同色三角形。
在解决一些图论问题中，我们还需要用到一些图论的定理。
三、一些图论的基本（著名的）定理
1.握手定理：设G有n个顶点，则该图中所有顶点的度之和为边数的两倍。即设G中的n个顶点为v1，v2…vn，总边数为e，则d（v1）+d（v2）+…d（vn）=2e
推论：任何图中，奇度顶点的个数是偶数。
证：所有顶点的度数和（2m=偶数）=偶度顶点的度数之和（偶数）+奇度点的顶点度数之和，所以奇度点的顶点度数之和是一个偶数，而奇数个奇数为奇数，故奇数点的个数必为偶数。
这实际上是一个简单的算两次。
2.托兰定理：对一个有n个顶点的图，若其少有+1的点，则必构成一个三角形。
证明：反证法，假设这个图没有三角形。记它的顶点为v1，v2…vn不妨设v1的度最大，为k，与它有边相连的点为v2，v3…vk+1则这k个点互相不能有边，否则有三角形。则它们每个点至多连（n-k）条边，剩下的n-k-1的点中，每个点至多有k条边，所以若这个n阶图没有三角形，它的顶点的度之和不超过k+k×（n-k）+（n-k-1）k=2（n-k）k由握手定理，它至多有（n-k）k条边。当k=时，边数最大，为。考虑它是个整数，所以至多条边。矛盾，因而命题得证。
3.定理：任意的9个人中，必有3个人互相认识或4个人互相不认识。
一般的，在图论中我们将这类问题称之为拉姆塞问题。这个定理实际上说的是：在有n个顶点的图G中，存在一个K3（即三角形），或在它的补图中（在Kn中去掉G的所有边后余下的图称为G的补图）有一个K4，二者必有一成立，n=9是保证这一个结论成立的n的最小值。更一般的，要确保在一个有t个顶点的图中存在Km，或在其补图中存在Kn，t的最小值是多少？这就是拉姆赛问题。记满足上述要求的t的最小值为r（m，n），称为对应的拉姆塞数。拉姆塞数有许多有趣的性质，在此就不在展开了。
四、问题的解决
最后我们回到2016年的竞赛题：
证明：以这10个点为顶点，所连的线段为边，得到十阶简单图G，下面我们证明G的边数不超过15。
设G顶点为V1，…V10，他们之间共连了k条边，用deg（Vi）表示Vi的度，
若deg（Vi）≤3恒成立，则k=deg（Vi）≤×10×3=15
若存在deg（Vi）≥4，不妨设deg（（V1）=n≥4，且V1与V2…Vn+1相邻，于是V2…Vn+1之间不再有边，否则构成三角形，所以V1…Vn+1之間恰有n条边。
对每个j（n+2≤j≤10），Vj与V2…Vn+1中的至多一个顶点相邻，否则设Vj与Vs，Vt相邻，则V1，Vj，Vs，Vt构成空间四边形，故V2…Vn+1与Vn+2…V10之间至多10-（n+1）=9-n条边。
在Vn+2…V10这9—n个顶点之间无三角形，由托兰定理，至多有条边。
因此总边数为k≤n+（9-n）+≤9+=15，综上k不大于15。
而对于15条边的图恰有一种构造方式，如下：
参考文献：
[1]张垚著.数学竞赛中的组合问题，华东师范大学出版社（ 第1版）
[2]熊斌，郑仲义著.图论.华东师范大学出版社，2005，4
[3]单樽著.数学竞赛研究教程.江苏教育出版社，2009，2
[4]单樽著.从简单入手.中等数学.2011，9
【关键词】图论问题 数学竞赛 解题方法
【中图分类号】G633.6 【文献标识码】A 【文章编号】2095-3089（2017）07-0123-02
圖论作为一个重要的数学分支，几千年前，我国的河图、洛书就已经涉及到一些简单有趣的图论问题。18世纪，哥尼斯堡七桥问题使得图论作为一门真正的学科进入学者们的视野。而近二十年来，由于计算机科学、编码理论、规划论、数字通讯、实验设计等学科的迅猛发展，提出了一系列的需要离散数学解决的理论和实际问题，使得图论的研究更为活跃。由于图论蕴含的数学思想丰富，图形简洁美观，证明巧妙，方法千变万化，非常灵活，因而备受数学竞赛的青睐。今年的高中数学联赛加试第三道题就是一道以图论为背景的题：
给定空间中10个点，其中任意四点不在一个平面上，将某些点之间用线段相连，若得到的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大值。
在解决这道图论问题前，我们先来介绍一下图论的一些定义和概念：
一、图论相关的基本定义和基本概念
图由一个点集合V和一个连接某些点对的线段的集合E构成的图形称为图。记作G（V，E）.其中，V中的点称为顶点，E中的线段（不一定是直线段）称为边。通常|V|和|E|表示顶点个数和边的数量。有n个顶点的图称为n阶图。值得注意的是图中顶点一定不能为空，而边可以为空。
为了研究图的相关性质，我们还需要一些图的相关概念：
度：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d（v）
平行边：若有若干条边连着相同的两个顶点，则称这些边是平行边
环：两端连接着同一端点的边称为环
简单图：既不含平行边也不含环的图称为简单图
完全图：任意两个顶点间都有边相连的简单图称为完全图，n阶完全图记为Kn
在高中数学竞赛中，常见的都是简单图。
二、解决图论问题的基本方法
在常见的图论问题中，我们主要研究一个图的边数，顶点数，这自然离不开计数方法的运用，使用最频繁的当属富比尼原理，这通常通过对顶点的度与图的边数的两次计数来实现。而其他如反证法、数学归纳法、抽屉原理等方法在图论中也有丰富的应用。
例题：
例1（1985年全国高中数学联赛试题）某足球邀请赛有十六个城市参加，每市派出甲、乙两个队，根据比赛规则，比赛若干天后进行统计，发现除A市甲队外，其它各队已比赛过的场数各不相同.问A市乙队已赛过多少场？请证明你的结论。
证明：用32个点表示这32个队，如果某两队比赛了一场，则在表示这两个队的点间连一条线，否则就不连线。
由于，这些队比赛场次最多30场，最少0场，共有31种情况，现除A市甲队外还有31个队，这31个队的比赛场次互不相同，故这31个队比赛的场次恰好为0到30场，就在表示每个队的点旁注上这队的比赛场次。
考虑比赛场次为30的队，这个队除自己与同城的队外，与不同城有队都进行了比赛，于是，它只可能与比赛0场的队同城；去掉这两支队伍以及这两支队伍的比赛场次（即这时候其他队伍的比赛场次都减少1），在剩下的30支队伍中，再考虑比赛28（29-1）场的队伍，这个队除与同城队不比赛外，与其他队伍都比赛过了，原先赛了1场的队此时记为0场了，同理，它和赛了29场的是一个城市的；依次类推，知比赛k场的队与比赛30-k场的队同城，这样，把各城都配对后，只有比赛15场的队没有与其余的队同城，故比赛15场的队就是A城乙队。即A城乙队比赛了15场。
该题是一道典型的顶点的度的应用，转化成图论问题之后，使我们对条件的理解更加直观，清晰了解题思路。
例2：证明任意六个人中，必有三个人相互认识或三个人相互不认识？
这道题将它用图论的语言转述即为：将一个6阶的图用两种颜色把其中的点两两连线（认识和不认识分别代表两种颜色），必有一个同色三角形。这就是著名的Ramsey定理。一种较为常见证明的过程是对由一个顶点出发对同色边的条数运用抽屉原理进行讨论，在此不再赘述。有趣的是，如果转而对同色角的个数去讨论，我们能得到一个更强的结论：
对K6完全图二染色，一定存在两个同色三角形
证明：由一个顶点出发，引出5条边，则以每个顶点可做出C个角，至少有4个两边同色的角，故图.K6中至少有24个同色角。而每个同色三角形有3个同色角，不同色的三角形有1个同色角。K6中一共有20个三角形。因此，至少有两个同色三角形。
在解决一些图论问题中，我们还需要用到一些图论的定理。
三、一些图论的基本（著名的）定理
1.握手定理：设G有n个顶点，则该图中所有顶点的度之和为边数的两倍。即设G中的n个顶点为v1，v2…vn，总边数为e，则d（v1）+d（v2）+…d（vn）=2e
推论：任何图中，奇度顶点的个数是偶数。
证：所有顶点的度数和（2m=偶数）=偶度顶点的度数之和（偶数）+奇度点的顶点度数之和，所以奇度点的顶点度数之和是一个偶数，而奇数个奇数为奇数，故奇数点的个数必为偶数。
这实际上是一个简单的算两次。
2.托兰定理：对一个有n个顶点的图，若其少有+1的点，则必构成一个三角形。
证明：反证法，假设这个图没有三角形。记它的顶点为v1，v2…vn不妨设v1的度最大，为k，与它有边相连的点为v2，v3…vk+1则这k个点互相不能有边，否则有三角形。则它们每个点至多连（n-k）条边，剩下的n-k-1的点中，每个点至多有k条边，所以若这个n阶图没有三角形，它的顶点的度之和不超过k+k×（n-k）+（n-k-1）k=2（n-k）k由握手定理，它至多有（n-k）k条边。当k=时，边数最大，为。考虑它是个整数，所以至多条边。矛盾，因而命题得证。
3.定理：任意的9个人中，必有3个人互相认识或4个人互相不认识。
一般的，在图论中我们将这类问题称之为拉姆塞问题。这个定理实际上说的是：在有n个顶点的图G中，存在一个K3（即三角形），或在它的补图中（在Kn中去掉G的所有边后余下的图称为G的补图）有一个K4，二者必有一成立，n=9是保证这一个结论成立的n的最小值。更一般的，要确保在一个有t个顶点的图中存在Km，或在其补图中存在Kn，t的最小值是多少？这就是拉姆赛问题。记满足上述要求的t的最小值为r（m，n），称为对应的拉姆塞数。拉姆塞数有许多有趣的性质，在此就不在展开了。
四、问题的解决
最后我们回到2016年的竞赛题：
证明：以这10个点为顶点，所连的线段为边，得到十阶简单图G，下面我们证明G的边数不超过15。
设G顶点为V1，…V10，他们之间共连了k条边，用deg（Vi）表示Vi的度，
若deg（Vi）≤3恒成立，则k=deg（Vi）≤×10×3=15
若存在deg（Vi）≥4，不妨设deg（（V1）=n≥4，且V1与V2…Vn+1相邻，于是V2…Vn+1之间不再有边，否则构成三角形，所以V1…Vn+1之間恰有n条边。
对每个j（n+2≤j≤10），Vj与V2…Vn+1中的至多一个顶点相邻，否则设Vj与Vs，Vt相邻，则V1，Vj，Vs，Vt构成空间四边形，故V2…Vn+1与Vn+2…V10之间至多10-（n+1）=9-n条边。
在Vn+2…V10这9—n个顶点之间无三角形，由托兰定理，至多有条边。
因此总边数为k≤n+（9-n）+≤9+=15，综上k不大于15。
而对于15条边的图恰有一种构造方式，如下：
参考文献：
[1]张垚著.数学竞赛中的组合问题，华东师范大学出版社（ 第1版）
[2]熊斌，郑仲义著.图论.华东师范大学出版社，2005，4
[3]单樽著.数学竞赛研究教程.江苏教育出版社，2009，2
[4]单樽著.从简单入手.中等数学.2011，9