趣书网

阅读记录  |   用户书架
上一章
目录 | 设置
下一页

第六百五十八章 林格尔猜想(图论)(1 / 2)

加入书签 | 推荐本书 | 问题反馈 | 内容报错

树图是只有分支没有闭合的图,完全图是每个节点都两两相连的满图。

格哈德·林格尔(Gerhard Ringel)想用多个相同树图去填充完全图。如何让多个简单的小图副本完美地重构(覆盖)一张大图?

1963年,一位名叫格哈德·林格尔的德国数学家提出了一个大胆的猜想:一些特定的图形总是可以被n个小图副本完美覆盖。对此,他指出:任给一棵具有 n条边的树 t,都能在2n+1阶完全图K2n+1中找到不重合且同构于t的2n+1个子图(即2n+1个t副本可以被完美地填充到K2n+1中)

解释一下,就是首先,想象一个包含2n+1个点的完整图形。然后思考使用n+1个点可以制作多少棵树,事实上可以做出很多种完全不同的树。现在,选择其中一棵树并将其放置,以使树的每个边与完整图形中的边重合。然后,将同一棵树的另一个副本放在整个图形的不同部分上。林格尔预测,假设你从正确的地方开始放置并持续这个动作,那么你将能够完美地复制出上面的完整图形。这意味着完整图形中的每个边都被树的每条边覆盖,且树的任何副本都不会相互重叠。

为了证明林格尔的猜想,人们发展与利用了多种数学工具,比如:概率方法、正则引理等,但似乎总有漏洞。

科齐格则推测,平铺总是可以旋转的方式完成。

如果想探究他们的猜想,简单的星形树图是或许是一个不错的起点。

最简单的树图之一是星形:有一个中心点,其他边从中心辐射出来。但它不同于典型的星形图,因为边不必在点周围均匀排列,只需从同一位置向外延伸,除了在中央点之外,不能在其他任何地方相交。

确实,数学家很快观察到,具有n+1个点的星形树始终可以完美地复制到具有2n+1个点的完整图形。单单这个事实就很有趣,但是如何证明却让数学家们犯了难。

但是这个实验依然有漏洞:星形图是规则的,因此无论如何放置都无关紧要。但是大多数树并不是,假如树上有许多不同长度的不同分支,那么只有正确放置它们才能使旋转方法起作用,且此时如何放置第一步将至关重要。

幸运的是,数学家们最终找到了一个直观的色彩方法。

近日,苏黎世瑞士联邦技术学院的本尼·苏达科夫(benny Sudakov)、伯明翰大学的理查德·蒙哥马利(Richard montgomery)和伦敦伯克贝克大学的亚历克斯·波克洛夫斯基(Alexey pokrovskiy)三名数学家发表的相关论文或许给证明这个困惑了人们将近60年的数学猜想带来了希望。他们通过颜色编码找到树的彩虹副本

颜色编码在生活中有很多应用,比如它可以帮助区分日常工作的紧急程度、完成情况等。事实证明,这也是找出如何放置第一颗树的有效方法。

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

上一章
目录
下一页
A- 18 A+
默认 贵族金 护眼绿 羊皮纸 可爱粉 夜间