|
|
| 1行目: |
1行目: |
| − | [[ファイル:Petersen graph 3-coloring.svg|thumb|right|3色に頂点彩色（最適彩色）されたグラフ。[[ピーターセングラフ]]の彩色数は3である。]]
| + | {{テンプレート:20180815sk}} |
| − | '''グラフ彩色'''（[[英語|英]]: '''Graph coloring'''）とは、[[グラフ理論|グラフ]]の何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを'''頂点彩色'''という。同様に'''辺彩色'''は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、'''面彩色'''は、[[平面グラフ]]の辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。
| |
| − | | |
| − | == 概要 ==
| |
| − | 頂点彩色が出発点であり、他の彩色問題は頂点彩色に変換可能である。例えば、辺彩色問題は、そのグラフを[[ライングラフ]]に変換したときの頂点彩色と同じであり、面彩色は[[平面グラフ]]の双対グラフの頂点彩色と同じである。しかし、頂点彩色以外の問題もそのままの形で研究されている。これは、見通しの良さのためでもあり、頂点彩色以外の形式で研究が進んでいるためでもある。
| |
| − | | |
| − | 彩色という表現を使うようになったのは、地図を国ごとに彩色する問題が起源である。地図の彩色問題は、平面グラフの面彩色問題に他ならない。また平面グラフの双対性により、頂点彩色問題とも等価であり、あらゆるグラフの問題として一般化できる。数学やコンピュータでは、非負または正の小さい整数を「色」を表現する値として使うことが多い。一般に、任意の有限集合を「色集合」として使うことができる。彩色問題の性質は色数には依存するが、個々の色をどう表すかは関係しない。
| |
| − | | |
| − | グラフ彩色はグラフのラベル付けとは異なる。ラベル付けは数で表される「ラベル」を頂点や辺に割り当てるものである。グラフ彩色問題では、色（を表す数）は任意のマーカーであり、隣接性や結合性に関わる状態を表す。グラフのラベル付け問題では、ラベル（を表す数）は計算可能な値であり、ラベル付けの際の定義で示される何らかの数値的条件を満たす必要がある。
| |
| − | | |
| − | グラフ彩色問題は理論的にも意味があるが、実用的な応用も多い。古典的問題以外にも、色の割り当て方や色自体に異なる制約を加えた問題もある。広く知られているパズルである[[数独]]もグラフ彩色問題の変形である。グラフ彩色は研究が盛んな分野のひとつである。
| |
| − | | |
| − | == 歴史 ==
| |
| − | {{See also |四色定理#歴史}}
| |
| − | グラフ彩色は、地図の色分けの形で始まったものであり、当初はほとんど[[平面グラフ]]だけを対象としていた。イングランドの地図を[[カウンティ]]ごとに色分けしようとした[[フランシス・ガスリー]]は、4色あればどの境界線も両側が同じ色になることがないよう色分けできることに気づき、[[四色定理]]を主張した。ガスリーの兄弟がこの問題を数学の先生だった[[ユニヴァーシティ・カレッジ・ロンドン]]の[[オーガスタス・ド・モルガン]]に提示してみたところ、彼は1852年に[[ウィリアム・ローワン・ハミルトン]]への手紙でこの問題に言及した。1879年、[[ロンドン数学会]]の会合で[[アーサー・ケイリー]]がこの問題を提示した。同年、[[アルフレッド・ケンプ]]がその証明をしたとする論文を発表し、その後10年ほどはこの問題は証明済みとみなされていた。この業績によってケンプは[[王立協会]]フェローに選ばれ、後にロンドン数学会の会長に就任している<ref>M. Kubale, ''History of graph coloring'', in {{harvtxt|Kubale|2004}}</ref>。
| |
| − | | |
| − | 1890年、[[パーシー・ヘイウッド]]はケンプの証明が間違っていることを指摘した。ケンプの証明は地図の塗りわけに「五色」あれば十分であることを示したに過ぎなかった。その後約1世紀に渡って四色定理を証明すべく様々な努力がなされ、とうとう1976年に[[ケネス・アッペル]]と[[ヴォルフガング・ハーケン]]が証明した。驚くべきことに、その証明の考え方はヘイウッドやケンプの考え方に沿ったもので、途中の数十年間の様々な努力は無視されている<ref>{{harvtxt|van Lint|Wilson|2001|loc=Chap. 33}}</ref>。四色定理の証明では初めて大規模にコンピュータを利用したことも注目に値する。
| |
| − | | |
| − | 1912年、彩色問題を研究する過程で[[ジョージ・デビット・バーコフ]]が[[彩色多項式]]を導入。これを[[W・T・タット]]が[[タット多項式]]として一般化し、[[代数的グラフ理論]]の重要な構成要素となっている。ケンプは1879年の時点で既に平面グラフ以外のグラフ一般にも言及しており<ref>{{harvtxt|Jensen|Toft|1995|p=2}}</ref>、グラフ彩色のより高次のグラフへの一般化は20世紀初頭から続々となされていった。
| |
| − | | |
| − | 1960年、[[クロード・ベルジュ]]はグラフ彩色についての新たな予想である「強パーフェクトグラフ予想」を定式化した。これは、[[クロード・シャノン]]の[[情報理論]]の概念であるグラフのゼロエラー容量が発想の元になっている。この予想は40年間証明されなかったが、2002年に[[:en:Maria Chudnovsky|Chudnovsky]]、[[:en:Neil Robertson (mathematician)|Robertson]]、[[:en:Paul Seymour (mathematician)|Seymour]]、[[:en:Robin Thomas (mathematician)|Thomas]]が証明し、「強[[パーフェクトグラフ]]定理」となった。
| |
| − | | |
| − | 1970年ごろから、グラフ彩色についてのアルゴリズムの研究が盛んになってきた。彩色数問題は1972年に[[リチャード・カープ]]が提案した[[カープの21のNP完全問題|21のNP完全問題]]の1つになっており、ほぼ同じころに[[バックトラッキング]]や {{harvtxt|Zykov|1949}} の削除・縮約の繰り返し (deletion-contraction recurrence) などに基づいた[[指数関数時間]]の様々なアルゴリズムが開発された。グラフ彩色の応用の1つとして[[コンパイラ]]における[[レジスタ割り付け]]があり、1981年に登場した。
| |
| − | | |
| − | == 定義と用語 ==
| |
| − | === 頂点彩色 ===
| |
| − | 単に[[グラフ理論|グラフ]]の'''彩色'''(coloring)と言った場合、「頂点彩色」を意味することが多い。また、隣接する頂点が同じ色にならないよう彩色すること、すなわち'''最適彩色'''を意味する。隣接する頂点とは、同じ辺と接している頂点である。ある頂点から同じ頂点へ戻る辺（ループ）が存在する場合、頂点彩色問題は決して最適解を持たないので、以下ではループがないグラフのみを扱う。
| |
| − | | |
| − | 頂点のラベルを「色」で表すのは地図の塗りわけに起源がある。「赤」や「青」といったラベルは色数が小さい場合のみ使われ、一般にはラベルとして整数 {1,2,3,...} を使う。
| |
| − | | |
| − | 最大 ''k'' 色を使った彩色を '''''k''-彩色'''と言う。グラフ ''G'' の彩色に必要な最小の色数を'''彩色数'''(chromatic number)と呼び χ(''G'') で表す。例えば、''n'' 個の頂点からなる[[完全グラフ]]（あらゆる頂点間に辺があるグラフ）<math>K_n</math> の彩色数は、<math>\chi(K_n)=n</math> である。''k''-彩色できるグラフを'''''k''-彩色可能'''(''k''-colorable)といい、その''k''がそのグラフの彩色数であるとき、'''''k''-彩色的'''(''k''-chromatic)という。同じ色が割り当てられた頂点の部分集合を「色クラス」と呼び、色クラス同士は[[独立集合]]となっている。したがって、''k''-彩色することは、頂点集合を ''k'' 個の独立部分集合に分割するのと等価であり、''k''-部 (''k''-partite) グラフや ''k''-彩色可能といった用語も同じ意味を持つ。
| |
| − | | |
| − | === 彩色多項式 ===
| |
| − | [[ファイル:Graph with all three-colourings.png|thumb|right|このグラフは3色で12通りの彩色が可能]]
| |
| − | '''彩色多項式'''(chromatic polynomial)とは、与えられたグラフを与えられた色数内で彩色したときの彩色の組合せ数を求める式である。例えば、右図のグラフは3色で彩色すると12通りの彩色が可能である。2色では彩色できない。4色では 24 + 4×12 = 72 通りである。4色を使った彩色は24通りで、4色のうちの3色を使った彩色はそれぞれ12通りなので、このような計算になる（4色を4つの頂点に割り当てる場合は、任意の組み合わせが可能である）。従って、このグラフの彩色数を表にすると次のようになる。
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | |色数 || 1 || 2 || 3 || 4 || …
| |
| − | |-
| |
| − | |彩色の組み合わせ数 || 0 || 0 || 12 || 72 || …
| |
| − | |}
| |
| − | | |
| − | 彩色多項式は、<math>P(G,t)</math> で表され、グラフ <math>G</math> を <math>t</math> 色で彩色したときの色の組合せ数である。名前が示すとおり、ある <math>G</math> についての彩色多項式は、<math>t</math> に関する[[多項式]]となる。例に挙げたグラフでは、<math>P(G,t)= t(t-1)^2(t-2)</math> となる。
| |
| − | | |
| − | 彩色多項式は彩色数と共に、<math>G</math> の彩色可能性についての情報をもたらす。実際、彩色数 χ は彩色多項式の根ではない最小の正の整数である。
| |
| − | : <math>\chi (G)=\min\{ k \colon P(G,k) > 0 \}</math>
| |
| − | | |
| − | この概念を最初に使ったのは George David Birkhoff と D. C. Lewis であり、[[四色定理]]の証明を試みる過程で用いた。
| |
| − | | |
| − | {| class="wikitable"
| |
| − | |+特定のグラフに関する彩色多項式
| |
| − | |-
| |
| − | | 三角形 <math>K_3</math> || <math>t(t-1)(t-2)</math>
| |
| − | |-
| |
| − | | 完全グラフ <math>K_n</math> || <math>t(t-1)(t-2)</math>...<math>(t-(n-1))</math>
| |
| − | |-
| |
| − | | <math>n</math> 頂点の[[木 (数学)|木]] || <math>t(t-1)^{n-1}</math>
| |
| − | |-
| |
| − | | [[閉路グラフ]] <math>C_n</math>|| <math>(t-1)^n+(-1)^n(t-1)</math>
| |
| − | |-
| |
| − | | [[ピーターセングラフ]] || <math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math>
| |
| − | |}
| |
| − | | |
| − | 彩色多項式には次のような属性がある。
| |
| − | * <math>P(G,0) = 0</math>
| |
| − | * <math>P(G,1) = 0</math> （<math>G</math> に辺がある場合）
| |
| − | * <math>P(G, t) = 0</math>（<math>t < \chi(G)</math> の場合）
| |
| − | <!-- * <math>(-1)^{|V(G)|} P(G,-1)</math> is the number of acyclic orientations of <math>G</math><ref>Stanley, 1973</ref> -->
| |
| − | * <math>G</math> が <math>n</math> 個の頂点、<math>m</math> 個の辺、<math>k</math> 個の連結成分 <math>G_1, G_2,</math>…,<math>G_k</math> から成るとき、
| |
| − | ** <math>P(G, t)</math> の次数は <math>n</math> である。
| |
| − | ** <math>P(G, t)</math> における <math>t^n</math> の係数は 1 である。
| |
| − | ** <math>P(G, t)</math> における <math>t^{n-1}</math> の係数は <math>-m</math> である。
| |
| − | ** <math>t^0, t^1,</math> … <math>t^{k-1}</math> の係数は全てゼロである。
| |
| − | ** <math>t^k</math> の係数はゼロではない。
| |
| − | ** <math>P(G, t) = P(G_1, t)P(G_2,t)</math>⋯<math>P(G_k,t)</math>
| |
| − | * 全ての彩色多項式の係数は符号が交互に変化する。
| |
| − | * <math>P(G, t) = t(t-1)^{n-1}</math> であるときのみ、<math>n</math> 頂点のグラフ G は木である。
| |
| − | * 単位元で評価された導関数 <math>P'(G,1)</math> は「彩色不変量(chromatic invariant)」<math>\theta(G)</math> である。
| |
| − | | |
| − | === 辺彩色 ===
| |
| − | グラフの'''辺彩色'''とは、グラフの辺を彩色するもので、1つの頂点に接合するそれぞれの辺が常に別々の色になるように最適彩色する。''k''色を使った辺彩色を「''k''-辺彩色」と呼び、辺集合を''k''個の[[マッチング (グラフ理論)|マッチング]]に分割する問題と等価である。グラフ ''G'' の辺彩色に必要な最小の色数を'''彩色指数''' (chromatic index) または'''辺彩色数''' (edge chromatic number) と呼び、''χ′(G)'' で表す。'''テイト彩色''' (Tait coloring) とは、[[立方体グラフ]]（3-[[正則グラフ]]）の3-辺彩色を意味する。四色定理は、3-正則で辺が交差しない平面グラフをテイト彩色できることと等価である。
| |
| − | | |
| − | == 属性 ==
| |
| − | === 彩色数の境界 ===
| |
| − | 個々の頂点にそれぞれ異なる色を割り当てれば、その彩色は正しい。従って次が成り立つ。
| |
| − | | |
| − | : <math>1 \le \chi(G) \le n\,</math>
| |
| − | | |
| − | 1-彩色可能なのは[[空グラフ|辺のないグラフ]]に限られる。''n''個の頂点を持つ[[完全グラフ]] <math>K_n</math> を彩色するには <math>\chi(K_n)=n</math> 色が必要である。最適な彩色では、グラフ内の ''m'' 個以上の辺が色クラス間を結ぶ位置にある。従って、次が成り立つ。
| |
| − | | |
| − | : <math>\chi(G)(\chi(G)-1) \le 2m\,</math>
| |
| − | | |
| − | ''G'' に大きさ ''k'' の[[クリーク (グラフ理論)|クリーク]]が含まれている場合、そのクリークの彩色に少なくとも ''k'' 色を必要とする。言い換えれば、グラフ ''G'' の彩色数について次が成り立つ。
| |
| − | | |
| − | : <math>\chi(G) \ge \omega(G)\,</math>
| |
| − | | |
| − | [[インターバルグラフ]]では、この境界がきつい。
| |
| − | | |
| − | 2-彩色可能なグラフは常に[[2部グラフ]]であり、[[木 (数学)|木]]や森もそれに含まれる。四色定理により、全ての平面グラフは4-彩色可能である。
| |
| − | | |
| − | [[貪欲彩色法]]によれば、あらゆるグラフは頂点の最大[[次数 (グラフ理論)|次数]]より1つ多い色数で彩色可能である。
| |
| − | | |
| − | : <math>\chi(G) \le \Delta(G) + 1 \,</math>
| |
| − | | |
| − | 完全グラフは <math>\chi(G)=n</math> かつ <math>\Delta(G)=n-1</math> であり、[[閉路グラフ|奇閉路]]は <math>\chi(G)=3</math> かつ <math>\Delta(G)=2</math> である。したがってこの境界条件はこれらのグラフでは彩色数をよく限定する。それら以外のグラフでは、境界条件をさらに若干改良する余地がある。[[ブルックスの定理]]<ref>{{harvtxt|Brooks|1941}}</ref>は次の通りである。
| |
| − | : '''ブルックスの定理''': 完全グラフでも奇閉路でもない単純な[[連結グラフ]] ''G'' について <math>\chi (G) \le \Delta (G) </math> が成り立つ。
| |
| − | | |
| − | === 彩色数の大きいグラフ ===
| |
| − | 最大クリークの大きなグラフは彩色数も大きいが、逆は必ずしも真ではない。Grötzschグラフ([[:en:Grötzsch graph|en]])は4-彩色的だが、三角形を含まない（[[クリーク (グラフ理論)|クリーク]]がない）。それを一般化したグラフを[[:en:Mycielskian|Mycielskian]]と呼ぶ。
| |
| − | | |
| − | : '''[[:en:Jan Mycielski|Mycielski]]の定理'''<ref>{{harvtxt|Mycielski|1955}}</ref>: 三角形を含まない、任意の彩色数のグラフが存在する。
| |
| − | | |
| − | ブルックスの定理から、彩色数の大きいグラフは次数が高くなければならない。また、局所的には大きなクリークがあれば彩色数は大きくなる。しかし、彩色可能性はグラフの局所的現象ではない。[[内周 (グラフ理論)|内周]]（最短閉路の長さ）が大きいグラフは、局所的に見れば木のようになっているが、その彩色数は2になるとは限らない。
| |
| − | :'''定理'''（エルデシュ）: 任意の内周が大きくかつ彩色数の大きいグラフが存在する。
| |
| − | | |
| − | === 彩色指数の境界 ===
| |
| − | ''G'' の辺彩色は、その[[ライングラフ]] <math>L(G)</math> の頂点彩色と等価であり、逆も成り立つ。従って、
| |
| − | | |
| − | :<math>\chi'(G)=\chi(L(G)) \, </math>
| |
| − | | |
| − | 辺彩色可能性とそのグラフの最大次数 <math>\Delta(G)</math> には強い関連性がある。同じ頂点に接合する全ての辺は異なる色にしなければならないので、次が成り立つ。
| |
| − | | |
| − | : <math>\chi'(G) \ge \Delta(G)\,</math>
| |
| − | | |
| − | さらに次が成り立つ。
| |
| − | | |
| − | : '''[[ケーニグの定理]]:''' ''G'' が[[2部グラフ]]なら <math>\chi'(G) = \Delta(G)</math>
| |
| − | | |
| − | 一般に、この関係はブルックスの定理が頂点彩色に与える関係よりも強い。
| |
| − | : '''Vizingの定理:''' 最大次数 <math>\Delta</math> のグラフの辺彩色数は <math>\Delta</math> または <math>\Delta+1</math> である。
| |
| − | | |
| − | === その他の属性 ===
| |
| − | 平面グラフでは、頂点彩色は基本的に [[:en:Nowhere-zero flow|nowhere-zero flow]] と双対関係にある。
| |
| − | | |
| − | [[無限グラフ]]については、まだよく判っていない。無限グラフの彩色について判明している数少ない事実として次の事柄がある。
| |
| − | : 無限グラフ ''G'' の全ての有限部分グラフが ''k''-彩色可能であれば、[[選択公理]]を仮定した場合に''G''自体も同様である{{harv|de Bruijn|Erdős|1951}}。
| |
| − | : また、''n'' ≥ ''n''<sub>0</sub> の ''n'' 色全部を使って彩色可能なグラフは、無限完全彩色可能である{{harv|Fawcett|1978}}。
| |
| − | | |
| − | === 未解決の問題 ===
| |
| − | 単位距離だけ離れている任意の2つの点が同じ色にならないように平面を彩色する問題 ([[:en:Hadwiger–Nelson problem|Hadwiger–Nelson problem]]) は未解決だが、その彩色数は4、5、6、7のいずれかだということまでは判明している。その他のグラフの彩色数に関する[[数学上の未解決問題|未解決問題]]としては、Hadwiger予想([[:en:Hadwiger conjecture (graph theory)|en]])がある。これは、彩色数 ''k'' のグラフは[[マイナー (グラフ理論)|マイナー]]として頂点 ''k'' 個の[[完全グラフ]]を含む、という予想である。また、Erdős–Faber–Lovász予想([[:en:Erdős–Faber–Lovász conjecture|en]])は、''k''-クリークが互いに高々1つの頂点を共有する形で''k''個連結されたグラフは''k''-彩色的だ、というものである。Albertson予想([[:en:Albertson conjecture|en]])は、''k''-彩色的グラフの中で完全グラフが最も[[交差数 (グラフ理論)|交差数]]が小さい、というものである。
| |
| − | | |
| − | BirkhoffとLewisは四色問題を攻略する手段として彩色多項式を導入し、平面グラフ ''G'' の彩色多項式 <math>P(G,t)</math> は <math>[4,\infty)</math> の領域でゼロにならないという予想を立てた。そのような彩色多項式が <math>[5,\infty)</math> の領域でゼロにならないことと、<math>P(G,4) \neq 0</math> であることは判明しているが、彼らの予想自体は未解決である。任意の2つのグラフの彩色多項式が同一かどうかの判定や、ある多項式が彩色多項式かどうかの判定も未解決の問題である。
| |
| − | | |
| − | == アルゴリズム ==
| |
| − | <table class="infobox"
| |
| − | cellspacing="5" style="width: 22em; text-align: left; font-size: 88%; line-height: 1.5em; ">
| |
| − | <tr><td colspan="2" style="text-align:center; font-size: 125%; font-weight: bold; background: #DD9">グラフ彩色</td></tr>
| |
| − | <tr><td colspan="2" style="text-align:center; "> [[ファイル:3-coloringEx.svg]] <br />
| |
| − | <tr><td colspan="2" style="text-align:center; font-size: 125%; background: #DD9">決定問題</td></tr>
| |
| − | <tr><td>名称<td>グラフ彩色、頂点彩色、''k''-彩色</tr>
| |
| − | <tr><td>入力<td>''n'' 個の頂点を持つグラフ ''G''。整数 ''k''</tr>
| |
| − | <tr><td>出力<td>''G'' は ''k'' 個の色で最適彩色可能か?</tr>
| |
| − | <tr><td>時間計算量<td>O(2<sup> ''n''</sup>''n'')<ref name="bhk"/></tr>
| |
| − | <tr><td>複雑性クラス<td>[[NP完全問題|NP完全]]</tr>
| |
| − | <tr><td>還元<td>[[充足可能性問題|3-SAT]]</tr>
| |
| − | <tr><td>Garey–Johnson<td>GT4</tr>
| |
| − | <tr><td colspan="2" style="text-align:center; font-size: 125%; background: #DD9">最適化問題</td></tr>
| |
| − | <tr><td>名称<td>彩色数</tr>
| |
| − | <tr><td>入力<td>''n'' 個の頂点を持つグラフ ''G''</tr>
| |
| − | <tr><td>出力<td>χ(''G'')</tr>
| |
| − | <tr><td>複雑性クラス<td>[[NP困難]]</tr>
| |
| − | <tr><td>近似計算量<td> O(''n'' (log ''n'')<sup>−3</sup>(log log ''n'')<sup>2</sup>)</tr>
| |
| − | <tr><td>非近似計算量<td> O(''n''<sup>1−ε</sup>) - [[P≠NP予想|P=NP]]でない場合</tr>
| |
| − | <tr><td colspan="2" style="text-align:center; font-size: 125%; background: #DD9">数え上げ問題</td></tr>
| |
| − | <tr><td>名称<td>彩色多項式</tr>
| |
| − | <tr><td>入力<td>''n'' 個の頂点を持つグラフ ''G''。整数 ''k''</tr>
| |
| − | <tr><td>出力<td>''G'' を ''k''-彩色する場合の ''P'' (''G'',''k'') の値</tr>
| |
| − | <tr><td>時間計算量<td>O(2<sup> ''n''</sup>''n'')</tr>
| |
| − | <tr><td>複雑性クラス<td>[[Sharp-P|#P完全]]</tr>
| |
| − | <tr><td>近似計算量<td>多項式時間 - 一部のケースのみ</tr>
| |
| − | <tr><td>非近似計算量<td>P=NPでない場合、多項式時間アルゴリズムは存在しない。</tr>
| |
| − | </table>
| |
| − | | |
| − | === 多項式時間 ===
| |
| − | あるグラフが2色で彩色可能かどうかを決定する問題は、そのグラフが[[2部グラフ]]かどうかの決定問題と等価であり、[[幅優先探索]]を使って[[多項式時間]]で解ける。より一般化すれば、[[パーフェクトグラフ]]の彩色数と具体的な彩色は[[半正定値計画法]]を使って[[多項式時間]]で計算できる。森、[[弦グラフ]]、[[閉路グラフ]]、[[車輪グラフ]]、[[梯子グラフ]]といった種類のグラフは彩色多項式がわかっているので、多項式時間での評価が可能である。
| |
| − | | |
| − | === 正確なアルゴリズム ===
| |
| − | ''k''-彩色の判定を[[力まかせ探索]]で行う場合、''n'' 個の頂点に ''k'' 色を割り当てる <math>k^n</math> の組み合わせを全て試し、制約をみたしているか調べる。彩色数や彩色多項式を計算する場合、力まかせ探索では <math>k=1,\ldots,n-1</math> の全ての ''k'' について同じ作業をすることになり、小さいグラフ以外では現実的でない。
| |
| − | | |
| − | [[動的計画法]]と[[最大独立集合問題|最大独立集合]]の数の制約を利用すると''k''-彩色可能性の判定は時間および空間計算量 <math>O(2.445^n)</math> で行える<ref>{{harvtxt|Lawler|1976}}</ref>。[[包除原理]]と高速ゼータ変換のための[[:en:Samuel Yates|Yates]]のアルゴリズムを使えば、''k''-彩色可能性の判定は任意の''k''について <math>O(2^nn)</math> の時間で行える<ref name="bhk">{{harvtxt|Björklund|Husfeldt|Koivisto|2006}}</ref>。3-彩色可能性および4-彩色可能性の判定についてはさらに高速なアルゴリズムが知られており、それぞれ <math>O(1.3289^n)</math><ref>{{harvtxt|Beigel|Eppstein|2005}}</ref> および <math>O(1.7504^n)</math><ref>{{harvtxt|Byskov|2004}}</ref> の時間で判定できる。
| |
| − | | |
| − | === 縮約 ===
| |
| − | グラフ ''G'' の[[縮約 (グラフ理論)|縮約]] <math>G/uv</math> とは、グラフ内の頂点 ''u'' と ''v'' を特定し、それらの間の辺を全て除去し、その2つの頂点を1つの新たな頂点 ''w'' に置き換え、''u'' や ''v'' と接合していた全ての辺を ''w'' に繋ぎかえることでできるグラフである。この操作はグラフ彩色の解析において重要な役割を演じる。
| |
| − | | |
| − | {{harvtxt|Zykov|1949}} によれば、彩色数は次の[[漸化式]]を満たす。
| |
| − | :<math>\chi(G) = \text{min} \{ \chi(G+uv), \chi(G/uv)\}</math>
| |
| − | ''u'' と ''v'' が隣接した頂点でない場合、<math>G+uv</math> は辺 <math>uv</math> を加えたグラフを意味する。この漸化式を評価することに基づくアルゴリズムもいくつかあり、それによって形成される計算木を Zykov 木と呼ぶこともある。実際にかかる時間は頂点 ''u'' と ''v'' の選択のしかた（ヒューリスティック）に依存する。
| |
| − | | |
| − | 彩色多項式は次の漸化式を満たす。
| |
| − | :<math>P(G-uv, k)= P(G/uv, k)+ P(G, k)</math>
| |
| − | ''u'' と ''v'' が隣接した頂点の場合、<math>G-uv</math> は辺 <math>uv</math> を除去したグラフを意味する。<math>P(G - uv, k)</math> はそのグラフの彩色の組み合わせ数を表し、''u'' と ''v'' が同色の場合もそうでない場合も含まれる。上の式から、彩色の組み合わせ数は2つのグラフの彩色組み合わせ数の和で表される。頂点 ''u'' と ''v'' の色が異なる場合、''u'' と ''v'' が1つの辺で結ばれたグラフでも同じ彩色が可能である。''u'' と ''v'' が同色の場合、''u'' と ''v'' を縮約したグラフと同じとみなすことができる。[[W・T・タット]]はこの漸化式を満たすグラフの属性について興味を持ち、彩色多項式を一般化した[[タット多項式]]を発見した。
| |
| − | | |
| − | これらから、再帰的な手続きが考えられ、それを削除・縮約アルゴリズム (deletion–contraction algorithm) と呼び、多くのグラフ彩色アルゴリズムの基盤となっている。すなわち、与えられたグラフを辺が1つ少ない2つのグラフに変換し、それを再帰的に繰り返すのである。これは[[フィボナッチ数]]と同様の再帰属性を持ち、最悪でも <math>((1+\sqrt{5})/2)^{n+m}=O(1.6180^{n+m})</math> の処理時間となる<ref>{{harvtxt|Wilf|1986}}</ref>。さらに入力されたグラフの[[スパニング木]]の数 <math>t(G)</math> の多項式の係数を応用することで解析を改善することができる<ref>{{harvtxt|Sekine|Imai|Tani|1995}}</ref>。実際には、[[分枝限定法]]を使い、[[グラフ同型|同型]]のグラフを排除することで再帰回数を減らすことができ、処理時間は2つの頂点を選ぶ際のヒューリスティックに依存する。
| |
| − | | |
| − | === 貪欲彩色 ===
| |
| − | [[ファイル:Greedy colourings.svg|thumb|right|同じグラフにおいて2種類の頂点の順序付けをしたときの貪欲彩色。うまく順序付けすれば2-彩色可能だが、貪欲彩色では <math>n/2</math> 色まで費やすことがある。]]
| |
| − | [[貪欲法]]では、頂点に所定の順序 <math>v_1</math>,…,<math> v_n</math> を設定し、<math>v_i</math> に対して <math>v_1</math>,…,<math> v_{i-1}</math> までの隣接する頂点で使っていない色を設定し、それまでに使ったどの色の頂点とも隣接している場合は、新たな色を設定する。結果は頂点をどう順序付けするかに依存し、彩色数 <math>\chi(G)</math> による最適彩色を導き出す順序付けも存在することがある。しかし、順序付けによってはもっと悪い結果になる。例えば頂点が ''n'' 個の [[:en:crown graph|crown graph]] は2-彩色的だが、貪欲彩色では <math>n/2</math> 色を必要とすることがある。
| |
| − | | |
| − | 頂点を[[次数 (グラフ理論)|次数]]が小さくなる順序で[[ソート]]すれば、貪欲彩色で使う最大色数は <math>\text{max}_i \text{ min}
| |
| − | \{d(x_i ) + 1, i\}</math> となり、最悪でもそのグラフの最大次数より1つだけ大きい色数になる。このヒューリスティックを Welsh–Powell アルゴリズムとも呼ぶ<ref>{{harvtxt|Welsh|Powell|1967}}</ref>。他にも、アルゴリズム実行中に動的に頂点の順序を決定していくヒューリスティックもあり、最も多くの異なる色と隣接している頂点を次の頂点として選ぶという方法もある<ref>{{harvtxt|Brèlaz|1979}}</ref>。他にも様々なヒューリスティクスを採用したアルゴリズムがあり、これらを総称して逐次彩色 (sequential coloring) アルゴリズムと呼ぶこともある。
| |
| − | | |
| − | === 並列アルゴリズムと分散アルゴリズム ===
| |
| − | グラフ彩色の[[分散アルゴリズム]]は、グラフの「対称性の破れ」の問題と密接に関連する。[[対称グラフ]]では、[[決定的アルゴリズム|決定的]]分散アルゴリズムでは最適彩色を見つけることができない。対称性の破れを見つけるには何らかの予備的情報を必要とする。一般的な前提条件として、''n'' 個の各頂点に {1, 2, ..., ''n''} の一意の識別子を付与した状態、つまりそれぞれが別々の色に彩色された状態を初期状態とする。したがって、なすべきことは ''n'' 色を例えば Δ + 1 色にまで減らしていくことである。
| |
| − | | |
| − | 貪欲法を単純に分散アルゴリズム化して(Δ + 1)-彩色を求めるアルゴリズムは、最悪の場合 Θ(''n'') 回の通信を必要とし、情報をネットワークの一端から全体に伝播させる必要があることもある。ただし、最大次数 Δ が小さければ、もっと高速なアルゴリズムも存在する。
| |
| − | | |
| − | 単純で興味深い例として ''n''-[[閉路グラフ]]がある。Richard Cole と [[:en:Uzi Vishkin|Uzi Vishkin]]<ref>{{harvtxt|Cole|Vishkin|1986}}, see also {{harvtxt|Cormen|Leiserson|Rivest|1990|loc = Section 30.5}}</ref>によれば、1回の同期通信ステップで色数を ''n'' から ''O''(log ''n'') に減らす分散アルゴリズムが存在する。これを繰り返すと''n''-閉路グラフの3-彩色を ''O''(log* ''n'') の通信ステップで得ることができる（各頂点には一意の識別子が付与されていることが前提）。
| |
| − | | |
| − | [[反復対数]]関数 log* は成長が非常にゆっくりとしていて、ほぼ定数とみなせる。そこで Cole と Vishkin の成果から、''n''-閉路の3-彩色を求める定数時間の分散アルゴリズムはあるのかという問題が提起される。{{harvtxt|Linial|1992}} によれば、そのようなアルゴリズムは存在しない。決定的分散アルゴリズムは''n''-閉路を''n''-彩色から3-彩色に減らすのに Ω(log* ''n'')の通信ステップを必要とする。
| |
| − | | |
| − | ColeとVishkinの技法は任意の次数の制限されたグラフに適用可能である。その場合の計算時間は poly(Δ) + ''O''(log* ''n'') となる<ref>{{harvtxt|Goldberg|Plotkin|Shannon|1988}}</ref>。(Δ + 1)-彩色の既知の最高速アルゴリズムとしては、Leonid Barenboim と Michael Elkin のものがある。その計算時間は ''O''(Δ) + log*(''n'')/2 であり<ref>{{harvtxt|Barenboim|Elkin|2009}}; see also {{harvtxt|Kuhn|2009}}</ref>、Linialの下限によれば 1/2 という係数はこれ以上改善できないので ''n'' に対して最適なアルゴリズムということになる。
| |
| − | | |
| − | 辺彩色の分散アルゴリズムも研究されてきた。{{harvtxt|Panconesi|Rizzi|2001}} では、(2Δ − 1)-辺彩色を ''O''(Δ + log* ''n'') の時間で可能なアルゴリズムが示されている。{{harvtxt|Linial|1992}} による分散頂点彩色の下限は、辺彩色問題についても同様に成り立つ。
| |
| − | | |
| − | === メッセージをやり取りしない分散アルゴリズム ===
| |
| − | メッセージのやり取りをしない分散アルゴリズム (decentralized algorithm) もある。最適彩色が存在するグラフについて、効率的にそれを求めるアルゴリズムが存在する。この場合、各頂点は隣接する頂点が自分と同じ色かどうかをメッセージをやり取りせずに確認できることを前提とする。例えば無線のチャンネル割り当てなどでは、他の通信機が同じチャンネルを使っているかどうかは容易に検出可能なので、この前提は穏当である。そのような情報があれば、学習するオートマトンが確実なグラフ彩色を見出すのに十分である<ref>{{harvtxt|Leith|2006}} and {{harvtxt|Duffy|2008}}</ref>。
| |
| − | | |
| − | === 計算量 ===
| |
| − | グラフ彩色は困難である。''k'' = 1 および ''k'' = 2 以外の ''k'' について「与えられたグラフが''k''-彩色可能か」という決定問題は[[NP完全問題|'''NP'''完全問題]]である。彩色数を求める問題は[[NP困難|'''NP'''困難]]である。彩色可能性を問う決定問題は[[次数 (グラフ理論)|次数]]が最大4の[[平面グラフ]]であっても'''NP'''完全である<ref>{{harvtxt|Dailey|1980}}</ref>。
| |
| − | | |
| − | 既知の最良の[[近似アルゴリズム]]はオーダー O(''n''(log n)<sup>−3</sup>(log log ''n'')<sup>2</sup>) の近似精度で彩色数を計算する<ref>{{harvtxt|Halldórsson|1993}}</ref>。あらゆる ''ε'' > 0 について、''n''<sup>1−''ε''</sup> 以内に彩色数を近似することは[[NP困難|'''NP'''困難]]である<ref>{{harvtxt|Zuckerman|2007}}</ref>。
| |
| − | | |
| − | 3-彩色可能なグラフを4色で彩色する問題も'''NP'''困難であり<ref>{{harvtxt|Guruswami|Khanna|2000}}</ref>、''k''-彩色可能なグラフを ''k''<sup>(log ''k'' ) / 25</sup> 色で彩色する問題も ''k'' が十分大きければ'''NP'''困難である<ref>{{harvtxt|Khot|2001}}</ref>。
| |
| − | | |
| − | 彩色多項式の係数を求める問題は[[Sharp-P|'''#P''']]困難である。実際 ''k'' = 1 または ''k'' = 2 以外の任意の有理数 ''k'' について <math>\chi(G,k)</math> を求める計算も'''#P'''困難である<ref>{{harvtxt|Jaeger|Vertigan|Welsh|1990}}</ref>。[[NP]] = [[RP (計算複雑性理論)|RP]] でない限り、''k'' = 2 以外の ''k'' ≥ 1.5 の有理数 ''k'' について彩色多項式を評価する多項式時間の近似アルゴリズムは存在しない<ref>{{harvtxt|Goldberg|Jerrum|2008}}</ref>。
| |
| − | | |
| − | 辺彩色については、Vizingの証明の結果から最大 Δ+1 色で彩色するアルゴリズムが得られている。しかし、2つの候補値から辺彩色数を決定する問題は'''NP'''完全である<ref>{{harvtxt|Holyer|1981}}</ref>。近似アルゴリズムの場合、Vizingの辺彩色数を求めるアルゴリズムの近似度は4/3であり、任意の ''ε > 0'' について(4/3 − ''ε'' )-近似アルゴリズムは存在しない（P=NPでない限り）。これらは近似アルゴリズムについての最も古い論文である（近似度という記法は明確には使っていない）<ref>{{harvtxt|Crescenzi|Kann|1998}}</ref>。
| |
| − | | |
| − | == 応用 ==
| |
| − | === スケジューリング ===
| |
| − | 頂点彩色は各種スケジューリング問題のモデルとなる<ref>{{harvtxt|Marx|2004}}</ref>。最も単純化したスケジューリング問題は、一連の仕事を時間割にひとつずつ（ある時間には1つの仕事だけをするように）あてはめていくものである。個々の仕事にはリソースの競合など同時に実施できない制約条件がある。これをグラフで表すと、個々の仕事が頂点、競合する仕事を結ぶ線が辺となる。このグラフの彩色数を求める問題は、全部の仕事が終わるまでにかかる時間を最小にすることと等価である。
| |
| − | | |
| − | スケジューリング問題の詳細がそのグラフの構造を定義する。例えば航空機の運航スケジューリングの場合、[[インターバルグラフ]]で表せば効率的に彩色問題として解ける。無線局の[[帯域幅]]割り当ての場合、[[単位円グラフ]]で表せばよい。
| |
| − | | |
| − | === レジスタ割り付け ===
| |
| − | {{Main|レジスタ割り付け}}
| |
| − | [[プログラム (コンピュータ)|コンピュータプログラム]]の[[コンパイラ]]は、ある[[プログラミング言語]]から別の言語への翻訳を行う。その結果生成されるコードの実効効率を向上させるため、[[レジスタ割り付け]]という[[コンパイラ最適化]]技法が使われる。これは、プログラムで頻繁に使う値を高速な[[レジスタ (コンピュータ)|レジスタ]]に保持し続けるようにするものである。理想的には演算に使用する値が常にレジスタに存在することが望ましい。
| |
| − | | |
| − | 典型的な技法として、この問題をグラフ彩色問題にモデル化する<ref>{{harvtxt|Chaitin|1982}}</ref>。コンパイラは頂点をレジスタ（変数）とし、辺を同時に必要とされるレジスタ同士を結ぶように配した干渉グラフを構築する。このグラフが''k''色で彩色可能なら、''k''個のレジスタに割り付け可能である。
| |
| − | | |
| − | === その他 ===
| |
| − | グラフ彩色問題は、[[パターンマッチング]]など様々な応用が見つかっている。
| |
| − | | |
| − | [[数独]]というパズルも、81個の頂点を持つグラフの9-彩色問題とみなすことができる。
| |
| − | | |
| − | == 脚注・出典 ==
| |
| − | {{Reflist}}
| |
| − | | |
| − | == 参考文献 ==
| |
| − | * {{Citation | last1=Barenboim | first1=L. | last2=Elkin | first2=M. | contribution=Distributed (Δ + 1)-coloring in linear (in Δ) time | pages=111–120 | title=Proceedings of the 41st Symposium on Theory of Computing | year=2009 | doi=10.1145/1536414.1536432}}
| |
| − | * {{Citation| last1= Beigel | first1= R.| last2= Eppstein | first2= D. | authorlink2= |title= 3-coloring in time O(1.3289<sup>n</sup>)|journal= Journal of Algorithms|volume= 54|pages=168–204|year=2005 | issue= 2)| doi= 10.1016/j.jalgor.2004.06.008}}
| |
| − | * {{Citation | last1=Björklund | first1=A. | last2=Husfeldt | first2=T. | last3=Koivisto | first3=M. | journal=SIAM Journal on Computing | pages=546–563 | title=Set partitioning via inclusion–exclusion | volume= 39 | year=2009 | doi=10.1137/070683933| issue=2}}
| |
| − | * {{Citation | last = Brèlaz | first = D. | title = New methods to color the vertices of a graph | journal = Communications of the ACM | volume = 22 | year = 1979 | pages = 251–256 | doi = 10.1145/359094.359101}}
| |
| − | * {{Citation | last = Brooks | first = R. L. | last2 = Tutte | first2 = W. T. | title = On colouring the nodes of a network | journal = Proceedings of the Cambridge Philosophical Society | volume = 37 | year = 1941 | pages = 194–197 | doi = 10.1017/S030500410002168X}}
| |
| − | * {{Citation | last1 = de Bruijn | first1 = N. G. | authorlink1 = | last2 = Erdős | first2 = P. | authorlink2 = ポール・エルデシュ | title = A colour problem for infinite graphs and a problem in the theory of relations | journal = Nederl. Akad. Wetensch. Proc. Ser. A | volume = 54 | year = 1951 | pages = 371–373 | url = http://www.math-inst.hu/~p_erdos/1951-01.pdf}} (= ''Indag. Math.'' '''13''')
| |
| − | * {{Citation|last=Byskov|first=J.M.|title=Enumerating maximal independent sets with applications to graph colouring|journal=Operations Research Letters|pages=547–556|volume=32|year= 2004|doi=10.1016/j.orl.2004.03.002}}
| |
| − | * {{Citation | last = Chaitin | first = G. J. | contribution = Register allocation & spilling via graph colouring | title = Proc. 1982 SIGPLAN Symposium on Compiler Construction | year = 1982 | pages = 98–105 | doi = 10.1145/800230.806984}}
| |
| − | * {{Citation | last1 = Cole | first1 = R. | last2 = Vishkin | first2 = U. | year = 1986 | title = Deterministic coin tossing with applications to optimal parallel list ranking | journal = Information and Control | volume = 70 | issue = 1 | pages = 32–53 | doi = 10.1016/S0019-9958(86)80023-7}}
| |
| − | * {{Citation | last1 = Cormen | first1 = T. H. | last2 = Leiserson | first2 = C. E. | last3 = Rivest | first3 = R. L. | title = Introduction to Algorithms | publisher = The MIT Press | year = 1990 | edition = 1st}}
| |
| − | * {{Citation | last1 = Dailey | first1 = D. P. | title = Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete | journal = Discrete Mathematics | volume = 30 | pages = 289–293 | year = 1980 | doi = 10.1016/0012-365X(80)90236-8}}
| |
| − | * {{Citation| last1 = Duffy | first1 = K.| last2 = O'Connell | first2 = N.| last3 = Sapozhnikov | first3 = A.| title=Complexity analysis of a decentralised graph colouring algorithm| journal=Information Processing Letters| volume=107| pages=60–63| year=2008| url=| doi=10.1016/j.ipl.2008.01.002}}
| |
| − | * {{Citation | last1 = Fawcett | first1 = B. W. | title = On infinite full colourings of graphs | journal = Canadian Journal of Mathematics|Can. J. Math. | volume = XXX | pages = 455–457 | year = 1978 | doi =}}
| |
| − | * {{Citation | last1 = Garey | first1 = M. R. | authorlink1 = | last2 = Johnson | first2 = D. S. | authorlink2 = | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 0-7167-1045-5}}
| |
| − | * {{Citation | last1 = Garey | first1 = M. R. | authorlink1 = | last2 = Johnson | first2 = D. S. | authorlink2 = | last3 = Stockmeyer | first3 = L. | authorlink3 = | year = 1974 | contribution = Some simplified NP-complete problems | url = http://portal.acm.org/citation.cfm?id=803884 | title = Proceedings of the Sixth Annual ACM Symposium on Theory of Computing | pages = 47–63}}
| |
| − | * {{Citation | last1 = Goldberg | first1 = L. A. | last2 = Jerrum | first2 = M. | authorlink2 = | title = Inapproximability of the Tutte polynomial | journal = Information and Computation | volume = 206 | issue= 7| date= July 2008 | pages = 908–929 | doi = 10.1016/j.ic.2008.04.003}}
| |
| − | * {{Citation | last1 = Goldberg | first1 = A. V. | last2 = Plotkin | first2 = S. A. | last3 = Shannon | first3 = G. E. | year = 1988 | title = Parallel symmetry-breaking in sparse graphs | journal = SIAM Journal on Discrete Mathematics | volume = 1 | issue = 4 | pages = 434–446 | doi = 10.1137/0401044}}
| |
| − | * {{Citation | last1 = Guruswami | first1 = V. | last2 = Khanna | first2 = S. | contribution = On the hardness of 4-coloring a 3-colorable graph | title = Proceedings of the 15th Annual IEEE Conference on Computational Complexity | pages = 188–197 | year = 2000 | doi = 10.1109/CCC.2000.856749}}
| |
| − | * {{Citation | last = Halldórsson | first = M. M. | year = 1993 | title = A still better performance guarantee for approximate graph coloring | journal = Information Processing Letters | volume = 45 | pages = 19–23 | doi = 10.1016/0020-0190(93)90246-6}}
| |
| − | * {{Citation | last = Holyer | first = I. | year = 1981 | title = The NP-completeness of edge-coloring | journal = SIAM Journal on Computing | volume = 10 | pages = 718–720 | doi = 10.1137/0210055}}
| |
| − | * {{Citation | last1 = Crescenzi | first1 = P. | last2 = Kann | first2 = V. | title = How to find the best approximation results — a follow-up to Garey and Johnson | journal = ACM SIGACT News | date = December 1998 | doi = 10.1145/306198.306210 | volume = 29 | page = 90}}
| |
| − | * {{Citation | last1 = Jaeger | first1 = F. | last2 = Vertigan | first2 = D. L. | last3 = Welsh | first3 = D. J. A. | year = 1990 | title = On the computational complexity of the Jones and Tutte polynomials | journal = Mathematical Proceedings of the Cambridge Philosophical Society | volume = 108 | pages = 35–53 | doi = 10.1017/S0305004100068936}}
| |
| − | * {{Citation | last1 = Jensen | first1 = T. R. | last2 = Toft | first2 = B. | title = Graph Coloring Problems | publisher = Wiley-Interscience, New York | year = 1995 | isbn = 0-471-02865-7}}
| |
| − | * {{Citation | last = Khot | first = S. |authorlink = | year = 2001 | contribution = Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring | title = Proc. 42nd Annual Symposium on Foundations of Computer Science | pages = 600–609 | doi = 10.1109/SFCS.2001.959936}}
| |
| − | * {{Citation | last1 = Kubale | first1 = M. | title = Graph Colorings | publisher = American Mathematical Society | year = 2004 | isbn = 0-8218-3458-4}}
| |
| − | * {{Citation | last1=Kuhn | first1=F. | contribution=Weak graph colorings: distributed algorithms and applications | pages=138–144 | title=Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures | year=2009 | doi=10.1145/1583991.1584032}}
| |
| − | * {{Citation | last1=Lawler | first1=E.L. | authorlink = | title=A note on the complexity of the chromatic number problem | pages=66–67 | journal=Information Processing Letters | year=1976|volume= 5 | doi=10.1016/0020-0190(76)90065-X| issue=3}}
| |
| − | * {{Citation | last1 = Leith | first1 = D.J. | last2 = Clifford | first2 = P. | year = 2006 | contribution = A Self-Managed Distributed Channel Selection Algorithm for WLAN | title = Proc. RAWNET 2006, Boston, MA | url =}}
| |
| − | * {{Citation | last1 = Linial | first1 = N. | authorlink = | year = 1992 | title = Locality in distributed graph algorithms | journal = SIAM Journal on Computing | volume = 21 | issue = 1 | pages = 193–201 | doi = 10.1137/0221015}}
| |
| − | * {{Citation | last1 = van Lint| first1 = J. H. | last2 = Wilson | first2 = R. M. | title = A Course in Combinatorics | year = 2001 | edition = 2nd | publisher = Cambridge University Press | isbn = 0-521-80340-3.}}
| |
| − | * {{Citation | last = Marx | first = Dániel | contribution = Graph colouring problems and their applications in scheduling | title = Periodica Polytechnica, Electrical Engineering | year = 2004 | pages = 11–16 | volume = 48 |issue=1-2 | url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.4268&rep=rep1&type=pdf}}
| |
| − | * {{citation | last = Mycielski | first = J. | journal = Colloq. Math. | pages = 161–162 | title = Sur le coloriage des graphes | volume = 3 | year = 1955 |url= http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf}}
| |
| − | * {{Citation | last1=Panconesi | first1=Alessandro | last2=Rizzi | first2=Romeo | title=Some simple distributed algorithms for sparse networks | publisher=Springer-Verlag | location=Berlin, New York | year=2001 | journal=Distributed Computing | issn=0178-2770 | volume=14 | issue=2 | pages=97–100 | doi=10.1007/PL00008932}}
| |
| − | * {{Citation | last1 = Sekine | first1 = K. | last2 = Imai | first2 = H. | last3 = Tani | first3 = S. | contribution = Computing the Tutte polynomial of a graph of moderate size | title = Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995) | series = Lecture Notes in Computer Science | volume = 1004 | publisher = Springer | year = 1995 | pages = 224–233 | doi = 10.1007/BFb0015427}}
| |
| − | * {{Citation | last1 = Welsh | first1 = D. J. A. | last2 = Powell | first2 = M. B. | year = 1967 | title = An upper bound for the chromatic number of a graph and its application to timetabling problems | journal = The Computer Journal | volume = 10 | doi = 10.1093/comjnl/10.1.85 | pages = 85–86 | issue= 1}}
| |
| − | * {{Citation | last = West | first = D. B. | title = Introduction to Graph Theory | year = 1996 | publisher = Prentice-Hall | isbn = 0-13-227828-6}}
| |
| − | * {{Citation | last = Wilf | first = H. S. | title = Algorithms and Complexity | publisher = Prentice–Hall | year = 1986}}
| |
| − | * {{Citation | last = Zuckerman | first = D. | title = Linear degree extractors and the inapproximability of Max Clique and Chromatic Number | journal = Theory of Computing | volume = 3 | pages = 103–128 | year = 2007 | doi = 10.4086/toc.2007.v003a006}}
| |
| − | * {{Citation | last = Zykov | first= A. A. | title = О некоторых свойствах линейных комплексов (On some properties of linear complexes) | language = Russian | journal = Math. Sbornik. | volume = 24(66) |issue=2 | year = 1949 | pages = 163–188 | url = http://mi.mathnet.ru/eng/msb5974}}
| |
| − | | |
| − | == 関連項目 ==
| |
| − | {{Commonscat|Graph coloring}}
| |
| − | * [[四色定理]]
| |
| − | * [[数独]]
| |
| − | | |
| − | == 外部リンク ==
| |
| − | * [http://planetmath.org/?op=getobj&from=objects&name=ChromaticNumber Chromatic number of a space] at PlanetMath.org
| |
| − | * [http://www.cs.ualberta.ca/~joe/Coloring/index.html ''Graph Coloring Page''] by Joseph Culberson （グラフ彩色プログラム）
| |
| − | * [http://vispo.com/software ''CoLoRaTiOn''] by Jim Andrews and Mike Fellows （グラフ彩色パズルゲーム）
| |
| − | * [http://www.adaptivebox.net/research/bookmark/gcpcodes_link.html 各種グラフ彩色プログラムのソースへのリンク集]
| |
| − | * [http://www.mcs.vuw.ac.nz/~djp/tutte/ Code for efficiently computing Tutte, Chromatic and Flow Polynomials] by Gary Haggard, David J. Pearce and Gordon Royle
| |
| − | | |
| − | {{DEFAULTSORT:くらふさいしよく}}
| |
| − | [[Category:グラフ理論]]
| |
| − | [[Category:数学に関する記事]]
| |