路人书

手机浏览器扫描二维码访问

第九十六章 四色猜想（第1页）

“知文，你瞄我干嘛？我可没说要参加ACM世界编程大赛？”吴哲开着沈知文的玩笑。

沈知文也不回话，两眼就直直地盯着吴哲。被沈知文这么盯着，吴哲只能投降。

“知文，这就是你找人帮忙的态度？这都快赶上威胁了。”吴哲笑着说道。

正说笑间，汪潮骂了句：“挖槽。”就见电脑死机黑屏了。

“汪大少，你又干什么了？看小电影了？你年纪还小，别弄那些有的没的？”黄明海调笑着汪潮。

不过虽然是玩笑话，几人还是很好奇的。毕竟电脑是沈知文这个高手配的，配置高，而且自己宿舍的防护都是沈知文和吴哲自己编写的陈序，而且汪潮的电脑水平也不低。要说是电脑病毒和被人黑了，不可能汪潮连一点反应也没有。

“呸，你才看小电影呢？我这运行下我写的程序，没想到刚运行就不行了。我这还找不出原因。”汪潮脸色通红地说道。妈的，好坏自己也算天才吧！写个程序能把自己宕机，汪潮不脸红才怪。

“知文你来帮我看看，这什么鬼？”实在找不出原因，汪潮也只能找沈知文了。

沈知文凑过来看了看，然后又仔细检查了下。动手敲下确认键运行，电脑依然是宕机了。

里里外外检查了下，没找出毛病。可只要一运行汪潮编写的程序，就会宕机，可沈知文检查了下代码，逻辑是通的，编码也没问题。系统也没报错，可就是运行不了。这现象还是第一次碰到。

“汪潮，你先别弄了，学校选拔考试快开始了。你和吴哲先去考，我和知文先帮你看看怎么回事？”黄明海看了下时间说道。

“嗯，那我们先去考试。“汪潮也知道轻重。

转身又招呼吴哲道：”走了，阿哲！”

“你一个人去吧！我就不去了。”吴哲笑着回道。

几人一脸疑惑地看着吴哲，你不去了？这算什么？当时可是在水木大学放了话的。吴哲要不参加，那他们几人以后都没脸见其他高校的人。

吴哲看其他几人神色，也知道不能再开玩笑了。笑着说道：“前两天学院通知我不用参加选拔考试了，怕耽误开心网的事情，我可以直接去参加丘赛。所以汪潮你需要一个人过去了，好好考，我看好你哟！”

“MMP！”汪潮现在只想大骂一声。

沈知文和黄明海见不是吴哲不参加丘赛，悬着的心也放了下来。都开始调笑汪潮。

汪潮出门前就只能做了个竖中指的手势。

吴哲等汪潮出门后，也开始查看起汪潮写的程序起来，代码没问题。吴哲慢慢看了起来，逻辑看起来也自洽。吴哲皱起眉头思考起来。

“嗯？这地方好像很眼熟啊！”吴哲眼光亮了亮，然后找汪潮的笔记本，看起他的建模思路来，脑中也是高速运转。

“知文，别忙活了。我应该知道问题所在了。”吴哲开口道。

“什么问题？”沈知文问道。

“呵呵，汪潮的心太大，你看这四个指标。上涨—下跌—整理—震荡，再带入其它参数，对于其的渲染结果做出判断。这种判断你看像什么？

“四色猜想？”沈知文立马反应过来。“艹，汪潮他怎么想的。这机器不宕机就怪了。”

“估计他自己也没反应过来，认为逻辑自洽就行了。这不宕机就怪了。计算量太大，可能需要超算才能完成。”吴哲笑着说道。

“而且他不光搞了一个四色问题的世界性难题，涉及图论那块他还搞了个西塔潘猜想出来。我都不知道说他是天才还是蠢材了。两个没证明的猜想能拿来运用，而且逻辑还是自洽的。回来我要逼着他给证明了。”汪潮恨恨说道。

“这没证明怎么就不能用了，1+1=2还没证明呢？不照样用。再说四色问题不是已经在计算机上面证明了吗？”黄明海在旁边说道。

“那只是把四色问题算到了100亿次没出错而已，一天没在数学逻辑上给出证明就还没完。”说完吴哲倒是来了兴趣，拿起笔和草稿纸开始证明起来。

——————

1852年，毕业于伦敦大学的格斯里，来到一家科研单位搞地图着色工作时，发现每幅地图都可以只用四种颜色着色。他就想着这个现象能不能从数学上加以证明呢？只能说是吃得太饱闲的，格斯里和他的弟弟还真就研究上了，最后还拉上了他弟弟的老师、著名数学家德·摩尔根，可到死几人也没研究出来。

直到1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题，世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1880年的时候，数学家利用归谬法来证明：大意是如果有一张正规的五色地图，就会存在一张国数最少的“极小正规五色地图”，如果极小正规五色地图中有一个国家的邻国数少于六个，就会存在一张国数较少的正规地图仍为五色的，这样一来就不会有极小五色地图的国数，也就不存在正规五色地图了。这样肯普就认为他已经证明了“四色问题”，但是后来人们发现他错了。

1922年费兰克林证明了每个有至多25个国家的地图都可以用四种颜色着色。1926年雷诺德将这一结果推广到27个国家，然后在1938年费兰克林又创造了31个国家的纪录。1940年温恩证明了35个国家的情形以后，这方面的研究有所停滞，直到1970年，奥尔和史坦普尔对所有至多包含40个国家的地图证明了四色定理。在哈肯和阿佩尔最终证明四色定理而使所有这类结果都黯然失色以前，这个数字曾经达到了96。

1950年德国数学家希许就曾估计，证明四色猜想大概要涉及一万个不同构形。虽然后来证明他的估计是过分夸大了，但它却正确地指明了，四色问题也许只有借助于能处理巨量数据的强有力的计算装置才能获得解决。

1972年哈肯与阿佩尔联手，经过整整四年的紧张工作，终于在1976年6月他们用三台计算机花费了1200个计算机小时，处理了两千多个构形，才算验证了四色问题成立。可对于数学家来说肯定是不满意的。

——————

吴哲先从着色判定问题入手：设已知一个图g和m>0种颜色，在只准使用这m种颜色对g的结点着色的情况下，是否能使图中任何相邻的两个结点都具有不同的颜色呢?

再从m-着色最优化问题则求可对图g着色的最小整数m。这个整数称为图g的色数。这是求图的最少着色问题，来求出m的值。

for（i=1;i<=n;i++）

{

if（DFS（0，i））

{

cout<<“themincolors:“<<i<<endl;

break;

}

}

------

看小说，630book

请关闭浏览器阅读模式后查看本章节，否则将出现无法翻页或章节内容丢失等现象。