地图着色问题算法分析 第4页
{ 1 , 0 } 组成的 脉组性质是等 价的，我们只需 要研究{ l , - 1 ) 组成的 脉组 就可以了， 而其余 两种情况可以 类似的 得到•为叙 述方便，以 下 再提到脉组时， 如不加特别注明， 就是 指{ { l , - 1 } 组成的。
由以上分析我们立即得到脉组和着色数日 之间的关系:
定理3对一个n 个区的三剖分图S 进行三着色，若S 有l 个脉组，设脉组大小为共 S = i 〔 即 脉组中 脉的 个 数) ，1 = 1 ，2，……l ， 则 每 个脉 组的 着色 有3 * 2的Mi次方种着色。
四、着色实例
我们通过计算机模拟本文算法的执行，给出了北京市地图所有三着色方案，
根据第四章的方法我们把它们转化为四着色。
北京市共有1 8个区县，为了方便，我们把市中心的崇文、东城、西城、宣
武四区看做一个 “ 市中心区” ，那么就成了 巧 个区。转化成的平滑三剖分共有
2 0 个区，1 5 个顶点，3 4 条边，如图所示。
本例2 0个区共生成了2 4 0 个编码 ( 在生化实验中考虑着色信息应当为4 8 0
种编码) 。我们将区的个数和 3 4条边依次输入程序，生成第一个区的编码 ( 1 2
个)输出结果如下:
T r u e , T r u e , 1 2 , 1 , 1 , 1 4 , F a l s e , F a l s e ，
T r u e , F a l s e , 1 2 , 1 , 1 1 4 , F a l s e , T r u e
F a l s e , T r ue , 1 2 , 1 , 1 1 4 , T r ue , F a l s e ，
F a l s e , F a l s e , 1 2 , 1 , 1 1 4 , T r ue , T r ue
T r ue , T r ue , 0 1 , 1 , 1 2 , T r ue , T r ue ，
T r ue , T r ue , 0 1 , 1 , 1 2 , F a l s e , F a l s e
T r ue , T r ue , 0 1 , 1 , 1 2 , T r ue , F a l s e ，
T r ue , T r ue , 0 1 , 1 , 1 2 , F a l s e , T r ue
T r ue , T r ue , 0 1 , 1 , 1 1 4 , T r ue , T r ue ，
T r u e , T r ue , 0 1 , 1 , 1 1 4 , F a l s e , F a l s e
T r ue , T r ue , 0 1 , 1 , 1 1 4 , T r ue , F a l s e ，
T r ue , T r ue , 0 1 , 1 , 1 1 4 , F a l s e , T r ue
通过以上编码，共找到了7 7 1 2种脉，但是由于最后找到的脉只与区及边的信息有关， 所以不考虑布尔变量的值如何， 脉中有大量的重复。 如果只输出脉中的边和区，我们推测，这些无重复的脉的个数将为 7 7 1 2的1 / 4 左右。如下面是我们找到的一条脉:
Tr ue Tr ue 0 5 5 5 6 Tr ue T r ue
F a l s e F a l s e 5 6 6 6 7 T r ue T r ue
F a l s e F a l s e 6 7 7 7 8 T r ue T r ue
F a l s e F a l s e 7 8 8 8 9 T r ue T r ue
F a l s e F a l s e 8 9 9 9 1 0 T r ue T r ue
F a l s e F a l s e 9 1 0 1 0 1 0 1 5 T r ue T r ue
F a l s e F a l s e 1 0 1 5 1 5 1 5 1 6 T r ue T r ue
F a l s e F a l s e 1 5 1 6 1 6 1 6 1 7 T r ue T r ue
F a l s e F a l s e 1 6 1 7 1 7 1 7 1 8 T r ue T r ue
F a l s e T r ue 41 8 1 8 1 7 1 8 T r ue F a l s e
F a l s e T r u e 3 4 4 4 1 8 T r ue F a l s e
F a l s e T r ue 2 3 3 3 4 T r ue F a l s e
F a l s e T r ue 1 2 2 2 3 T r ue F a l s e
F a l s e F a l s e 1 2 1 1 1 4 T r ue T r ue
F a l s e Fa l s e 1 1 41 41 31 4 Tr ue Tr u e
T r ue T r ue 0 1 3 1 3 1 3 1 4 T r ue F a l s e
以上每一行是一个编码，1 6 个编码可以依次发生互补反应，连成一个长链。可以看出，这条脉依次经过5 , 6 , 7 , 8 , 9 , 1 0 , 1 5 , 1 6 , 1 7 , 1 8 , 4 , 3 , 2 , 1 ,1 4 , 1 3 等1 6 个区。
找到所有的脉后，程序自动执行 1 0步循环，就可以找出所有的脉组。我们总共找到了5 7 2 4种脉组，只考虑边和区的话它们中间也有若干相同的，但是我们也没有找出重复出 现的规律。下面是从中 选出的一个由 分别具有4个区、1 6个区的两条脉组成的脉组:
[ 1 ] : T r u e T r u e 0 1 1 1 1 4 F a l s e T r u e
[ 2 ] : T r u e F a l s e 1 3 1 4 1 4 1 1 4 F a l s e F a l s e
[ 3 ] : T r u c T r u e 1 2 1 3 1 3 1 3 1 4 F a l s e F a l s e
[ 4 ] : T r u e T r u e 0 1 2 1 2 1 2 1 3 F a l s e F a l s e
[ 1 ] : T r u e T r u e 0 2 2 2 3 T r u e T r u e
[ 2 1 : F a l s e F a l s e 2 3 3 3 4 T r u e T r u e
上一页 [1] [2] [3] [4] [5] [6] [7] 下一页
地图着色问题算法分析 第4页下载如图片无法显示或论文不完整，请联系qq752018766
