寶石方塊與圖的著色理論2~從數學定義開始

Def. Pn(G) = { (u,v) 存在 a length n-1 path connect u and v in G}

Def. Pn(u,v) = { (u=x_1 , x_2 , ... , v=x_n) (u,v) in Pn(G) and d(x_i , x_i+1) = 1 , i=1,2 ... n-1}

Def. C : V(G) -> N is a coloring function on vetex of G , N is natural number

Def. δ : V x V -> {0,1}
δ(x_i , x_j) = 0 if C(x_i) ≠ C(x_j)
δ(x_i , x_j) = 1 if C(x_i) = C(x_j)

Def. Π(u,v) : Pn(u,v) -> {0 , 1}

Π(u,v) =Πi=1 ,2,...n-1 δ(x_i , x_i+1) 註:這是連乘

Def. (Coloring Extension)

C(G,Pn): V(G) -> N={0 , 1 , 2 ...m-1} is a m-coloring for Pn in G satisfying as follow:
for all (u,v) in Pn(G) 則 Π(u,v) = 0 and we denote the C(G,Pn)= m

Def. (Chromatic Number For Coloring Extension)

X(G , Pn) = min { |C(G,Pn)| = m | C(G,Pn) is a m-coloring for Pn in G}

把上述一連串定義中的 n = 2 就是我們最原始兩點相連不同色的著色問題 , 至於寶石方陣的著色問題是建立在 n=3 且 G = Grid Graph with 8 x 8
Remark:
1. G is a Grid Graph with n x n X(G, P_3) = 2
2. G is a Cyclic Graph Cn X(Cn, P_3) = 2
3. G is a Kn X(Kn, P_3) = n/2 的上高斯 (why!? Because every color can't exceed 2)

在來重點是我要用數學定義 Swap 這個動作 :
Def. C* is a set that collect all coloring function C on V(G) we denote
C*={ C | C : V(G)-> N }
C*(G,Pn) is a set that collect all m-coloring for Pn in G we denote
C*(G,Pn) = { C(G,Pn)| C(G,Pn) : V(G) -> N }
註 : 很明顯 C*(G,Pn) is a subset of C*

Def. ( A Swap transform between two coloring function in G) We define a swap transform S : (C*, V(G) , V(G)) -> C* S(C_1 , a , b )= C_2 such that
C_2(x)=C_1(x) if x≠a and x≠b
C_2(x)=C_1(b) if x=a
C_2(x)=C_1(a) if x=b
現在將Swap的動作加入我們原本考慮的 m-coloring for Pn in G , 我要再定義一個變形的Chromatic Number with Swap Operator

Def. XS(G , Pn ) = min { |C(G,Pn)| | S( C(G,Pn) , a , b ) always lie in C*(G,Pn) for all (a,b) ∈ E(G) }

(待續)