顶点中文网

手机浏览器扫描二维码访问

第六百五十八章 林格尔猜想图论（第2页）

他们通过颜色编码找到树的彩虹副本

颜色编码在生活中有很多应用，比如它可以帮助区分日常工作的紧急程度、完成情况等。

事实证明，这也是找出如何放置第一颗树的有效方法。

如何进行颜色编码呢？首先，想象围绕一个圆排列的11个点的完整图，编码规则是根据距离（通过一条边连接的两个点之间的距离）进行上色。

假设如果两个点彼此相邻，则它们之间的距离为1，如果两个点中间相隔一个点，则它们之间的距离为2。

现在根据距离为完整图的边上色。

距离为1的所有点的边都涂成相同的颜色，例如蓝色。

距离为2的点的所有边也都标记相同的颜色，例如黄色。

继续这样操作，以使连接点的边距相等的距离都标记相同的颜色。

结果证明，在具有2n+1个点的完整图形上，你需要n种不同的颜色来执行该方案。

给完整图形按颜色编码后，如何找到放置第一颗树的方法呢？

这个想法是将树定位，使其覆盖每种颜色的一个边，且不覆盖任何颜色两次，数学家们将此位置称为树的彩虹副本。

对于一个具有2n+1个点的完整图来说，由于着色需要n种颜色，并且其彩虹副本总是具有n+1个点的树图，因此我们知道彩虹副本是存在的。

至此，数学家们就可以通过证明每个具有2n+1个点的完整图包含具有n条边的树的彩虹副本，来证明林格尔的猜想。

如果彩虹副本始终存在，则完全覆盖完整图始终有效。

如果有一个包含11（2n+1=11，则n=5）个点，且已用5种不同颜色上色的完整图形，以及一个包含6个点、5条边的树图，你的任务是在完整图中找到树的彩虹副本。

随着工作不断进行，放置下一个树的工作越来越难，因此你可能需要提前做好计划。

三个数学家从一开始就知道，找到彩虹副本或许不难，难得是如何放置。

就好像打包过行李箱，众所周知，我们应该从最困难、最复杂的物体开始，比如手提箱、自行车等，因为无论如何，你最后总能找到缝隙塞进一些小东西，数学家们也采纳了这一哲学。

想象一棵有11条边的树，其中6条边的点集中在一起。

剩下的大部分是单一的形状，像卷须一样。

最难放置的部分是具有6条边的点。

因此，数学家将它与树的其余部分分开，然后将其首先放置。

这就像你要把一张床移到楼上必须得先拆卸再进行组装一样。

通过这样做，他们确保了整个图形中的剩余空间是随机的。

这三位数学家的研究表明，一旦嵌入了树图最难的部分，且完整图的剩余空间是随机的，那么总有一种方法可以嵌入树的其余部分以获得彩虹副本。

除此之外，三位数学家的研究结果给类似未解决的问题提供了新思路。

或许适当调整一下还可以解决更多未知猜想。