宫廷看书网>数学心 > 第六百五十八章 林格尔猜想图论（第1页）
第六百五十八章 林格尔猜想图论（第1页）
树图是只有分支没有闭合的图，完全图是每个节点都两两相连的满图。
格哈德·林格尔（GerhardRingel）想用多个相同树图去填充完全图。如何让多个简单的小图副本完美地重构（覆盖）一张大图？
1963年，一位名叫格哈德·林格尔的德国数学家提出了一个大胆的猜想：一些特定的图形总是可以被n个小图副本完美覆盖。对此，他指出：任给一棵具有n条边的树t，都能在2n+1阶完全图K2n+1中找到不重合且同构于t的2n+1个子图（即2n+1个t副本可以被完美地填充到K2n+1中）
解释一下，就是首先，想象一个包含2n+1个点的完整图形。然后思考使用n+1个点可以制作多少棵树，事实上可以做出很多种完全不同的树。现在，选择其中一棵树并将其放置，以使树的每个边与完整图形中的边重合。然后，将同一棵树的另一个副本放在整个图形的不同部分上。林格尔预测，假设你从正确的地方开始放置并持续这个动作，那么你将能够完美地复制出上面的完整图形。这意味着完整图形中的每个边都被树的每条边覆盖，且树的任何副本都不会相互重叠。
为了证明林格尔的猜想，人们发展与利用了多种数学工具，比如：概率方法、正则引理等，但似乎总有漏洞。
科齐格则推测，平铺总是可以旋转的方式完成。
如果想探究他们的猜想，简单的星形树图是或许是一个不错的起点。
最简单的树图之一是星形：有一个中心点，其他边从中心辐射出来。但它不同于典型的星形图，因为边不必在点周围均匀排列，只需从同一位置向外延伸，除了在中央点之外，不能在其他任何地方相交。
确实，数学家很快观察到，具有n+1个点的星形树始终可以完美地复制到具有2n+1个点的完整图形。单单这个事实就很有趣，但是如何证明却让数学家们犯了难。
但是这个实验依然有漏洞：星形图是规则的，因此无论如何放置都无关紧要。但是大多数树并不是，假如树上有许多不同长度的不同分支，那么只有正确放置它们才能使旋转方法起作用，且此时如何放置第一步将至关重要。
幸运的是，数学家们最终找到了一个直观的色彩方法。
近日，苏黎世瑞士联邦技术学院的本尼·苏达科夫（bennySudakov）、伯明翰大学的理查德·蒙哥马利（Richardmontgomery）和伦敦伯克贝克大学的亚历克斯·波克洛夫斯基（Alexeypokrovskiy）三名数学家发表的相关论文或许给证明这个困惑了人们将近60年的数学猜想带来了希望。他们通过颜色编码找到树的彩虹副本
颜色编码在生活中有很多应用，比如它可以帮助区分日常工作的紧急程度、完成情况等。事实证明，这也是找出如何放置第一颗树的有效方法。
如何进行颜色编码呢？首先，想象围绕一个圆排列的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条边的点。因此，数学家将它与树的其余部分分开，然后将其首先放置。这就像你要把一张床移到楼上必须得先拆卸再进行组装一样。
通过这样做，他们确保了整个图形中的剩余空间是随机的。
这三位数学家的研究表明，一旦嵌入了树图最难的部分，且完整图的剩余空间是随机的，那么总有一种方法可以嵌入树的其余部分以获得彩虹副本。
除此之外，三位数学家的研究结果给类似未解决的问题提供了新思路。或许适当调整一下还可以解决更多未知猜想。
请勿开启浏览器阅读模式，否则将导致章节内容缺失及无法阅读下一章。
相邻推荐:刑警处长和他的总裁顾问 开局瞎子，我靠捏泥人超凡入圣 斗罗：收徒霍雨浩，武魂无限觉醒 风中往事 转生凡人萝莉，一路修炼一路杀 星铁：开局令使，成为镜流夫君 轰成炮灰后，我去破落宗门种田了 全民修仙：我批量培植高武大帝 末世我有百亿物资，顶流偶像跪舔 斗罗之拜托！我很强的 掌家娘子福满满 军婚爆甜：我一胎三宝给夫家撑腰 都重生了肯定全都要啊 柔柔如她 禁止离婚：傅少求放过 神尊之吾名仙姬 快穿：沉迷学习，无法自拔 小镇春色 女神校花的贴身高手 震惊！顶流私下居然是这样的男人
