毕业论文论文范文课程设计实践报告法律论文英语论文教学论文医学论文农学论文艺术论文行政论文管理论文计算机安全
您现在的位置: 毕业论文 >> 课程设计 >> 正文

地图着色问题算法分析 第4页

更新时间:2009-7-1:  来源:毕业论文
地图着色问题算法分析 第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
设为首页 | 联系站长 | 友情链接 | 网站地图 |

copyright©751com.cn 辣文论文网 严禁转载
如果本毕业论文网损害了您的利益或者侵犯了您的权利,请及时联系,我们一定会及时改正。