Get best of the week

彩虹着色是数学家的最好朋友

最近，彩虹色帮助进行了新的证明。而且它们并不是第一次有用。



拉丁方及其图形的颜色编码可以为您提供很多信息，

最近，我们讨论了林格假设的新证明。部分证据与彩虹色的使用有关，彩虹色是一种用于可视化信息的特殊颜色编码方式。但是，这种着色书已经被数学家使用了很长时间，以方便解决难题，现在，他们正在尝试将该技术应用于与上一个着色书相关的问题。

Ringel假设是组合图形学领域的一个问题，涉及图形的构建-通过线（边）连接的点（顶点）。它预测具有2n +1个顶点的某种类型的大图与具有n +1个顶点的成比例的较小图之间的特殊关系。

例如，让我们从11个峰开始。将每个顶点与所有其他顶点连接以获得所谓的全图。接下来，取六个可用的顶点，并根据需要将它们连接起来，只是这样才能避免出现闭环。这样我们得到所谓的“木”。


完整图和树的示例

Ringel的假设说，任何一棵树的副本都可以理想地覆盖或平铺相应完整图的所有边缘-就像您可以用相同的瓷砖平铺厨房地板一样。



与厨房地板一样，要成功，必须选择第一块瓷砖的正确位置。提出证明颜色的三位数学家根据顶点之间的距离对完整图形的边缘进行了编码，以找到该位置。



然后，他们尝试将树布置在完整的图形中，以使其覆盖每种颜色的一个边缘。已经证明了这种“彩虹”布置在任何情况下都是可行的，他们证明了Ringel预测的理想平铺总是可行的。

但是，这种彩虹着色技术并不是第一次被抢救。

在18世纪，伦纳德·欧拉（Leonard Euler）对诸如数独的儿童感兴趣。取一个3x3单元格的正方形。欧拉填充它，以便在每一行和每一列中都有从1到3的数字，从此不再重复。这个难题叫拉丁方。欧拉和其他数学家在研究拉丁方格中发现的模式和技术与许多不同的数学领域都有联系。



然后，欧拉想知道：是否可以选择三个单元格，每一列和每一行中一个，这样它们中的数字就不会重复？假设您可以从包含1的第一行的第一列中选​​择一个单元格，从包含3的第二列的第二行中选择一个单元格，并从包含2的第三列的第三行中选择一个单元格。因此，我们选择了三个单元格，每个单元格分别属于不同的行和列，并包含其数字-1、3、2。这组单元格称为横向单元。



欧拉想知道是否有可能将整个3x3网格（或任何大小的正方形网格）完全划分为横向集合，以便每个集合的每一行和每一列都有一个数字。也就是说，对于3x3的正方形，我希望我们能够找到三个不同的横向集合，这些横向集合将正方形的所有像元都覆盖在一起。

结果，数学家发现探索此问题的一种方法是将正方形变成图形。为此，请在左侧绘制三个顶点，表示三列。然后，我们在右侧绘制三个顶点，分别代表这些线。画出连接右侧每个顶点和左侧每个顶点的边。每个边缘是特定行和列的组合，代表九个单元之一。例如，右上顶点和左上顶点之间的边对应于第一列第一行的单元格（拉丁方格的左上单元格）。



现在我们取出彩色铅笔，并根据它们所代表的正方形数字对肋骨的颜色进行编码。假设我们用蓝色标记表示1的线，用2标记红色的线，用3标记的线。如果1在左上方的单元格中，则顶部顶点之间的边缘将是蓝色。



让我们看一下边缘的颜色。是否可以从三种颜色的每一种中选择三个边缘，以便它们在不同的顶点开始和结束？这组称为彩虹匹配。如果找到它，则很明显在相应的拉丁方格中有一个横向。此外，如果找到三个不同的彩虹对应关系，则很显然整个拉丁方由横向组成。



彩虹色可以帮助研究人员研究过去的问题，并且成为Ringel假设新证据的关键要素。它们还在更为复杂的任务（优美的标记假设）中发挥作用。

要了解问题的实质，请首先绘制六个顶点，然后将它们连接以形成树。以任何方式为每个顶点分配一个数字。然后用连接的顶点数之差标记每个边。也就是说，例如，如果一条边连接了顶点6和2，则我们用数字4标记该边。

您的目标是使这些边标签按顺序排列，并且它们的数字不重复。在这种情况下，为1、2、3、4、5。如果可以执行此操作，则树将存在优美的标记。



在1960年代，提出假设的格哈德·林格（Gerhard Ringel）和安东·科茨格（Anton Kotsig）一起提出，可以优雅地标记任何树木，无论其边缘或形状如何。

优美的标记假设暗示了Ringel假设-也就是说，如果第一个假设为真，则Ringel假设也为真。为了理解这一点，让我们返回一个优美地标记的六个顶点树和一个完整的11个顶点图。我们将这11个顶点分布在圆周上，并从1到11进行编号。现在，我们将树的副本放置在完整图上，以使这些顶点的标签重合：树的顶点5与整个图的顶点5重叠，依此类推。此放置是优美标记的树的彩虹副本。



因此，如果知道顶点数为n + 1的树始终可以被优美地标记，那么您知道它们总是可以被放置在具有2n +1个顶点的相应完整图形中，从而获得树的彩虹副本。这样的放置将恰好是开始对Ringel进行拼贴的过程的位置。

“如果发现优美的标记，我可以告诉您如何找到彩虹的副本，” 林格假设的三位作者之一瑞士联邦技术学院的本尼·苏达科夫说。

当然，数学家最终能够证明林格尔假设的真相，而不必证明优美标记的假设，从而使这个问题没有得到解答。

苏达科夫说：“优美的标记本身就是一个引人入胜的美丽问题，并且仍然存在。”

但是，导致Ringel假设得到证明的方法可能可以应用于优美的标记-数学家急切地想知道这些方法可以带给他们多远的距离。

More articles:


All Articles