グラフの色付け
ピーターセン グラフの頂点を、可能な限り最小の 3 色で適切に彩色します。

グラフ理論において、グラフ彩色とは、グラフの要素に伝統的に「色」と呼ばれるラベルを系統的に割り当てることである。この割り当ては、2 つの隣接する要素が同じ色にならないなど、特定の制約を受ける。グラフ彩色は、グラフラベリングの特殊なケースである。最も単純な形式では、 2 つの隣接する頂点が同じ色にならないようにグラフの頂点を彩色する方法であり、これは頂点彩色と呼ばれる。同様に、辺彩色では、2 つの隣接する辺が同じ色にならないように各辺に色を割り当て、平面グラフの面彩色では、境界を共有する 2 つの面が同じ色にならないように各面 (または領域) に色を割り当てる。

頂点彩色は、グラフ彩色問題の導入によく用いられます。これは、他の彩色問題が頂点彩色のインスタンスに変換できるためです。例えば、グラフの辺彩色はその線グラフの頂点彩色に過ぎず、平面グラフの面彩色はその双対グラフの頂点彩色に過ぎません。しかし、非頂点彩色問題は、しばしばそのまま述べられ、研究されます。これは、教育的な理由と、辺彩色のように、一部の問題は非頂点形式で研究するのが最適であることによる理由があります。

色を使う慣習は、政治地図上の国を色分けすることに由来します。政治地図では、それぞれの面が文字通り色分けされています。これは、平面に埋め込まれたグラフの面を色分けすることに一般化されました。平面双対性により、頂点を色分けするようになり、この形ですべてのグラフに一般化されます。数学的表現やコンピュータ表現では、最初のいくつかの正または非負の整数を「色」として使用するのが一般的です。一般に、任意の有限集合を「色集合」として使用できます。色分け問題の性質は、色の数によって決まりますが、色の本質には依存しません。

グラフ彩色は、理論的な課題だけでなく、多くの実用的な応用も享受しています。古典的な問題に加え、グラフ自体、色の割り当て方法、さらには色そのものに様々な制限を課すことも可能です。人気の数字パズル「数独」の形で、一般の人々にも広く知られるようになりました。グラフ彩色は、現在も非常に活発な研究分野です。

歴史

四色定理に従って色分けしたアメリカ合衆国の地図。

グラフ彩色に関する最初の成果は、地図彩色の形でほぼ平面グラフのみを扱ったものである。1852年、イングランドの地図を彩色しようとしていたフランシス・ガスリーは、四色予想を提唱し、共通の境界線を共有する地域が同じ色にならないように地図を彩色するには4色で十分であると指摘した。[ 1 ]ガスリーの弟フレデリックは、ユニバーシティ・カレッジの数学教師オーガスタス・ド・モーガンにこの問題を伝え、ド・モーガンは1852年にウィリアム・ハミルトンに宛てた手紙の中でこの問題について言及した。アーサー・ケイリーは、1879年のロンドン数学会でこの問題を提起した。同年、アルフレッド・ケンプがその結果を証明したとする論文を発表し、その後10年間、四色問題は解決済みとみなされた。この功績により、ケンプは王立協会の会員に選出され、後にロンドン数学会の会長となった。[ 2 ]

1890年、パーシー・ジョン・ヒーウッドはケンプの議論が間違っていると指摘した。しかし、その論文でヒーウッドは五色定理を証明し、ケンプのアイデアを用いて、あらゆる平面地図は5色以下で塗り分けられると述べた。次の世紀には、膨大な研究が行われ、色の数を4色に減らす理論が展開され、最終的に1976年にケネス・アペルとヴォルフガング・ハーケンによって四色定理が証明された。この証明はヒーウッドとケンプのアイデアまで遡り、その間の発展はほとんど無視された。[ 3 ]四色定理の証明は、1世紀も前の問題を解決したという点だけでなく、コンピュータを利用した最初の主要な証明であるという点でも注目に値する。

1912年、ジョージ・デイヴィッド・バーコフは彩色問題を研究するために彩色多項式を導入しました。これはWTタットによってタット多項式へと一般化されました。これらはいずれも代数グラフ理論における重要な不変量です。ケンペは既に1879年に一般の非平面グラフの場合に注目しており[ 4 ]、20世紀初頭には平面グラフ彩色の高次曲面への一般化に関する多くの結果が続きました。

1960年、クロード・ベルジュはグラフ彩色に関する新たな予想、強パーフェクトグラフ予想を提唱した。これはもともと、シャノンによって導入されたグラフのゼロエラー容量と呼ばれる情報理論の概念に着想を得たものである。この予想は40年間未解決のままであったが、2002年にチュドノフスキー、ロバートソン、シーモア、トーマスによって、著名な強パーフェクトグラフ定理として確立された。

グラフ彩色は1970年代初頭からアルゴリズムの問​​題として研究されてきました。彩色数問題（後述の「頂点彩色」セクションを参照）は、1972年にKarpが提示した21個のNP完全問題の1つであり、ほぼ同時期には、バックトラッキングとZykov (1949)の削除縮約回帰に基づく様々な指数時間アルゴリズムが開発されました。グラフ彩色の主要な応用例の1つであるコンパイラにおけるレジスタ割り当ては、1981年に導入されました。

定義と用語

このグラフは 12 通りの方法で 3 色にすることができます。

頂点カラーリング

グラフの色付けは、特に限定されずに使用される場合、ほとんどの場合、適切な頂点色付け、すなわち、同じ辺を共有する2つの頂点が同じ色にならないようにグラフの頂点を色でラベル付けすることを指します。ループ（つまり、自身に直接接続された頂点）を持つ頂点は適切に色付けできない ため、この文脈におけるグラフはループがないと理解されます。

