骑士书屋 通过搜索各大小说站为您自动抓取各类小说的最快更新供您阅读!

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

格哈德·林格尔(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个点的完整图,编码规则是根据距离(通过一条边连接的两个点之间的距离)进行上色。

假设如果两个点彼此相邻,则它们之间的距离为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条边的点。因此,数学家将它与树的其余部分分开,然后将其首先放置。这就像你要把一张床移到楼上必须得先拆卸再进行组装一样。

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

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

除此之外,三位数学家的研究结果给类似未解决的问题提供了新思路。或许适当调整一下还可以解决更多未知猜想。

骑士书屋推荐阅读:重生:第一玩家全民穿越,异世界求生网游之我的属性百倍成长吞掉一万只哥布林后,我无敌了!篮坛圆梦大师:我带你们拿冠军莲花楼之我带花花去修仙别反野了,对面打野都哭了!金币爆率100倍,我骄傲了吗?大家都在艰难求生,凭什么你开挂网游:有五个神职姐姐的我,无敌网游:从暴打隔壁校花开始网游:怪物降临现实阁下如何应对唐俏儿沈惊觉异界全能领主就算是假千金也要勇敢摆烂杏坛一笑我的三战充满玄学NBA得分后卫养成记末日游戏:开局获得荒野的呼唤网游之我的属性变变变史上最强青训选手碟战,我能分辨日碟NBA的下一个答案智慧的明灯与心灵的指引生存游戏,别人啃草她吃肉带着玩家在赛博世界闹革命kenshi 漂泊终地异界求生被我玩成了冒险开局福星附身,所有技能增强!领主:开局召唤齐天大圣孙悟空DNF之异界鬼剑士全民求生:我是地窟第一猛男梦幻西游:开局第一无级别绝区零:我是个很普通的人篮球:系统新手任务,隔扣大鲨鱼综网的巫:从艾泽拉斯吃到山海经网游:盲人刺客杀穿异界NBA:从偷吃库里爆米花始无敌纵漫,从02的世界开始强化网游:蜕变之路联盟:我,重新定义辅助!10投必中8,你管这叫中投挂?叶凌天周雪青九州天王免费阅读全文自来也豪杰物语:原神篇篮球,人生冷青衫最新小说联盟三千年震惊:暮年詹姆斯依旧吊打全联盟夏初见易楠平的小说全文免费阅读无弹窗万古帝婿夜玄
骑士书屋搜藏榜:全民航海求生,开局一艘冥王号轮回乐园之投影三枪追魂穿越者公敌领主降临:从选择身份开始对别人的男宠一见钟情超神:四舍五入我老婆是三王宅在游戏当大侠重生八零完美逆袭我是巅峰BOSS新还珠传奇之风云再起七十一变[综]都市之纵意花丛丧尸末世,但是在大唐NBA:爱发推特的我统治了联盟游戏制作从负债千万开始全球降临:浮空岛无限战争清歌煮酒林小北的游戏赚钱生涯从黑袍开始成为究极生物全民大航海,我开局一条幽灵船卢米安莉雅的小说免费阅读眼睛一闭一睁,无限我来啦九州天王叶凌天周雪青夏初见易楠平全文免费阅读完整版LCK的中国外援最后的地球战神怪猎聊天群DNF圣职者转生异界为爱延续大神捂紧你的小马甲网游之海盗王木叶有妖气全球游戏:无敌氪金系统斗罗:被读心后成了武魂殿团宠墨门飞甲网游:我的道具能具现斗破之我让魂族从了良网游之剑气无双美女总裁的护花保镖李南神话天书战龙归来林北逆战之大枪神我叫欧楚良斗破:家祖玄帝萧玄LOL系统:从扮演刀妹开始墨迹诸天极品豪婿植僵大陆:我的农场也太全面了吧NBA数据自由定制,谗哭科詹库
骑士书屋最新小说:转生萝莉:变身虫族女皇!量子游戏没有爱魔炎崩坏,我才不是魅魔啊!重生之我在云都偷心三千次崩坏,镜流的王者大师兄海贼:国服路飞不给就送!LOL:全能AD和他的四个挂件四合院之重走来时路结局大不同网游之重生开天全世界都想我和前搭档复合网游:全职召唤师九霄灵枢:量子修真纪元崩铁观影:太一?阿哈不许复活赘婿逆袭:商业神级系统刑侦:他又在凶案现场偷亲我天幕:狐妖小红娘明明是杰克的我为什么会在柯南啊轮回录:魔族小妹拐了妖族团宠安魂鬼事录四合院:拒绝秦淮如,踢爆易中海破茧成凰前男友的追悔录转生索罗亚,被精灵老婆包围了武道霸主:小保安也能穿越?水仙花的执念领袖之证:汽车人与东方神秘力量柯学怪盗古明地恋的奇妙冒险四合院:暴秦淮如,东旭青幽幽爱与救赎柯南与灰原哀在霍格沃茨心想事成安陵容重生本宫偏要逆天改命替嫁后被植物人老公宠上天魔法少女:攻略暗黑地牢被恶鬼室友逼迫生子无尽杀戮游戏,技能无限升级全技大师全民转职:召唤十万特种兵暴杀世界融合,开局无人侏罗纪星露谷马莱入侵?反手解放全世界!原神:提瓦特的大法师弃女独居后,前任竟是替身将我的灵魂撕碎再重组虚空游戏:从离开太阳系开始蛇王恋爱脑:痴缠千世轮回妻咸鱼续命:国师真香史前求生:开局获得幸运神兽帝君穿书后,全师门都癫了哪吒2魔童闹海之惊天秘事网游:这个隐藏天赋不正经