为什么中学生要学习图论？

作者|Jason  编辑|罗数君

文1896字  阅读时间约5分钟

作者介绍：

Jason，卡耐基梅隆大学（CMU）大三数学金融系学生，罗博深数学实习生。在大一上了Po-Shen的《离散数学》之后成为了他的迷弟，希望能将他的数学思维传递给全世界：)

图论是数学中非常重要的一个分支，然而当我们在数学学习中听到图论这个词，往往会与高等数学联系在一起，让人不由自主的感到无从下手。确实，在我们从小学到高中的数学学习中，图论从来没有在课本里出现过，直到大学的学习，也只有数学系的学生才会慢慢的接触到图论。惭愧的说，在进入大学前的我也从来没有任何对图论的了解，而当我在离散数学课上第一次接触到了图论，就被它的魅力所折服。我渐渐的发现，在我们从小到大的数学学习中，图论其实经常悄悄的出现。现在，就让我用一些有趣的例子，让大家也感受一下图论的魅力。

在小的时候，我们在数学课上经常会遇到一笔画的问题，如下图：

图片来源：baidu.com

这些一笔画问题就是使笔尖不离开纸面而又不重复地画出一个图形，我们在经过尝试之后发现，有一些图片能轻松的用一笔画出，而有一些图片似乎无论如何也不能通过一笔完成。

我们经过不断地尝试和总结，可以渐渐找到一些规律，我们发现一个图形能否被一笔画出似乎和顶点连出的线段的奇偶性有着一些关系。我们将引出奇数个线段的顶点称作奇点，将引出偶数个线段的顶点成为偶点，我们可以观察出一个图形能否被一笔画下来，看的是奇点的个数：当一个图中奇点的数量为0或者2个时，这个图可以被一笔画出，反之，这个图无论如何也不能被一笔画出。

这样的一笔画问题其实是图论中非常重要的问题。一笔画的问题起源于十八世纪“格尼斯堡桥”的问题，在这个问题中，我们需要不重复地走遍七座桥回到出发点，如下图：

       对于这个问题的研究开创了一个新的数学分支，也就是图论。在图论中，我们将其中的点称作顶点，将连接这些顶点的线成为边，这些顶点和边的关系是我们解决一笔画问题的关键，通过图论的知识，我们可以证明出之前发现的一笔画的规律。

与此同时，让我们一起来探讨一个非常有意思的图论的问题。我们已经引出了图论中顶点和边的概念，我们也知道图论中的图是由一些顶点和边组成的，这些顶点和边将平面切成了不一样的区域。当我们一起观察这些顶点，边和区域的数量时，我们可以发现一些非常有意思的规律：我们发现顶点数(V)减去边数(E)加上区域数(R)的数量总是一样的。这个规律是由数学家欧拉最先提出的，让我们来验证一下：

似乎无论在平面中的图形无论是怎么样的，只要这些顶点和边是相连的，我们都可以得出结论：V-E+R = 2。

想必同学们一定想知道这样的规律是否可以被证明出来，我可以给大家简单的介绍一下。这个规律的证明思想用到数学证明常用的递归法思想。

当一个图只有一个顶点且没有任何边的时候，顶点的数量是1，边的数量是0，区域数是1，我们可以看到V-E+R = 1-0+1 = 2。当我们增加第一条边的时候，自然也会增加一个顶点，然而由于平面中只有一个顶点，增加一条边不能将平面切开，所以区域数不会改变。

因此，V-E+R仍然是2。当我们有n条边的时候，增加一条边会有两个情况，一是从顶点延伸出一条边，这样，区域数不会改变，而顶点数会增加1。所以当顶点数增加1且边数增加1，在区域数没有改变的情况下，V-E+R仍然等于2。第二个情况是这条新的边链接了两个顶点，这样顶点数不会改变，但是连接两个顶点会将平面一切两段，所以就会增加一个区域。

这样，在增加了一个边和一个区域的情况下，我们看到V-E+R仍然等于2。通过递归法的思路，我们可以证明出发现的结论。

有兴趣的同学可以再进一步，看看这个规律在三维的情况下是否还适用？

图片来源：http://jdh.hamkins.org/math-for-eight-year-olds/

图论和应用是非常广泛的，虽然组成图的顶点和边看似十分简单，我们却可以用之模拟生活中很多的活动，包括人际关系，路线问题，通讯系统，计算机问题。通过图论，我们可以把顶点当做一个人，而连接两个顶点的边表示两个人是朋友，我们可以通过图论证明出拉姆西难题：在随意凑齐的六个人中，一定能找到彼此认识或者彼此不认识的三个人。通过图论，我们若将边加上重量，我们就可以用此模拟优化问题，这些问题在计算机中被称作货郎担问题，是计算机学科中经典的NP问题，正被无数数学和计算机学科中的精英研究着。

这就是图论的魅力了，你感受到了吗？

Reference：七彩教育网《一笔画问题与图论》

喜欢这篇文章吗？欢迎给我们留言，探讨有趣的数学问题，如果你还想看其他的相关内容，也可以向我们提出来哦！ 

相关推荐