頂点ラベルに色を使用するという用語の起源は、地図の色分けに遡ります。赤や青といったラベルは、色の数が少ない場合にのみ使用され、通常はラベルは整数{ 1, 2, 3, ...}で表されます。

最大k色 を使用した彩色は、（適切な） k彩色と呼ばれる。グラフGを彩色するために必要な最小の色数は、その彩色数と呼ばれ、しばしば χ( G ) と表記される。[ 5 ] χ ( G )はグラフのオイラー特性を示すためにも使用されるため、γ( G )が使用されることもある。 [ 6 ] （適切な） k彩色を割り当てることができるグラフはk彩色可能であり、その彩色数がちょうどkである場合にk彩色である。同じ色が割り当てられた頂点のサブセットは色クラスと呼ばれ、そのようなクラスはすべて独立集合を形成する。したがって、k彩色は頂点セットをk 個の独立集合に分割することと同じであり、 k部とk彩色可能という用語は同じ意味を持つ。

彩色多項式

3頂点の非同型グラフとその彩色多項式。空グラフE 3 (赤) は1色彩色が可能。完全グラフK 3 (青) は3色彩色が可能。その他のグラフは2色彩色が可能。

彩色多項式は、与えられた数の色のうちいくつかを使ってグラフを彩色する方法の数を数えます。例えば、3色を使うと、隣の画像のグラフは12通りの彩色が可能です。2色だけだと、全く彩色できません。4色を使うと、24 + 4 × 12 = 72通りの彩色が可能です。つまり、4色すべてを使うと、4! = 24通りの有効な彩色が可能です（ 4頂点グラフに4色を割り当てると、すべて適切な彩色になります）。また、4色のうち3色を選ぶと、12通りの有効な3色彩色が可能です。したがって、例のグラフの場合、有効な彩色方法の数を示す表は次のようになります。

利用可能な色 1234...
着色数 001272...

彩色多項式は、Gのt 回の彩色の回数を数える関数P ( G , t )です。名前が示すように、与えられたGに対して、この関数はtに関する多項式です。例のグラフでは、P ( G , t ) = t ( t − 1) 2 ( t − 2)となり、実際にはP ( G , 4) = 72 となります。

彩色多項式は、彩色数よりもGの彩色可能性について多くの情報を含んでいます。実際、 χは彩色多項式χ( G ) = min{ k  : P ( G , k ) > 0}の零点ではない最小の正の整数です。

特定のグラフの彩色多項式
三角形K 3t ( t − 1)( t − 2)
完全グラフK nt ( t − 1)( t − 2) ... ( t − ( n − 1))
n頂点 を持つ木t ( t − 1 ) n −1
サイクルC n( t − 1) n + (−1) n ( t − 1)
ピーターセングラフt ( t − 1)( t − 2)( t 7 − 12 t 6 + 67 t 5 − 230 t 4 + 529 t 3 − 814 t 2 + 775 t − 352)

エッジカラーリング

グラフの辺彩色は辺の適切な彩色であり、同じ色の2つの辺に頂点が接続されないように辺に色を割り当てることを意味します。k色による辺彩色はk辺彩色と呼ばれ、辺集合をk 個のマッチングに分割する問題と同等です。グラフGの辺彩色に必要な最小色の数は彩色指数、または辺彩色数χ ′ ( G )です。テイト彩色は、立方体グラフの3辺彩色です。4色定理は、すべての平面立方体の橋なしグラフがテイト彩色を許容する という主張と同等です。

トータルカラーリング

全彩色は、グラフの頂点と辺の彩色の一種です。何の修飾もなしに用いられる場合、全彩色は常に、隣接する頂点、隣接する辺、そして辺とその端点に同じ色が割り当てられないという意味で、適切であるとみなされます。グラフGの全彩色数χ ″( G )は、 Gのあらゆる全彩色に必要な色数の最小値です。

顔の色付け

表面上に強く埋め込まれたグラフの場合、面彩色は頂点彩色問題の双対になります。

トゥッテのフロー理論

ウィリアム・T・タット[ 7 ] [ 8 ] [ 9 ]は、有向曲面上に強い埋め込みを持つグラフGについて、グラフがk面彩色可能であるならば、 Gはどこでも零でないkフローを許容することを発見した。この同値性は、曲面が球面の場合にも成り立つ。

ラベルなしの色付け

グラフのラベルなし彩色とは、グラフの自己同型群の作用による彩色の軌道である。色はラベル付きのままであり、ラベルが付いていないのはグラフである。彩色多項式に相当するものがあり、与えられた有限色の集合からグラフのラベルなし彩色の数を数える。

d頂点のグラフの色付けを⁠ ⁠Zd{\displaystyle \mathbb {Z} ^{d}}内のベクトルとして解釈すると、自己同型の作用は色付けベクトル内の係数の 順列になります。

プロパティ

彩色数の上限

異なる頂点に異なる色を割り当てると、常に適切な色付けが得られるので、

1≤χ（G）≤n。{\displaystyle 1\leq \chi (G)\leq n.}

1色にできるグラフは辺のないグラフのみです。n頂点の完全グラフには色が必要です。最適な色分けでは、グラフのm本の辺のうち少なくとも1つは、色クラスの各ペアの間に存在する必要があります。つまり、 Kn{\displaystyle K_{n}}χ（Kn）＝n{\displaystyle \chi (K_{n})=n}

χ（G）（χ（G）−1）≤2メートル。{\displaystyle \chi (G)(\chi (G)-1)\leq 2m.}

