三元方程解集基底互素定理可解决大量未解的丢番图问题(44)
2023-12-21 来源:飞速影视
能四色区分的图是由哈密顿路径组织成的一棵树,哈密顿图是一个可3-着色图,判定哈密顿图如果在多项式时间里是可计算的,那就证明了P=NP,凡四色可区分图能最大化改成三色可区分图就是哈密顿图的判定算法。故哈密顿图是可归约为3-着色图的,3-着色图又可归约为图着色问题的,其中就含四色猜想。
四色猜想须局部满足三色定理,四色猜想是邻接色须满足三色定理的前提下才成立的,是鸽笼定理的计算方法为判定三色定理找到了充分必要条件,证明这一性质的相关定理有四邻定理(第四色总被前三色覆盖),一笔画性质(前继被后继覆盖),欧拉示性数(一边会被一图覆盖,一图会被一边覆盖,即前继被后继覆盖)。我们知道任意给定地图,都可以用区块替换顶点来置换成对偶图,当然对偶图也可在若当曲线区分给定图的结构后进行,便于直观选择产生偶数闭链,其单区块可满足覆盖奇链或被奇链覆盖。在这一点上思考对偶图不如思考区块图更方便。区块图对色彩结构区分更直观。
外围延申的拓展图,从顶点延申的拓展图,都是若当曲线延申出来的子图,局部子图总满足一笔画要求,局部子图总满足三色定理。可解决3-着色问题。外围邻接色不超过三色,顶点邻接色也不超过三色。
冷色肯普链和暖色肯普链交替延伸,该两类偶闭链相互紧邻包围,于是已着色图要么是偶闭链,要么是偶开链,要么是单区块。最后或包含偶闭链终端子图,或包含偶开链终端子图,或包含单区块终端子图。其他为待着色图和可悔棋模式图,除可悔棋模式图外,其他闭链图作为邻接色皆不超过三色。a、b、c为向内待着色子图,d为向外待着色子图,与待着色图相邻的非闭链图,都不是新一轮邻接色闭链图,而是可悔棋模式图,其最后确定需要同待着色图提供结构确定的相邻区块形成闭链方可。
可见,作为NP完全的3-着色问题也是P问题。图着色问题之所以能够解决,是因为相邻闭链若存在奇闭链总能变成偶闭链 单区块,把单区块设置为待着色区块,加入到下一轮的偶闭链中,完成邻接色。如此一来,任何未着色区,都是三色可约图。因为总能被约当曲线闭链填充,或填满(包含偶闭链、偶开链和单区块),或分割为圈内圈外两部分,或分割为仅有圈内,或分割为仅有圈外,但可保证每次形成闭环的邻接色都不超过三色,未形成偶闭链时,从单区块出发的双色肯普链都属于“悔棋模式图”,要等待形成偶闭链或被偶闭链相邻包围后方可定色区分。
两类肯普链可持续着色下去,最后留下的都是终端子图。三元方程解集基底互素定理可判定高阶区块都可以用双色肯普链来区分,而任何给定地图都可以用一条线性连接高阶区块的高阶肯普链来表达。而任意线性世界用两类拓扑符号就足以区分(任意偶数用两个素数相加就足以得到),单连通的平面世界经历了从一阶到二阶,故用2x2=4类元素就足以区分,N维空间的最少单位区分数是2^N。
本站仅为学习交流之用,所有视频和图片均来自互联网收集而来,版权归原创者所有,本网站只提供web页面服务,并不提供资源存储,也不参与录制、上传
若本站收录的节目无意侵犯了贵司版权,请发邮件(我们会在3个工作日内删除侵权内容,谢谢。)
www.fs94.org-飞速影视 粤ICP备74369512号