On chromatic polynomials of graphs

グラフの彩色多項式

On chromatic polynomials of graphs

数学専攻 長谷川 祐子 HASEGAWA Yuko

1

数学における最も有名な定理の１つに4色定理(four-coloring theorem)が挙げられる. 4色定理とは,任意の平 面的グラフ(planar graph)は4彩色可能であるというものである. これを証明することは,一見簡単そうに見える が難しく, 1852年に予想され, 1976年に証明されたが,現在でもコンピュータを使用しない証明は得られていない.

この定理は実用的には携帯電話の基地局配置に応用されている.周波数の同じ電波同士で混信してしまう携帯 電話システムでは隣接する基地局同士に同じ周波数を割り当てないように塗り分ける必要がある.

また,グラフ理論においては,一般のグラフの彩色問題があり,その1つが,彩色多項式である.彩色多項式とは, 頂点とその頂点を結ぶ辺からなるグラフにおいて,隣り合う頂点は異なる色であるという条件で彩色するとき,彩 色方法は何通りあるかを多項式で表したものである.彩色多項式についてのいくつかの論文では,この多項式の有 効な計算方法を論じている.それらのほとんどは,指数時間で計算しており,辺を 縮約/削除 する方法を使用して いるが,今回は, P.Berthom´e, S.Lebresne, K.Nguyˆen[3]らが考案している弦グラフを用い,辺を 加える/縮約 する 方法を紹介する.また[3]では,アルゴリズムの改良を考察する際に, thicknessやfill-inに関して注目していたが, この論文では特に完全2部グラフに関して, thicknessとfill-inと木幅の関係について示した.この論文では,グラ フG= (V, E)とは有限な単純無向グラフであるとする.

2

グラフGに対して,Gの頂点をλ色に塗り分け,隣接している頂点は異なった色で塗る.これをGの彩色とい う.整数λ≥0に対し,高々λ色を使ったGの頂点の異なる彩色の個数P(G, λ)はλに関する多項式になること が知られている.これを彩色多項式(chromatic polynomial)という.

以下のTheorem 1を用い,空グラフ,完全グラフ,木の彩色多項式を計算することができる.

Theorem 1 (本論文定理1) P( ¯K_n, λ) =λⁿ P(K_n, λ) =λ⁽ⁿ⁾=

n−1

i=0

(λ−i) P(T_n, λ) =λ(λ−1)ⁿ⁻¹

縮約はDefinition 1のように定義され,グラフの彩色多項式は, Theorem 2の漸化式で計算することができる.

Definition 1 (本論文定義1) グラフG= (V, E)において,p, q∈V,e= (p, q)∈Eとする.このとき,辺eを除 去し,その端点p, qを同一視して新たな頂点rにする操作を,辺eの縮約(contraction)といい,G/eで表す.グラ フG/eにおいて,その新たな頂点rは,pとqが隣接していたV − {p, q}のすべての頂点と隣接している.

以下では,G/eはGからeを縮約して得られたグラフの多重辺とループは取り除いたグラフを表すものとする.

さらに,e= (p, q)を縮約して生じる頂点rをpで表すことにする.

1

Theorem 2 (本論文定理2) グラフG= (V, E)において,e∈ E のとき,Eから辺eを除いて得られるグラフ をG−eとし,縮約して得られるグラフをG/eとする.このとき,P(G, λ) = P(G−e, λ)−P(G/e, λ)· · ·(1)が成り 立つ.また,e∈Eのとき,Gに辺eを加えて得られるグラフをG+eとする.このとき,P(G, λ) = P(G+e, λ) + P((G+e)/e, λ)· · ·(2)が成り立つ.

この論文では, (2)式の辺を 加える/縮約 する方法を使用していく.これを改良するために弦グラフを用いる.

Definition 2 (本論文定義2) 弦グラフGのクリークグラフ(clique graph)G= (V,E)とは,V={c1, c2, . . . , cm} はGの極大クリーク全体の集合であり,E ={(c_i, c_j)|c_i, c_j ∈ V, c_i =c_j, c_i∩c_j =∅}のようなグラフである.こ こで,クリークグラフGの辺(ci, cj)は,ci∩cjがグラフGの頂点集合の空でない部分集合に対応すると考え,辺 (c_i, c_j)の重みは|c_i∩c_j|で与えられているとする.