より一般的には、グラフ族がχ有界であるとは、グラフを最大で色で彩色できるような関数が存在する場合である。ここで はのクリーク数である。パーフェクトグラフ族の場合、この関数は である。 F{\displaystyle {\mathcal {F}}}c{\displaystyle c}G{\displaystyle G}F{\displaystyle {\mathcal {F}}}c（ω（G））{\displaystyle c(\omega (G))}ω（G）{\displaystyle \omega (G)}G{\displaystyle G}c（ω（G））＝ω（G）{\displaystyle c(\omega (G))=\omega (G)}

2色に色付け可能なグラフは、木や森を含む二部グラフそのものです。四色定理により、あらゆる平面グラフは4色に色付けできます。

貪欲彩色法では、すべてのグラフは最大頂点次数より1色多く彩色できることが示される。

χ（G）≤Δ（G）+1.{\displaystyle \chi (G)\leq \Delta (G)+1.}

完全グラフはと を持ち、奇数閉路はとを持つので、これらのグラフに対してはこの境界が最良である。他のすべての場合では、この境界はわずかに改善される。ブルックスの定理[ 10 ]によれば、 χ（G）＝n{\displaystyle \chi (G)=n}Δ（G）＝n−1{\displaystyle \Delta (G)=n-1}χ（G）＝3{\displaystyle \chi (G)=3}Δ（G）＝2{\displaystyle \Delta (G)=2}

ブルックスの定理: 連結された単純グラフGの場合、ただしGが完全グラフまたは奇数サイクルでない場合。χ（G）≤Δ（G）{\displaystyle \chi (G)\leq \Delta (G)}

彩色数の下限

色彩の境界の下限値は長年にわたっていくつか発見されてきました。

Gにサイズkのクリークが含まれている場合、そのクリークを色付けするには少なくともk色が必要です。言い換えると、彩色数は少なくともクリーク数になります。

χ（G）≥ω（G）。{\displaystyle \chi (G)\geq \omega (G).}

完全グラフの場合、この境界は厳密です。クリークを見つけることはクリーク問題として知られています。

ホフマンの境界：が の辺でない場合は常にとなるような実対称行列とします。を定義します。ここで はの最大固有値と最小固有値です。 を定義します。ここで は上記と同じです。次に： W{\displaystyle W}W私、j＝0{\displaystyle W_{i,j}=0}（私、j）{\displaystyle (i,j)}G{\displaystyle G}χW（G）＝1−λ最大（W）λ分（W）{\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}λ最大（W）、λ分（W）{\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)}W{\displaystyle W}χH（G）＝最大WχW（G）{\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}W{\displaystyle W}

χH（G）≤χ（G）。{\displaystyle \chi _{H}(G)\leq \chi (G).}

ベクトル彩色数：が の辺であるとき、 となるような半正定値行列とする。をそのような行列が存在する最小の k と。すると、 W{\displaystyle W}W私、j≤−1け−1{\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}}（私、j）{\displaystyle (i,j)}G{\displaystyle G}χV（G）{\displaystyle \chi _{V}(G)}W{\displaystyle W}

χV（G）≤χ（G）。{\displaystyle \chi _{V}(G)\leq \chi (G).}

ロヴァース数:補グラフのロヴァース数は彩色数の下限でもある:

ϑ（G¯）≤χ（G）。{\displaystyle \vartheta ({\bar {G}})\leq \chi (G).}

分数彩色数:グラフの分数彩色数は彩色数の下限でもあります。

χf（G）≤χ（G）。{\displaystyle \chi _{f}(G)\leq \chi (G).}

これらの境界は次のように順序付けられます。

χH（G）≤χV（G）≤ϑ（G¯）≤χf（G）≤χ（G）。{\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).}

彩度の高いグラフ

大きなクリークを持つグラフは彩色数が大きいが、その逆は真ではない。グロッチュグラフは三角形を持たない4彩色グラフの例であり、この例はミシェルスキアングラフに一般化できる。

定理（WT Tutte、1947、[ 11 ] Alexander Zykov  1949、Jan Mycielski  1955）：任意の高い彩色数を持つ三角形のないグラフが存在する。

これを証明するために、ミシェルスキとジコフの両者は、それぞれ、三角形のないグラフの帰納的に定義された族だが、彩色数は任意に大きなグラフの構成を示した。 [ 12 ]バーリング（1965）は、交差グラフが三角形がなく、適切に彩色するには任意の数の色を必要とする軸平行ボックスを構築した。このグラフ族はバーリンググラフと呼ばれる。同じグラフのクラスは、平面上の三角形のない線分の族の構築にも使用され、これはパウリクら（2014）によって示されている。[ 13 ]これは、交差グラフの彩色数も任意に大きいことを示している。したがって、軸平行ボックスと線分はχ-有界ではないことを意味する。[ 13 ]R3{\displaystyle \mathbb {R} ^{3}}R3{\displaystyle \mathbb {R} ^{3}}R2{\displaystyle \mathbb {R} ^{2}}

ブルックスの定理によれば、彩色数の高いグラフは最大次数も高くなる。しかし、彩色可能性は完全に局所的な現象ではない。内周の高いグラフは、すべての閉路が長いため局所的には木のように見えるが、彩色数は必ずしも2である必要はない。

定理（エルデシュ）：任意の大きさの内周と彩色数を持つグラフが存在する。[ 14 ]

彩色指数の境界

Gの辺彩色はその線グラフ の頂点彩色であり、その逆もまた同様である。したがって、 L（G）{\displaystyle L(G)}

