路线着色问题是图论中?这个猜想认为,可以绘制一张“万能地图”,指导人们到达某一目的地,不管他们原来在什么位置.具体点是怎样的
来源：学生作业帮助网 编辑：六六作业网 时间：2024/05/11 16:31:23
路线着色问题是图论中?这个猜想认为,可以绘制一张“万能地图”,指导人们到达某一目的地,不管他们原来在什么位置.具体点是怎样的
路线着色问题是图论中?
这个猜想认为,可以绘制一张“万能地图”,指导人们到达某一目的地,不管他们原来在什么位置.
具体点是怎样的
路线着色问题是图论中?这个猜想认为,可以绘制一张“万能地图”,指导人们到达某一目的地,不管他们原来在什么位置.具体点是怎样的
这个难题的假设是,在出发点（圆点）及道路（直线）的数量都固定的情况下,应该有办法以不同颜色标示道路,让人不管从哪一个点出发,都能到达固定的点.这在真实生活中的情况就像是,不管朋友住在哪里,只要知道你家的位置,绕再远都有办法到你家.
以图为范本（图取自维基百科,无法在此引用）,如果按照「蓝—红—红、蓝—红—红、蓝—红—红」(这是道路的颜色)的方式行走,不管从哪个点出发都能到黄色(这是指某一点)的点；如果是「蓝—蓝—红、蓝—蓝—红、蓝—蓝—红」,则一定能到绿点
In graph theory the road coloring theorem, known until recently as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can re...
全部展开
In graph theory the road coloring theorem, known until recently as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network (which might be a representation of city streets or a maze).[1] In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. This theorem also has implications in symbolic dynamics.
The theorem was first conjectured in 1970 by Benjamin Weiss and Roy Adler.[2] It was proved by Avraham Trahtman in September 2007. [3]
收起