您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识

在一个完整的平面图中，顶点的最大数量是多少？

顶点,你的,平面图在一个完整的平面图中，顶点的最大数量是多少？

发布时间：2016-12-08加入收藏来源：互联网点击：

在一个完整的平面图中，顶点的最大数量是多少？

回答于 2019-09-11 08:43:50

回答于 2019-09-11 08:43:50

在图论中，顶点数量固定以后，如果不存在重复的边，那么n个顶点之间可以有n（n-1）/2条边，这样的图叫做完全图。这个可以根据组合数学很容易算出来，因此你的问题显得不是那么清晰，我感觉你是再问完全图的结构。

很明显，如果你不是考虑完全图，那么平面上的图最多可以有无穷多个顶点，顶点与顶点之间你可以用线段依次连接起来，这个的树图当然是平面图了。难道你是想问这个问题吗？

如果是顶点的数目固定，那么平面图的边数与顶点数之间存在一个不等式，具体可以参考图论的教材，或者今日头条上科普与教育自媒体“潇轩”的相关视频。因为那个不等式的推导还是有点复杂的，我建议你可以看看相关教材。这个真不是我现在一下子能给你说出来的。

不过，你的提问有点模糊，我不理解的是什么叫一个完整的平面图？具体是什么意思呢？还希望你仔细思考一下你的提问是不是有不够明确的地方。

不过，看起来你肯定是在问图论的问题，这点应该是没错的。

另外，进一步来说，如果你对图论中顶点的染色问题有兴趣，可以学习一点染色多项式的知识。相关的知识在组合数学中是非常深邃的，染色问题的一个典型的案例就是证明地图的四色原理，这个问题到目前为止还没有被人类用纯粹数学的方法解决。如果你是一个年轻人，那么，既然你已经提出了这个图论问题了，我希望你能继续在这个方向上思考下去，为数学的发展做出自己的贡献，那真是极好的。

回答于 2019-09-11 08:43:50

当你在平面上绘制任意图形时，都会产生一些点或是“顶点”（v），一些路径或是“边”（e），和一些区域或是“面”（f）。这些面是由各边所形成的白色区域，我们通常把整个图形周围的空间作为一个面。

例如，这里有4个顶点，6条边和4个面:

当你有零维物体 (顶点)，一维物体(边)，和二维物体(面)的时候，你立即用交替符号把它们加在一起。偶数得到a+，奇数得到a-。这是欧拉在拓扑学中的深刻见解之一，现在被称为欧拉特性。我们很快就会明白它为什么这么经典了。

方程是这样的：

χ=v−e+fχ=v−e+f

在我们刚刚看过的例子中，

χ=4−6+4=2χ=4−6+4=2.

让我们再试试其他例子：

可以看到v=8v=8个顶点，e=12e=12条边，f=6f=6个面——别忘了最外面的那个区域。所以：

χ= 8−12 + 6 = 2χ= 8−12 + 6 = 2

啊哈又是2，这肯定是个巧合对不对。让咱们来个难的，作为学霸的你就小享受一下:

这个图形有20个顶点，30条边(自己数！)和12个面。那么,χ是多少呢?没错，还是2。

欧拉的观点是，只要你的图形是连通的，也就是说你可以从任意顶点到任意路径，这个值总是等于2。你的图形可以有3个顶点或是1万亿个顶点，只要能在平面上画出来，它的顶点数、面数、棱数就会存在这样特有的规律。

这是为什么呢?

你可以通过很多方法加以验证，但是有一种我认为是相当直观的。如果在图中没有圆圈，也就是没有沿着边走的路线，然后不按原路线返回出发点，那么就生成了所谓的森林。如果将森林也连接起来，那么就生成了树。树的顶点总数总是会比边数多1——通过归纳法很容易证明，如果你学过一些算法的话，就更不用说了。除了外部区域以外，它也不构成任何区域。所以对于树来说，欧拉特性总是2。

v−(v−1)+1=2v−(v−1)+1=2

现在，当你开始添加边数的时候，每一条额外的边都不会改变顶点的数量，增加1条边，同时也就增加了1个面，因为它正好把一个面分成了两部分，所以欧拉特性χ不变。

因为每个连通图都可以通过生成树和添加边数进行绘制，搞定。

这和K5有什么关系呢?

如果你在平面上画出5个点，并通过路径把它们连接在一起，你就会得到5个点，10条路径，所以必然是7个面，因为x=2。但这是毫无意义的:每个面都至少有3条边，每条边都最多属于2个面。所以必然是3f≤2e3f≤2e，而21>20。出现这样的矛盾意味着K5不是平面图。

还有很多其他图也不是平面的，其中一个是k3,3，这张图有三个点和另外三个点相连。库拉脱斯基（Kuratowski）证明了k5和k3,3这两张图是非平面图形的唯一理由是：如果你的图包含基本非平面图中的任何一个作为它的子图，那么这个图就是非平面图。反之，就是平面图。

这个美丽的定理被延伸到了很多方面，用来描述可以绘制在其他表面上的图形，并最终形成了一个惊人的定理：罗伯斯-西摩定理。在我看来，这是20世纪数学界的最高成就之一，它实在太有魅力了。