Theorem 3 (本論文定理3) T = (V,E)がクリーク木(clique tree)であるための必要十分条件は,Gのクリーク グラフの最大重み全域木がTであることである.

クリーク木は与えられたグラフGが弦グラフのときに定義されたので,グラフが弦グラフでない場合はグラフ を三角形分割し,そのクリーク木を求める.

Definition 3 (本論文定義4,5,6) グラフG= (V, E)において,Gの三角形分割(trianguration)F とは,

G = (V, E∪F)が弦グラフであるような辺の集合のことである.また,このようにFを加えることを三角形分割

するという.Gの三角形分割全体の集合をFとする.

Gのfill-inとは,三角形分割F の要素の数|F|のことであり,min

F∈ F|F|をGの最小fill-in(minimumfill -in)と いう.(三角形分割FをGのfill-inということもあるが,この論文では要素の数を表すことのみに使う.)

グラフG= (V, E)において,FをGの極小三角形分割(minimal triangulation),T = (V,E)をG= (V, E∪F) のクリーク木とする.このとき,φ(V_i, V_j) =F∩E(G[V_i∩V_j])は部分集合FによるEのラベルであり,Fに関し てGの増加クリーク木(augmented clique tree)をT = (V,E, φ)とする.G[U]はV(G)の部分集合U によって誘 導されたGの部分グラフである.

グラフG= (V, E)において,FをGの極小三角形分割,T = (V,E)をG = (V, E∪F)のクリーク木とする.この とき,三角形分割F のthickness(thickness of triangulationF)をTh(G, F) = max

(Vi,Vj)∈E|φ(V_i, V_j)|と定義し,G のすべての三角形分割において,三角形分割のthicknessの最小値である最小thickness(minimum thickness) をTh(G) = min

F∈ FTh(G, F)と定義する.

Gが弦グラフのとき, Lemma 1を用い,彩色多項式を計算する.

Lemma 1 (本論文補題4) G= (V, E)は弦グラフであり,T = (V,E)はV={V1, V2, . . . , Vk}であるGのクリー

ク木である.このとき,Gの彩色多項式は,P(G, λ) = k i=1λ^(|Vi|)

(Vi,Vj)∈Eλ^(|Vi∩Vj)| と表せる.

Theorem 4を導くことより, (2)式を用いて計算した際,F1, F2, T1, T2を求めることができる.

Theorem 4 (本論文定理4) グラフGにおいて,FをGの三角形分割,TをG+Fのクリーク木とする.また,e∈F とし,G1=G+e, G2= (G+e)/eとする.このとき,F1はG1の三角形分割で,T1はG1+F1のクリーク木であ り,F₂はG₂の三角形分割で,T₂はG₂+F₂のクリーク木である.

2

Thorem 5を用い,グラフを分割することができる.

Theorem 5 (本論文定理5) グラフGにおいて,G₁, G₂はGの部分グラフであり,G=G₁∪G₂, G₁∩G₂K_r とし,FをGの三角形分割,TをG+F のクリーク木とする.このとき,三角形分割F は,F1はG1の,F2はG2

の三角形分割であるような2つの交わらない集合F₁とF₂に分割することができる.さらに,三角形分割された グラフのクリーク木はT から1本の辺を取ることによって得ることができる.

以上より,以下のAlgorithmのように彩色多項式を計算することができる.このAlgorithmの計算量をなるべ く少なくするためには,入力であるaugumented clique treeT をthicknessやfill-inが最小になるようにとること などが考えられる.また, step 9のChoice Functionの選択する順番をうまくとる必要がある.

Algorithm: Chromatic-Polynomial(G,T) (本論文Algorithm 3) T is an augmented clique-tree of the graph G

Returns the Chromatic polynomial of G 1begin

2 if Gis trianglatedthen returnChromatic-Polynomial(G, T) usingLemma 1 (本論文補題4) 3 if ∃ε∈T such thatφ(ε) =∅

4 Decompose GusingTheorem 5 (本論文定理5):

5 LetG1, T1, G2, T2 andKrthe resulting elements 6 P₁←Chromatic -Polynomial(G₁, T₁)

7 P₂←Chromatic -Polynomial(G2, T2) 8 return(P₁×P₂)/P(K_r)

9 Lete= Choice Function(G, T)

10 UsingTheorem 4 (本論文定理4), we compute 11 G1=G+e, and the resultingT1=T