χ′（G）＝χ（L（G））。{\displaystyle \chi '(G)=\chi (L(G))。}

辺の彩色可能性とグラフの最大次数の間には強い関係がある。同じ頂点に接するすべての辺はそれぞれ独自の色を必要とするため、 Δ（G）{\displaystyle \Delta (G)}

χ′（G）≥Δ（G）。{\displaystyle \chi '(G)\geq \Delta (G).}

さらに、

ケーニッヒの定理: Gが二部構成の場合。χ′（G）＝Δ（G）{\displaystyle \chi '(G)=\デルタ(G)}

一般に、この関係はブルックスの定理が頂点彩色に与える関係よりもさらに強い。

Vizing の定理:最大次数のグラフには辺彩色数または が。Δ{\displaystyle \Delta }Δ{\displaystyle \Delta }Δ+1{\displaystyle \Delta +1}

その他の特性

グラフがk色を持つ場合、かつそのグラフが非巡回的な向きを持ち、その最長パスの長さがk以下になる場合に限ります。これがGallai–Hasse–Roy–Vitaver の定理です( Nešetřil & Ossona de Mendez 2012 )。

平面グラフの場合、頂点カラーリングは本質的に、どこにもゼロがないフローと双対になります。

無限グラフについては、まだほとんど知られていません。以下は、無限グラフ彩色に関する数少ない研究結果のうちの2つです。

未解決の問題

上で述べたように、1998年のリードの予想では、その値は本質的に下限に近いという。ω（G）≤χ（G）≤Δ（G）+1.{\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}χ（G）≤⌈ω（G）+Δ（G）+12⌉。{\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}

平面 の彩色数（ 2点が単位距離であれば隣接している）は未知ですが、5、6、7 のいずれかです。グラフの彩色数に関するその他の未解決問題には、彩色数kを持つすべてのグラフにはマイナーとしてk頂点の完全グラフが存在するというHadwiger 予想、各ペアに共通する頂点が最大で 1 つである完全グラフの和の彩色数を上限とするErdős–Faber–Lovász 予想、およびk彩色グラフの中で交差数が最も小さいものが完全グラフであるというAlbertson 予想があります。

バーコフとルイスは、四色定理への攻撃において彩色多項式を導入した際、平面グラフ に対して、多項式は領域 に零点を持たないと予想しました。このような彩色多項式は領域 に零点を持たないこと、また であることが知られているにもかかわらず、彼らの予想は未だ解決されていません。また、同じ彩色多項式を持つグラフを特徴付け、どの多項式が彩色であるかを判断することも未解決の問題です。 G{\displaystyle G}P（G、t）{\displaystyle P(G,t)}[4、∞）{\displaystyle [4,\infty )}[5、∞）{\displaystyle [5,\infty )}P（G、4）≠0{\displaystyle P(G,4)\neq 0}

アルゴリズム

グラフの色付け
決断
名前グラフカラーリング、頂点カラーリング、kカラーリング
入力n頂点のグラフG。整数k
出力Gはk色による適切な頂点彩色を許容しますか?
実行時間O (2 n n ) [ 15 ]
複雑NP完全
削減額3-満足度
ゲイリー・ジョンソンGT4
最適化
名前彩色数
入力n個の頂点を持つグラフG。
出力χ ( G )
複雑NP困難
近似可能性O ( n (log  n ) −3 (log log  n ) 2 )
近似不可能性P = NPでない限り、 O ( n 1− ε )
数え上げ問題
名前彩色多項式
入力n頂点のグラフG。整数k
出力Gの適切なk色付けの数P  ( G , k )
実行時間O (2 n n )
複雑＃P完了
近似可能性制限されたケースに対するFPRAS
近似不可能性P = NPでない限りPTASは発生しない

多項式時間

グラフを2色で彩色できるかどうかを判断することは、グラフが二部グラフであるかどうかを判断することと等価であり、したがって幅優先探索または深さ優先探索を用いて線形時間で計算可能です。より一般的には、完全グラフの彩色数とそれに対応する彩色は、半正定値計画法を用いて多項式時間で計算できます。彩色多項式の閉式は、フォレスト、弦グラフ、サイクル、ホイール、ラダーなど、多くのグラフのクラスで知られているため、多項式時間で評価できます。

グラフが平面グラフで枝幅が狭い場合（または非平面グラフだが枝分解が既知である場合）、動的計画法を用いて多項式時間で解くことができます。一般に、必要な時間はグラフのサイズに対して多項式ですが、枝幅に対しては指数関数的です。

正確なアルゴリズム

k色彩のブルートフォース探索では、n個の頂点へのk色の割り当てをそれぞれ検討し、それぞれが正当かどうかを検証します。彩色数と彩色多項式を計算するために、この手順はあらゆる に対して用いられますが、入力グラフが最小の場合を除いて実用的ではありません。 けn{\displaystyle k^{n}}け＝1、…、n−1{\displaystyle k=1,\ldots ,n-1}

動的計画法と最大独立集合の数の上限を用いると、k色可能性は時間と空間で決定できる。[ 16 ]包含排他原理と高速ゼータ変換のための Yates アルゴリズムを用いると、任意のkに対してk色可能性は時間で決定できる[ 15 ] [ 17 ] [ 18 ] [ 19 ]。より高速なアルゴリズムは 3 色可能性と 4 色可能性で知られており、それぞれ時間で決定できる[ 20 ]と[ 21 ] 。また、5 色可能性と 6 色可能性、および疎グラフを含む制限されたグラフ族に対しては、指数関数的に高速なアルゴリズムが知られている。[ 22 ]O(2.4423n){\displaystyle O(2.4423^{n})}O(2nn){\displaystyle O(2^{n}n)}O(1.3289n){\displaystyle O(1.3289^{n})}O(1.7272n){\displaystyle O(1.7272^{n})}

収縮

グラフGの縮約とは 、頂点uとvを識別し、それらの間の辺を削除することによって得られるグラフです。元々uまたはvに接続していた残りの辺は、それらの識別（つまり、新たに融合されたノードuv ）に接続されるようになります。この操作は、グラフ彩色の解析において重要な役割を果たします。 G/uv{\displaystyle G/uv}

彩色数は再帰関係を満たす：

χ(G)=min{χ(G+uv),χ(G/uv)}{\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}

Zykov (1949)によるもので、uとv は隣接しない頂点であり、 は辺uvが追加されたグラフです。いくつかのアルゴリズムはこの再帰性を評価することに基づいており、結果として得られる計算木は Zykov 木と呼ばれることもあります。実行時間は、頂点uとvを選択するためのヒューリスティックに基づいています。 G+uv{\displaystyle G+uv}

彩色多項式は次の再帰関係を満たす。

P(G−uv,k)=P(G/uv,k)+P(G,k),{\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k),}

ここで、uとv は隣接する頂点であり、は辺uvを取り除いたグラフです。はグラフの適切な彩色の可能な数を表します。頂点は同じ色でも異なる色でも構いません。この場合、適切な彩色は 2 つの異なるグラフから生じます。説明するために、頂点uとvが異なる色である場合、 uとvが隣接するグラフを検討してもよいでしょう。uとv が同じ色である場合、 uとvが縮約されたグラフを検討してもよいでしょう。この再発を満たす他のグラフ特性についての Tutte の好奇心から、彼は彩色多項式の 2 変数一般化であるTutte 多項式を発見しました。 G−uv{\displaystyle G-uv}P(G−uv,k){\displaystyle P(G-uv,k)}

これらの式から、削除–縮約アルゴリズムと呼ばれる再帰手順が生成され、これはグラフ彩色のための多くのアルゴリズムの基礎となる。実行時間はフィボナッチ数列と同じ再帰関係を満たすため、最悪の場合でも、このアルゴリズムはn頂点m辺に対しての多項式係数以内で実行される。[ 23 ]この解析は、入力グラフの全域木の数の多項式係数以内にまで改善できる。 [ 24 ]実際には、分枝限定法やグラフ同型性拒絶法を用いて再帰呼び出しを回避する。実行時間は頂点ペアの選択に用いるヒューリスティックに依存する。 (1+52)n+m=O(1.6180n+m){\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}t(G){\displaystyle t(G)}

貪欲な色付け

同じグラフを異なる頂点順序で貪欲彩色する2つの例。右の例は、n頂点を持つ2色彩色可能なグラフに一般化され、貪欲アルゴリズムによって色が拡張されます。n/2{\displaystyle n/2}

貪欲アルゴリズムは、頂点を特定の順序, ...,で検討し、 , ...,の中から の隣接頂点で使用されていない最小の利用可能な色を に割り当て、必要に応じて新しい色を追加します。結果の色付けの品質は、選択した順序付けによって異なります。最適な色数で貪欲彩色を実現する順序付けが存在します。一方、貪欲彩色は任意に悪い結果になることもあります。例えば、n頂点のクラウングラフは2 色にすることができますが、 色で貪欲彩色を実現する順序付けがあります。 v1{\displaystyle v_{1}}vn{\displaystyle v_{n}}vi{\displaystyle v_{i}}vi{\displaystyle v_{i}}v1{\displaystyle v_{1}}vi−1{\displaystyle v_{i-1}}χ(G){\displaystyle \chi (G)}n/2{\displaystyle n/2}

弦グラフ、および区間グラフや無差別グラフといった弦グラフの特殊なケースでは、グラフの頂点順序を完全消去順序の逆とすることで、貪欲彩色アルゴリズムを用いて多項式時間で最適な彩色を求めることができる。完全順序付け可能グラフはこの性質を一般化しているが、これらのグラフの完全順序付けを求めるのはNP困難である。

頂点が次数に従って順序付けられている場合、結果として得られる貪欲彩色では最大で色、つまりグラフの最大次数より最大で 色多く使用されます。このヒューリスティックはウェルシュ・パウエルアルゴリズムと呼ばれることもあります。[ 25 ]ブレラズによる別のヒューリスティックでは、アルゴリズムの実行中に順序が動的に決定され、次に最も多くの異なる色に隣接する頂点が選択されます。[ 26 ]他の多くのグラフ彩色ヒューリスティックも同様に貪欲彩色に基づいており、特定の静的または動的戦略で頂点を順序付けます。これらのアルゴリズムは順次彩色アルゴリズム と呼ばれることもあります。maxi min{d(xi)+1,i}{\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}}

この数を最大化するように選択された頂点順序を使用して貪欲アルゴリズムによって取得できる最大 (最悪) の色数は、グラフの グランディ数と呼ばれます。

ヒューリスティックアルゴリズム

グラフの色付けのためのよく知られた 2 つの多項式時間ヒューリスティックは、DSatur アルゴリズムと再帰最大優先(RLF) アルゴリズムです。

貪欲彩色アルゴリズムと同様に、DSaturはグラフの頂点を1つずつ彩色し、必要に応じて未使用の色を消費します。新しい頂点が彩色されると、アルゴリズムは残りの未彩色頂点のうち、近傍に最も多くの異なる色を持つ頂点を特定し、次にその頂点を彩色します。これは、与えられた頂点の 彩度として定義されます。

再帰最大優先アルゴリズムは、各色クラスを1つずつ構築するという異なる方法で動作します。これは、特殊なヒューリスティックルールを用いてグラフ内の最大独立頂点集合を特定することで行われます。次に、これらの頂点に同じ色を割り当て、グラフから削除します。これらの処理は、残りの部分グラフに対して、頂点がなくなるまで繰り返されます。

DSaturの最悪ケースの計算量は であり、はグラフの頂点数である。このアルゴリズムは、飽和度を格納するバイナリヒープを用いて実装することもでき、 はグラフの辺数である。[ 27 ]これにより、疎グラフでの実行速度が大幅に向上する。RLFの全体的な計算量はにおいてDSaturよりもわずかに高い。[ 27 ]O(n2){\displaystyle O(n^{2})}n{\displaystyle n}O((n+m)log⁡n){\displaystyle O((n+m)\log n)}m{\displaystyle m}O(mn){\displaystyle O(mn)}

DSaturとRLFは二部グラフ、サイクルグラフ、ホイールグラフに対して正確である。[ 27 ]

並列および分散アルゴリズム

χ彩色グラフは、決定論的LOCALモデルにおいて、ラウンドで個のc 色グラフに彩色できることが知られています。また、ラウンド数の下限値も知られています。この下限値は、量子情報を交換できる量子コンピュータ（場合によっては事前に共有されたエンタングルメント状態を持つ）が許容される場合でも成立します。 O(n1/α){\displaystyle O(n^{1/\alpha })}α=⌊c−1χ−1⌋{\displaystyle \alpha =\left\lfloor {\frac {c-1}{\chi -1}}\right\rfloor }Ω(n1/α){\displaystyle \Omega (n^{1/\alpha })}

分散アルゴリズムの分野において、グラフ彩色は対称性の破れの問題と密接に関連している。現在の最先端のランダム化アルゴリズムは、最大次数Δが十分に大きい場合、決定論的アルゴリズムよりも高速である。最も高速なランダム化アルゴリズムは、シュナイダーとワッテンホファーによる多重試行法を採用している。[ 28 ]

対称グラフでは、決定論的分散アルゴリズムでは適切な頂点彩色を見つけることができません。対称性を破るためには、何らかの補助情報が必要です。標準的な仮定として、各ノードは初期状態で一意の識別子（例えば、{1, 2, ..., n }の集合から）を持っているとします。言い換えれば、n色彩が与えられていると仮定します。課題は、n色の色数を例えばΔ + 1色に減らすことです。Δ + 1色ではなくO (Δ)色を使用するなど、使用する色数が多いほど、必要な通信ラウンド数は少なくなります。[ 28 ]

(Δ + 1)-カラーリングの貪欲アルゴリズムの単純な分散バージョンでは、最悪の場合、Θ( n )回の通信ラウンドが必要になります。つまり、ネットワークの一方側からもう一方側に情報を伝播する必要がある場合があります。

最も単純で興味深い例はnサイクルである。リチャード・コールとウジ・ヴィシュキン[ 29 ]は、1回の同期通信ステップで色数をnからO (log  n )に削減する分散アルゴリズムが存在することを示している。同じ手順を繰り返すことで、 O ( log * n )回の通信ステップでnサイクルの3色化を実現することができる（ただし、ノード識別子が一意であると仮定）。  

関数log *（反復対数）は、極めて緩やかに増加する関数であり、「ほぼ定数」です。そのため、ColeとVishkinの結果は、nサイクルの3色化を行う定数時間分散アルゴリズムが存在するかどうかという疑問を提起しました。Linial (1992)は、これが不可能であることを示しました。つまり、決定論的な分散アルゴリズムは、nサイクルでn色化を3色化に縮約するために、Ω( log * n )回の通信ステップを必要とするということです。  

Cole と Vishkin による手法は、任意の制限次数グラフにも適用でき、実行時間は poly(Δ) + O ( log *  n ) です。[ 30 ]この手法は、 Schneider と Wattenhofer によって単位ディスクグラフに拡張されました。 [ 31 ]小さな Δ に対する (Δ + 1)-彩色の最速の決定論的アルゴリズムは、Leonid Barenboim、Michael Elkin、Fabian Kuhn によるものです。[ 32 ] Barenboim らによるアルゴリズムは、O (Δ) +  log * ( n )/2 の時間で実行され、定数係数 1/2 は Linial の下限により改善できないため、nの観点から最適です。Panconesiと Srinivasan (1996)は、ネットワーク分解を使用して、時間で Δ+1 彩色を計算しました。 2O(log⁡n){\displaystyle 2^{O\left({\sqrt {\log n}}\right)}}

辺彩色の問題は分散モデルにおいても研究されている。Panconesi & Rizzi (2001)は、このモデルにおいて(2Δ − 1)-彩色をO (Δ +  log *  n )時間で達成した。Linial (1992)による分散頂点彩色の下限値は、分散辺彩色問題にも当てはまる。

分散型アルゴリズム

分散型アルゴリズムは、メッセージの受け渡しが許可されないアルゴリズムです（ローカルなメッセージの受け渡しが行われる分散型アルゴリズムとは対照的です）。適切な色付けが存在する場合にグラフを色付けする効率的な分散型アルゴリズムも存在します。これらのアルゴリズムでは、頂点が隣接する頂点のいずれかが自分と同じ色を使用しているかどうか、つまりローカルな競合が存在するかどうかを感知できることを前提としています。これは多くのアプリケーションでは控えめな仮定です。例えば、無線チャネル割り当てでは、ステーションが他の干渉送信機が同じチャネルを使用しているかどうかを検出できると想定するのが通常合理的です（SINRを測定するなど）。この感知情報は、学習オートマトンに基づくアルゴリズムが確率1で適切なグラフの色付けを見つけるのに十分です。[ 33 ]

計算の複雑さ

グラフ彩色は計算的に困難である。与えられたグラフが、与えられたkに対してk彩色を許容するかどうかを判定することは、 k ∈ {0,1,2}の場合を除いてNP 完全である。特に、彩色数を計算することは NP 困難である。[ 34 ] 3 彩色問題は、4 正則平面グラフ上でも NP 完全である。[ 35 ]しかし、最大次数が 3 以下のグラフでは、ブルックスの定理により、3 彩色問題は線形時間で解けることが示される。さらに、任意のk > 3 に対して、4 色定理により平面グラフのk彩色が存在し、そのような彩色を多項式時間で見つけることが可能である。しかし、平面グラフの辞書式最小の 4 彩色を見つけることは NP 完全である。[ 36 ]

最もよく知られている近似アルゴリズムは、彩色数の係数O（n（log log  n）2（log n）−3 ）以内のサイズの彩色を計算する。[ 37 ]すべてのε >0に対して、 n 1− ε 以内で彩色数を近似することはNP困難である。[ 38 ]

3色塗り可能なグラフを5色で塗り分けることもNP困難である。[ 39 ] 4色塗り可能なグラフを7色で塗り分けることもNP困難である。 [ 39 ] k≥5のk色塗り可能なグラフを5色で塗り分けることもNP困難である。 [ 40 ](k⌊k/2⌋)−1{\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1}

彩色多項式の係数を計算するのは#P困難である。実際、k  = 1とk  = 2を除く任意の有理点kにおいて、の値を計算することさえ#P困難である。 [ 41 ] NP  =  RPでない限り、 k  = 2を除く任意の有理点k  ≥ 1.5において彩色多項式を評価するFPRASは存在しない。[ 42 ]χ(G,k){\displaystyle \chi (G,k)}

辺彩色については、ヴィジングの結果の証明は最大Δ+1色を使用するアルゴリズムを与える。しかし、辺彩色数の2つの候補値の間で決定することはNP完全である。[ 43 ]近似アルゴリズムの観点から見ると、ヴィジングのアルゴリズムは辺彩色数が4/3以内に近似できることを示しており、困難性の結果は、  P = NPでない限り、任意のε > 0に対して(4/3 − ε )アルゴリズムが存在しないことを示す。これらは近似アルゴリズムの文献の中で最も古い結果の一つであるが、どちらの論文でもその概念が明示的に用いられていない。[ 44 ]

アプリケーション

スケジュール

頂点彩色モデルは、多くのスケジューリング問題に適用できる。[ 45 ]最も単純な形式では、与えられた一連のジョブを時間スロットに割り当てる必要があり、各ジョブにはそのようなスロットが1つ必要である。ジョブは任意の順序でスケジュールできるが、ジョブのペアは競合する可能性がある。つまり、同じ時間スロットに割り当てられない可能性がある。これは、たとえば、ジョブが共有リソースに依存している場合などである。対応するグラフには、すべてのジョブに対応する頂点と、競合するジョブのペアに対応する辺が含まれる。グラフの彩色数は、すべてのジョブを競合なく完了するための最適時間である最小メイクスパンとまったく同じである。

スケジューリング問題の詳細によってグラフの構造が決まります。例えば、航空機をフライトに割り当てる場合、結果として得られる競合グラフは区間グラフとなるため、彩色問題は効率的に解くことができます。無線局への帯域幅割り当ての場合、結果として得られる競合グラフは単位円グラフとなるため、彩色問題は3近似可能です。

レジスタ割り当て

コンパイラとは、あるコンピュータ言語を別の言語に変換するコンピュータプログラムです。生成されたコードの実行時間を改善するために、コンパイラの最適化手法の一つとしてレジスタ割り当てが挙げられます。レジスタ割り当てとは、コンパイルされたプログラムで最も頻繁に使用される値を高速プロセッサレジスタに保持する手法です。理想的には、値は使用時にすべてレジスタ内に格納されるようにレジスタに割り当てられます。

この問題に対する教科書的なアプローチは、グラフ彩色問題としてモデル化することにある。[ 46 ]コンパイラは干渉グラフを構築する。干渉グラフでは、頂点は変数であり、辺は2つの頂点が同時に必要になった場合にそれらを結ぶ。グラフをk色で彩色できる場合、同時に必要となる変数の集合は最大k個のレジスタに格納できる。

その他のアプリケーション

グラフの色分け問題は、スポーツのスケジュール作成、[ 47 ]、座席表の作成、[ 48 ]、試験の時間割作成、[ 49 ] 、タクシーのスケジュール作成、[ 50 ] 、数独パズルを解くなど、多くの実用的な分野で発生します。[ 51 ]

その他の着色料

ラムゼイ理論

不適切な彩色問題の重要なクラスは、ラムゼー理論で研究されています。この理論では、グラフの辺に色が割り当てられ、接続する辺の色には制限がありません。簡単な例としては、友人と他人の定理があります。これは、6つの頂点を持つ完全グラフの辺をどのように彩色しても、単色三角形が存在するというものです。これは、6人組のいずれにも、3人は互いに他人か3人は知り合いがいるという形でよく説明されます。ラムゼー理論は、この考え方を一般化して無秩序さの中に規則性を求め、与えられた構造を持つ単色部分グラフが存在するための一般条件を見つけることに関係しています。 K6{\displaystyle K_{6}}

モジュラーカラーリング

モジュラーカラーリングは、各頂点の色が隣接する頂点の色の合計となるグラフカラーリングの一種です。

k ≥ 2 を色の数とし、 はkを法とする整数の集合で、要素（または色）0,1,2, ..., k-2, k-1から構成される。まず、 の要素を用いて G の各頂点を彩色し、隣接する2つの頂点に同じ色を割り当てることができるようにしたい。言い換えれば、 c を c: V(G) → となる彩色とし、隣接する頂点に同じ色を割り当てることができるようにしたい。 Zk{\displaystyle \mathbb {Z} _{k}}Zk{\displaystyle \mathbb {Z} _{k}}Zk{\displaystyle \mathbb {Z} _{k}}

Gの各頂点vについて、vの色和σ(v)は、vに隣接するすべての頂点のmod kの合計である。vの色和は次のように表される。

σ(v) = ∑ u ∈ N(v) c(u)、

ここで、u は v の近傍にある任意の頂点 N(v) である。次に、各頂点を、隣接する頂点の和によって決定される新しい彩色で彩色する。グラフ G がモジュラー k-彩色を持つとは、隣接する頂点の任意のペア a,b に対して、σ(a) ≠ σ(b) が成り立つことを意味する。G のモジュラー彩色数 mc(G) は、G のモジュラー k-彩色が存在するような k の最小値である。<

例えば、頂点vが、0、1、1、3 mod 4 (k=4) の色を持つ頂点に隣接しているとします。色の合計は σ(v) = 0 + 1 + 1 + 3 mod 4 = 5 mod 4 = 1 となります。これが頂点vの新しい色です。このプロセスをG内のすべての頂点に対して繰り返します。隣接する2つの頂点の色の合計が等しい場合、Gは4を法とする彩色を持ちません。隣接するどの頂点の色の合計も等しくない場合、Gは4を法とする彩色を持ちます。

その他の着色料

符号付きグラフやゲイングラフでも色付けを検討できます。

参照

注記

  1. ^マッケンジー、ドナルド（2004年）『証明の機械化：コンピューティング、リスク、そして信頼』MITプレス、103ページ。
  2. ^ M. Kubale、「グラフカラーリングの歴史」、 Kubale (2004)。
  3. ^ヴァン リント & ウィルソン (2001)、第 1 章。 33.
  4. ^ジェンセンとトフト (1995)、p. 2.
  5. ^ Weisstein, Eric W. 「Chromatic Number」 . mathworld.wolfram.com . 2025年2月9日閲覧。
  6. ^ Weisstein, Eric W. 「オイラー特性」 . mathworld.wolfram.com . 2025年2月9日閲覧。
  7. ^トゥッテ（1949）
  8. ^トゥッテ（1954）
  9. ^張（1997）
  10. ^ブルックス（1941年）。
  11. ^デカルト (1947) .
  12. ^スコット＆シーモア (2020) .
  13. ^ a b Pawlik et al. (2014) .
  14. ^エルデシュ (1959) .
  15. ^ a bビョークルンド、フスフェルト、コイヴィスト (2009)、p. 550。
  16. ^ローラー（1976年）。
  17. ^イェーツ（1937）、66-67ページ。
  18. ^ Knuth（1997）、第4.6.4章、pp.501-502。
  19. ^コイヴィスト (2004)、45、96–103 ページ。
  20. ^ Beigel & Eppstein (2005) .
  21. ^ Fomin、Gaspers、Saurabh（2007年）。
  22. ^ザミール (2021) .
  23. ^ウィルフ（1986年）。
  24. ^関根、今井、谷 (1995)。
  25. ^ウェルシュ＆パウエル（1967年）。
  26. ^ブレラズ (1979) .
  27. ^ a b cルイス (2021) .
  28. ^ a bシュナイダー＆ワッテンホーファー (2010)。
  29. ^ Cole & Vishkin (1986) 、 Cormen、Leiserson & Rivest (1990 、第30.5節)も参照。
  30. ^ゴールドバーグ、プロトキン、シャノン（1988）。
  31. ^シュナイダー＆ワッテンホファー（2008年）。
  32. ^バレンボイムとエルキン (2009) ;クーン (2009)。
  33. ^例えば、Leith & Clifford (2006)およびDuffy、O'Connell & Sapozhnikov (2008)を参照。
  34. ^ゲイリー、ジョンソン＆ストックマイヤー (1974) ; ゲイリー＆ジョンソン (1979)。
  35. ^デイリー（1980） .
  36. ^ Khuller & Vazirani (1991) .
  37. ^ Halldórsson (1993) .
  38. ^ザッカーマン（2007） .
  39. ^ a b Bulín、Krokhin、Opršal (2019) .
  40. ^ Wrochna＆Živný (2020) .
  41. ^イェーガー、ヴァーティガン、ウェルシュ（1990）。
  42. ^ゴールドバーグ＆ジェラム（2008年）。
  43. ^ホリヤー（1981） .
  44. ^クレセンツィ＆カン（1998）。
  45. ^マルクス（2004年）。
  46. ^チャイティン（1982） .
  47. ^ Lewis (2021)、pp. 221–246、第8章：スポーツリーグの設計。
  48. ^ Lewis (2021)、pp. 203–220、第7章：座席計画の設計。
  49. ^ Lewis (2021)、pp. 247–276、第9章：大学の時間割の設計。
  50. ^ Lewis (2021)、pp. 5–6、セクション1.1.3：タクシーのスケジュール作成。
  51. ^ Lewis (2021)、pp. 172–179、セクション6.4：ラテン方陣と数独パズル。

参考文献

ウィキメディア コモンズには、グラフの色付けに関連するメディアがあります。
「 https://en.wikipedia.org/w/index.php?title=Graph_coloring&oldid=1327327996」より取得