地图着色问题算法分析 第3页
个三着色， 那么它可以很容易的转化成原图的三着色。因此， 我们可以通过找出加边后的三剖分三着色的方法来找出原图的三着色。
自由补全图的三着色
自由补全图的三着色是四色问题证明中的重要问题， 我们这里证明了自由补全图是平滑三剖分，因此以上的三着色算法可以直接用于自由补全图。
定义1 [ W近三剖分 三剖分加上它外面的无限区部分叫做近三剖分。
定义2 一 个 构 形 K 由 一 个 近 三 剖 分 G ( K ) 和 一 个 映 射 Y k : V ( G ( K ) ) 一 Z , 构 成 ， 而且Y k 具有以 下性质:
( 1 ) b ` 点 v ， G ( K ) \ ” 至 多 有 两 部 分 ， 若 有 两 部 分 ， Y , ( v ) 一 d , ( v ) + 2
( 2 ) V 点 v , 若 ” 与 无 限 区 不 相 关 联 ， 则 Y K ( v ) 一 d o ( v ) 。 否 则 Y K ( v ) > d . ( v )两 种 情 况 下 都 有7 K ( V ) > _ 5 。
( 3 ) K有环型z 2 ，环型定义如下:E( Y K ( v ) 一 d c ( v ) 一 1 ) 其中 F = ( v I v - 7 K 的 无 限区 相关 联， 且 G ( K ) \ A连 通 的 } 。
定义3自由 补全图
令K是构形，S 是近三剖分。如果满足:
( 1 ) R是S 的边界回路，且与S 的无限区相关联。
( 2 ) G ( K ) 是S 的 一 个导 出 子图 ， G ( K ) 一 S \ V ( R ) ， 任 何G ( K ) 的 有限 区 是S 的 有限 区， G ( K ) 的 无 限 区 包 含R 和S 的 无 限 区。 ( 3 ) 任 何 在5 中 不 在V ( R ) 中 的 点 、 在S 中 的 度 数 为 7 , ( V ) ,则称S 是构形K的关于环R的自由补全图。
K, S , R 如上所述。问题是要找出S 的所有三着色。若用穷举法，则对n个点的S ， 要 从3 ' 种 列举中 找出 正 确的 着色。 若。 二 2 5 ， 则 有1 4 3 4 7 9 0 7 种列举。构型的自由补全图边数一般在2 0以上，因此这个计算量是庞大的。
定义4 平滑三剖分: 若H中每一个三角区至少与另外两个三角区相关联， 则称这样的三剖分为平滑三剖分。
一般的， 一个三剖分可以拆成若干个平滑三剖分和一些非平滑三剖分， 这些非平滑三剖分为单个或者几个三角区组成的三剖分图， 它们的着色是容易的。因此只要给出了平滑三剖分的一个三着色算法， 就可以容易的给出任何一个三剖分的三着色。因此以下的算法只讨论平滑三剖分的三着色。
定理 1自由补全图S是一个平滑三剖分。
证明:当K变成3 时，K的边界上的每一个点最多新增3 条边， 这三条边至少围城两个区。否则有一个K中的顶点和无限区相关联，与自由补全图定义第 ( 2 )
条矛盾。
因此， 如果这三条边中有一条与无限区相关联， 则相邻两个顶点新增的边中要有两条边不相交， 则至少有两个点连不上， 因此也会有一个K中的顶点和无限区相关联，也与自由 补全图定义第( ( 2 ) 条矛盾。 也就是说， 如果S 中 有这样的脉: 它的第一个区r ] 有两条边与S 的无限区相关联， 则与上面的结论矛盾。因此S 是一个平滑三剖分。.
由于自由补全图是平滑三剖分的一种， 因此以下我们只考虑平滑三剖分的三着色问题就可以了。
三着色的脉及其性质
脉的思想来源很久，最初是由肯普在 1 8 7 9年在试图解决四色问题时提出的
“ 肯普链”的思想，N e i l R o b e r t s o n等人将其发展并用于四色问题中构形可约性的证明。 我从脉出发， 进一步提出脉组的概念， 并证明了覆盖平滑三剖分H所有区的脉组必然存在的定理。这一证明是后一部分着色算法的基础。
下面是H的三着色的有关脉的一些性质，以方便给出后面脉组的定义，并有助于定理的证明。
任何脉中，K ( g o ) , K ( g ] ) , . . . , K ( g r ) 的值是取士 1 且交替取值( 或者1 , 0 或者 1 , 0 ) ;任何与脉相关联，但不在脉中的边。 ，K ( e ) = 0 ( 或者‘ ( e ) 二 1 或者K ( e ) = - 1 ) ; 因 为 脉中 的 着 色 互换 不 会 影 响 每 一 个 区 仍 然由 三 种 颜 色 着 色， 所以K ( g o ) , K ( g , ) , . . . , K ( g , ) 的 值 取 异 号 时 ， 可 得 H 的 一 个 新 的 三 着 色 ; 任 意 两 个 脉 不 相交，即两个不同的脉没有公共的边或者区，因为若相交， 则相交区的三条边只用到 两 种着 色， 矛 盾; 对 于1 ， - 1 交 替 的 脉， 对1 5 i < _ k ， 若r c ( g i ) = 土 1 ， 则g i 属于 唯 一一 个 脉;K ( g i ) 一 。 ， 则g ‘ 不 属于 任 何 一 个 脉。 事 实 上， 当S 的 一 个着 色给定了时，S中的脉就己经固定了下来。
如果一个区有两条边在一条脉中， 我们称此区被这条脉通过。 一个区不在脉中但是与脉中的一个区有公共边， 我们称此区与脉关联， 公共边与脉的关系也称为相关联。
我从以上性质出发，对脉作了进一步的探讨，得到以下有用的性质:
性质1 一个区不能与不同的脉同时关联。
若有一个区与两个不同的脉相关联，则有它的两条边同时取O o
性质2一个脉也不能与一个区的两条边相关联。( 不交的另一种形式)
若有，则此区两条与脉关联的边同时取0 ，矛盾。
脉组存在性定理
定义 脉组:是指一个H的三着色中那些全为 1 ，- 1( 或者全为0 ，- 1 或者全为0 , 1 )交替的一组脉正好把H的所有区所覆盖。
下面给出了覆盖平滑三剖分H所有区的脉组的存在性定理。
定理2对平滑三剖分H的任一个三着色，存在一个脉组。
证明:只须证H的一个区必然属于H的一个脉。以下仅讨论1 ，- 1 的脉组即可，0 , 1 和一 1 , 0 的脉可以有类似的讨论。
设二 为H的 一 个 三 着 色， 区; 的 边e , . f , g 分别 着一 1 , 1 , 0 ， 则由 平 滑三 剖分的定 义， ; 必 与 另 外 至 少 两 个H的 区 相 关 联， 设 其中 两 个 为‘ ， r , ， 不失 一 般 性， 设r , 与e , f 中 一 条 边 相 关 联， 不 妨 设 为 f ， 则r , 中 其 余 两 条 边 着 色 为 一 1 , 。 ， 对‘ ，若r , 的 着 一 1 的 边厂 不 是H的 边 界R 中 的 边， 则由 于H是 一 个平 滑三 剖分， 它 必与 一 个 另 一 个H的 区r 2 相 关 联， r 2 与r i 共 用 一 条 边关 ， r 2 中 另 外 两 条 边 着1 , 0 ,设 着1 的 边 为关， 这 样 找 下 去 ， 直 到 找 到 一 个 区 ， 它 着1 或 着 一 1 的 边 是 R 中 的边 为 止， 设 最 终 找 到 的 这 个 边 为几， 记 从 f 开 始的 一 1 , 1 交 替出 现 且 跨 越f , r i , f , r 2 , f 2 , . . . , m , f的 带 子 为r t b l , f r i f , r 2 f . . . . f . ;
对 : 的 着 一 1 的 边 ， 要 么 。 是 H 的 边 界 R 中 的 边 ， 此 时 “ r f r , f i r a . 二 即 。 + r i b l是H中的一条脉， 显然; 属于此脉;要么“ 不是R中的边， 类似于前面的找法，可得另一半带子r i b 2 ，合并r i b l 和r i b 2 ，可得一个脉，显然r 属于此脉。因此H的任何一个区都属于一个脉。由脉的性质， 一个区只能属于一个脉，脉和脉不相交，因此H可以由脉的组合覆盖，即对任一个三着色，H存在一个脉组。.推论1脉中除了 两端外，还有可以在脉中间有一条在E ( R ) 中的边。
因为 在 三着色中， { l , - 1 } 组成的 脉组 和{ { 0 , - 1 }
上一页 [1] [2] [3] [4] [5] [6] [7] 下一页
地图着色问题算法分析 第3页下载如图片无法显示或论文不完整，请联系qq752018766