12 G2= (G+e)/e, and the resultingT2

13 returnChromatic-Polynomial(G₁, T₁) + Chromatic-Polynomial(G₂, T₂) 14end

3

2

thickness, fill-in,

前節までは, [3]で論じられていることであり,そこでは, thiknessと他の不変量である木幅との関係性が問題の 1つとして挙げられていた.ここでは,完全2部グラフについて, thicknessとfill-inと木幅との関係について示す.

一般性を失うことなく,m≤nとしてよい.K_m,nについて次を得る.

Theorem 6 (本論文定理7) m ≤nである完全2部グラフKm,nの最小thicknessは¹₂m(m−1)であり,最小 fill-inは¹₂m(m−1)である.

この定理より, 2≤m≤nであるK_m,n= (A∪B, E)において,三角形分割F は,Aが完全グラフK_mになる ように取ればよい.また,Km,nの増加クリーク木Tは,ラベルのない辺はなく,Fのすべてが各辺のラベルである.

これより, Algorithmのstep 9のChoice Functioneはどの辺から選んでも同じである.

3

Definition 4 (本論文定義9) G= (V, E)をグラフとする.T = (I, F)を木とし,X ={Xi : i ∈ I}をV の 部分集合の属とする.このとき,(i)

i∈IX_i = V であり,(ii)すべての辺(v, w) ∈ E に対して,v ∈ X_i, w ∈ X_i を満たすi ∈ Iが少なくとも1つ存在し,(iii)すべてのi, j, k ∈ Iに対して,j がiとkを結ぶ道の上にある のならば,X_i ∩X_k ⊆ X_j が成り立つような(T,X)を Gの木分解(tree decomposition)という.また,木分解 の幅は,max

i∈I |Xi| −1である.グラフGの木幅(treewidth) tw(G)とは,Gのすべての木分割において最小の幅 (minimum width)のことである.

2≤m≤nである完全2部グラフKm,nの木幅は, tw(Km,n) =mであることは知られている[8].また,この木 分解は増加クリーク木のラベルを除いたものと本質的に同じである.

以上より,完全2部グラフにおいて,木幅tw(Km,n) =mに対して,最小thicknessと最小fill-inは ¹₂m(m−1) であることがわかった.

参考文献

[1] B.Aspvall and P.Heggernes.Finding minimum height elimination trees for interval graphs in polynomial time.

BIT, 34(4):484-509, 1994.

[2] C.Berge.Graphs and Hypergraphs.North Holland, Amsterdam, 1973.

[3] P.Berthom´e, S.Lebresne and K.Nguyˆen. Computation of chromatic polynomial using triangulations and clique trees. RR LRI1403, March 2005. (See also Lecture Notes in Computer Science, Volume 3787/2005, Graph-Theoretic Concepts in Computer Science, p362-373, 31st International Workshop, WG 2005, Metz, France, June 2005, Revised Selected papers.)

[4] J.R.S.Blair and B.W.Peyton. On finding minimum-diameter clique trees.Tech Report ORNL/TM-11850, Oak Bridge National Laboratory, Tennessess, 1991.

[5] H.L.Bodlaender, T.Kslok, D.Kratch and H.M¨uller.Treewidth and minimum f ill-in on d-trapezoid graphs.

Jurnal of graph algorithms and applications, vol.2, no5, pp.1-23, 1998.

[6] R.Diestel. Graph theory, 2nd Edition.Springer-Verlag, 1997. [訳:根上生也,太田克.グラフ理論.シュプリン ガー・フェラーク東京, 2000.]

[7] F.M.Dong, K.M.Koh and K.L.Teo.Chromatic polynomials and chromaticicity of graphs. Singapore, Decem- ber, 2004.

[8] F.V.Fomin, D.M.Thilikos.Dominating sets and local treewidth. REPORTS IN INFORMATICS, ISSN 0333- 3590, REPORT NO 251, AUGUST 2003

[9] A.M.C.A.Kpster, H.L.Bodlaender and S.P.M.van Hoesel.Treewidth : Computational experiments.Konrad- Zuse-Zentrum f¨ur loformarionstechnik Berlin, Report01-38, December 28, 2001.

[10] R.J.Wilson.Introduction to Graph Theory 4th edition. 1996. [訳:西関隆夫,西関裕子.グラフ理論入門 原書第 4版.近代科学社, 2001.]

4