词条 | 图着色问题 |
释义 | 图着色问题(Graph Coloring Problem, GCP) 又称着色问题,是最著名的NP-完全问题之一。 一,路线着色问题是图论中最著名的猜想之一。通俗的说,这个猜想认为,可以绘制一张“万能地图”,指导人们到达某一目的地,不管他们原来在什么位置。这个猜想最近被以色列数学家Avraham Trahtman在2007年9月证明。 举个例子。在维基网给出的图例中,如果按图中所示方式将16条边着色,那么不管你从哪里出发,按照“蓝红红蓝红红蓝红红”的路线走9步,你最后一定达到黄色顶点。路线着色定理就是说在满足一定条件的有向图中,这样的着色方式一定存在。严格的数学描述如下。我们首先来定义同步着色。G是一个有限有向图并且G的每个顶点的出度都是k。G的一个同步着色满足以下两个条件:1)G的每个顶点有且只有一条出边被染成了1到k之间的某种颜色;2)G的每个顶点都对应一种走法,不管你从哪里出发,按该走法走,最后都结束在该顶点。有向图G存在同步着色的必要条件是G是强连通而且是非周期的。一个有向图是非周期的是指该图中包含的所有环的长度没有大于1的公约数。路线着色定理这两个条件(强连通和是非周期)也是充分的。也就是说,有向图G存在同步着色当且仅当G是强连通而且是非周期的。 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。