23

“中广网北京6月21日报道:最近,全球数学界兴奋无比——困扰科学界近40年的一道谜题,最近终于被以色列巴尔伊兰大学数学家艾夫拉汉·特雷特曼破解。他成功解决了所谓的路线着色问题。
网上搜索相关条目,其实2008年3月20日就有的媒体相关报道:
63-year-old solves riddle from 1970
Israeli mathematician unravels puzzle that baffled scientists for decades
Israeli immigrant mathematician solves math riddle
Road coloring problem

“路线着色问题是图论中最著名的猜想之一。是犹太裔美国数学家和计算机专家本杰明·韦斯和他在IBM工作的同事罗伊·艾德勒于1970年首先提出来的。他们认为,如果路线的数量有限,人们应该能画出一张地图,标上不同的颜色,把人引导到某一目的地。路线着色问题可以通俗解释为,“一个人来到他从未造访过的小镇上,驾着车到处寻找他朋友的家,即使连路名都没有。朋友说,别担心,他会指示他如何到达,先向左,再向右,接着向左……”

“这个难题的假设是,在出发点(圆点)及道路(直线)的数量都固定的情况下,应该有办法以不同颜色标示道路,让人不管从哪一个点出发,都能到达固定的点。这在真实生活中的情况就像是,不管朋友住在哪里,只要知道你家的位置,绕再远都有办法到你家。以图为范本,如果按照蓝—红—红的方式行走,不管从哪个点出发都能到黄色的点;如果是蓝—蓝—红则一定能到绿点...

Avraham Trakhtman
Avraham Trakhtman, a mathematician who worked as a laborer after immigrating to Israel from Russia, has succeeded where dozens have failed, solving the elusive "Road Coloring Problem."

“今年63岁的特雷特曼出生在俄罗斯叶卡捷琳堡,1972年在乌拉尔州立大学获得数学博士学位,之后在乌拉尔科技大学任教。但是犹太人身份使他在工作中受到歧视和排挤。尽管特雷特曼在1992年移居以色列之前就是一位颇有造诣的数学家,但他刚到以色列时身无分文,为养家糊口他经常去教会领救济品,后来在好心人的介绍下,他成了一名值夜班的保安员,但生活仍然十分艰苦。1995年,特雷特曼被聘为巴尔伊兰大学的教员。当年把他招进巴尔伊兰大学的马戈利斯回忆说,“我第一次见到他时,他穿着守夜人的制服,不修边幅,衣服很脏。”

“以色列人也为特雷特曼取得的成就感到无比的骄傲。特拉维夫电视台中断了正常的节目播放,以第一时间发布了这一重大消息,连中东其他国家的主流媒体也作了大篇幅的。世界上众多著名学术刊物编辑部得知此事后,纷纷向他约稿,但他最终决定把论文发表在即将出版的《以色列数学杂志》上。

On this day..

6 Responses to “Road Coloring Problem”

  1. qiusir Says:

    Wikipedia Road coloring problem
    http://en.wikipedia.org/wiki/Road_coloring_problem

  2. qiusir Says:

    完整证明过程可以在这篇论文里找到:
    http://arxiv.org/abs/0709.0099

  3. 传奇世界私服 Says:

    科学证明一切啊

  4. mydear255 Says:

    我的注册什么时候能通过啊?在哪里发文?

  5. qiusir Says:

    mydear255 我今天一定给你认证!

  6. qiusir Says:

    mydear255
    通过认证。