2016年2月 8日更新

グラフの彩色

PDF版

濃度については順序数・濃度の簡単なまとめも参照.

定義 V が集合, E が V 上の二項関係で非反射的かつ反対称的なとき,組 G=(V, E) をグラフという.

定義 G=(V, E) をグラフとする.

  1. S⊂V が従属(dependent) ⇔ ある x, y∈S が存在して xEy となる.
  2. S⊂V が独立(independent) ⇔ S が従属でない.
  3. 写像 f: V→C が「任意の c∈C に対して f-1(c)⊂V が独立である」を満たすとき, f を彩色(coloring)と呼ぶ.
  4. 彩色 f: V→C が存在するとき, G は |C|-彩色可能であるという.
  5. χ(G) := min{ λ | G は λ-彩色可能である } が存在するとき,χ(G) を G の彩色数(chromatic number)という.
  6. f: V→C が既約(irreducible) ⇔ 任意の c, d∈C,c≠d に対して f-1(c)∪f-1(d) が従属となる.

定義 集合 X, Y に対してグラフ G(X, Y)=(X×Y, E0) と G'(X, Y)=(X×Y, E1) を次により定める.

<x, y>E0<x', y'> ⇔ (x=x', y≠y')または(x≠x', y=y')
<x, y>E1<x', y'> ⇔ x≠x'かつy≠y'

定理1 次の命題は( ZF 上)同値.

  1. 選択公理
  2. 任意のグラフの彩色数が存在する.
  3. 任意の集合 X に対して,グラフ G'(X, Γ(X)) の彩色数が存在する.

証明 (1 ⇒ 2)彩色は任意のグラフに対して存在するから,選択公理により最小元 χ(G) = min{ λ | G は λ -彩色可能である } も存在する.

(2 ⇒ 3) 明らか.

(3 ⇒ 1) グラフ G := G'(X, Γ(X)) は |X|-彩色可能かつ |Γ(X)|-彩色可能である.故に χ(G)≦|X| かつ χ(G)≦|Γ(X)| となる. χ(G)=|Γ(X)| と仮定すると |Γ(X)|=χ(G)≦|X| となり矛盾するから, χ(G) < |Γ(X)| である.

|C|=χ(G) となる集合 C と彩色 f: X×Γ(X)→C を取る. |C| < |Γ(X)| だから C は整列順序集合としてよい.x∈X,c∈C に対して A(x, c) := { α∈Γ(X) | f(x, α)=c } と置く.任意の x∈X に対してある c∈C が存在して |A(x, c)|≧2 となる.

そうでないと仮定する.即ちある x∈X が存在して,任意の c∈C に対して |A(x, c)|≦1 となるとする.このとき f(x, -): Γ(X)→C は単射である.故に |C| < |Γ(X)| に矛盾する.

よって g(x) := min{ c∈C | |A(x, c)|≧2 } と定義することができる.この g: X→C は単射である.

g が単射でないと仮定すると, x, y∈X で x≠y,c := g(x) = g(y) となるものが取れる.このとき α, β∈Γ(X) で f(x, α)=c,f(y, β)=c となるものが存在するから f が彩色であることに矛盾する.

故に |X|≦|C| となり X は整列可能である.

証明から,次の同値も成り立つことが分かる.

定理2 選択公理 ⇔ グラフ G が λ0-彩色可能かつ λ1-彩色可能ならば,ある基数 μ が存在して μ≦λ0,μ≦λ1 かつ G がμ-彩色可能となる.

更に,次も成り立つ.

定理3 選択公理 ⇔ グラフ G が λ0-彩色可能かつ λ1-彩色可能ならば,ある基数 μ が存在して μ≦*λ0,μ≦*λ1 かつ G がμ-彩色可能となる.

証明 ( ⇒ ) 明らか.

( ⇐ ) X を集合とする.グラフ G'(X, Γ(P(X))) は |X|-彩色可能かつ |Γ(P(X))|-彩色可能だから,仮定により,ある基数 λ が存在して, λ≦*|X|,λ≦*|Γ(P(X))| かつ G'(X, Γ(P(X))) が λ-彩色可能である. λ < |Γ(P(X))| となる.

λ≦*|Γ(P(X))| で Γ(P(X)) が整列可能だから, λ≦|Γ(P(X))| となる. λ=|Γ(P(X))| と仮定すると |Γ(P(X))|≦*|X| である.即ち全射 f: X→Γ(P(X)) が存在する.このとき f-1: Γ(P(X))→P(X) は単射であり矛盾する.

よって定理1の 3⇒1 の証明と同様にして X が整列可能であることがわかる.

定理4 次の命題は( ZF 上)同値.

  1. 選択公理
  2. 任意のグラフは既約な彩色を持つ.
  3. 任意の集合 X に対して,グラフ G(X, Γ(X)) は既約な彩色を持つ.

証明 (1 ⇒ 2) (V, E) をグラフとする. V の整列順序 ≦ を取る. f: V→V を f(x) := min(V\{ f(y) | y<x, yEx }) で定めれば f は既約な彩色である.

(2 ⇒ 3) 明らか.

(3 ⇒ 1)無限集合 X が整列可能であることを示す.仮定3より, G(X, Γ(X)) の既約な彩色 f: X×Γ(X)→C が存在する. π1: X×Γ(X)→X,π2: X×Γ(X)→Γ(X) を標準射影とする.c0∈C を一つ取り, M := f-1(c0),S1 := π1(M)×Γ(X),S2 := X×π2(M),C1 := f(S1),C2 := f(S2) と定める.

f は彩色だから, c∈C に対して π1|f-1(c)2|f-1(c) は単射である.よって |π1(M)|=|f-1(c0)|=|π2(M)| となる.また |f-1(c)|≦|Γ(X)| となり, f-1(c) に整列順序が入る.よって S⊂X×Γ(X) に対して写像 g: f(S)→S を g(c):=min(S∩f-1(c)) で定めることができる.この g は明らかに単射である.故に |f(S)|≦|S| となる.従って |C1|=|f(S1)|≦|S1|=|π1(M)×Γ(X)| となり C1 も整列順序が入る.また

|C2|=|f(S2)|≦|S2|=|X×π2(M)|=|X×π1(M)|≦|X×X|

となる. Γ(X)=Γ(X×X) だから, |Γ(X)|\not\leq|C2| である.一方, x∈X に対して Γ(X)∋α|→f(x, α)∈C は単射である.故に Ax := { <w, c>∈Γ(X)×C1 | f(x, α)=c } ≠ ∅ となる.Γ(X),C1 は整列されているから h: X→Γ(X)×C1 を h(x) := min(Ax) で定めることができる.この h は単射だから X も整列可能である.

参考文献

コメント

コメントはまだありません。

コメントする

感想、意見、質問など何でもどうぞ。
※書き込んだのに表示されない場合は、ページをリロードしてみてください。