貪欲な色付け

数学とコンピュータサイエンスにおけるグラフ彩色問題の研究では、貪欲彩色または順次彩色^[1]は、グラフの頂点を順番に検討し、各頂点に最初に利用可能な色を割り当てる貪欲アルゴリズムによって形成されるグラフの頂点の彩色です。貪欲彩色は線形時間で見つけることができますが、一般的には可能な限り最小の数の色を使用しません。

頂点のシーケンスの選択によって、通常、与えられたグラフの色付けは異なるため、貪欲な色付けの研究の多くは、適切な順序付けを見つける方法に関係しています。最適な色付けを生成する順序付けは常に存在しますが、そのような順序付けは多くの特殊なグラフのクラスで見つけることができますが、一般的に見つけることは困難です。頂点の順序付けによく使用される戦略には、次数の高い頂点を次数の低い頂点よりも前に配置するか、制約の少ない頂点よりも利用可能な色が少ない頂点を選択することが含まれます。

貪欲彩色のバリエーションでは、グラフの彩色されていない部分の構造を知らなくてもオンラインで色を選択したり、色の総数を減らすために最初に利用可能な色以外の色を選択したりします。貪欲彩色のアルゴリズムは、スケジューリングやレジスタ割り当ての問題、組み合わせゲームの分析、彩色と次数の関係に関するブルックスの定理などの数学的結果の証明に適用されています。貪欲彩色から派生したグラフ理論の他の概念には、グラフのグランディ数（貪欲彩色で見つけられる色の最大数）や、すべての貪欲彩色で同じ数の色を使用するグラフであるよく彩色されたグラフなどがあります。

与えられた頂点順序に対する貪欲な色付けは、線形時間で実行されるアルゴリズムによって計算できます。アルゴリズムは、与えられた順序で頂点を処理し、処理されるたびに各頂点に色を割り当てます。色は数字で表すことができ、各頂点には、その近傍のいずれにも使用されていない最小の番号の色が割り当てられます。使用可能な最小の色を見つけるには、配列を使用して各色の近傍の数を数え（または、近傍の色のセットを表し）、配列をスキャンして最初のゼロのインデックスを見つけます。^[2]${\displaystyle 0,1,2,\dots }$

Pythonでは、アルゴリズムは次のように表現できます。

def  first_available ( colors ): 
"""指定された色のセットに含まれない最小の非負整数を返します。    """ color = 0 while color in colors : color += 1 return color    

      
       
          
     

def  greedy_coloring ( G ,  order ): 
"""指定された順序で G の貪欲色付けを見つけます。    

    G の表現は https://www.python.org/doc/essays/graphs/ のよう
    に、ノード/頂点の近傍を "for w in G[node]" で反復処理できるものと想定されます。
    戻り値は、頂点をその色にマッピングする辞書です。
    """ 
    coloring  =  dict () 
    for  node  in  order : 
        used_neighbour_colors  =  { coloring [ nbr ] 
                                 for  nbr  in  G [ node ] 
                                 if  nbr  in  coloring } 
        coloring [ node ]  =  first_available ( used_neighbour_colors ) 
    return  coloring

サブルーチンfirst_availableは、引数リストの長さに比例した時間がかかります。これは、リスト自体に対するループと、同じ長さのカウントのリストに対するループの 2 つを実行するためです。色付けアルゴリズム全体の時間は、このサブルーチンの呼び出しによって大きく左右されます。グラフ内の各辺は、これらの呼び出しの 1 つ、つまり頂点順序付けで後にある辺のエンドポイントに対する呼び出しにのみ寄与します。したがって、引数リストの長さの合計first_availableと、アルゴリズムの合計時間は、グラフ内の辺の数に比例します。^[2]

同じ色付けを行う別のアルゴリズム^[3]は、頂点の集合を各色で 1 色ずつ選択するというものである。この方法では、各色クラスは、頂点を指定された順序でスキャンすることによって選択される。このスキャンで、に隣接頂点がない色なしの頂点に遭遇すると、が に追加される。このようにして、 は、小さい色が割り当てられていない頂点の中で最大の独立集合になる。アルゴリズムは、すべての頂点が色付けされるまで、このように色クラスを繰り返し検出する。ただし、この方法では、上記の 1 回のスキャンのみを使用する方法ではなく、色クラスごとに 1 回のスキャンでグラフを複数回スキャンする必要がある。^[4]${\displaystyle C}$${\displaystyle v}$${\displaystyle C}$${\displaystyle v}$${\displaystyle C}$${\displaystyle C}$

グラフの頂点の順序が異なると、貪欲な彩色で使用する色の数も異なる場合があります。使用する色の数は、最適な色数から、場合によってはグラフの頂点数に比例する色数までさまざまです。たとえば、クラウン グラフ( i ≠ j の場合は必ずa _{i を}b jに接続して、 n /2 個の頂点の互いに素な 2 つのセット{ a ₁、a ₂、 ... } と{ b ₁、b ₂、 ... } から形成されるグラフ) は_、貪欲な彩色には特に不向きです。頂点の順序がa ₁ 、b ₁、a ₂、b ₂、 ...の場合、貪欲な彩色では、各ペア( a _i、b _i )に 1 色ずつ、n /2色が使用されます。ただし、このグラフに最適な色の数は 2 色で、頂点a _iに 1 色、頂点b _iにもう 1 色使用されます。^[5]また、ランダムに選択された頂点の順序によって、最小値よりもはるかに多くの色数になる確率が高いグラフも存在します。^[6]したがって、貪欲な着色では、頂点の順序を慎重に選択することが重要です。

グラフの頂点は常に、貪欲アルゴリズムが最適な色付けを生成するような順序に並べることができます。なぜなら、任意の最適な色付けが与えられた場合、頂点を色で並べることができるからです。次に、この順序で貪欲アルゴリズムを使用すると、結果として得られる色付けは自動的に最適になります。^[7]しかし、最適なグラフ色付けはNP完全であるため、貪欲色付けの最適な順序付けを見つけることを含め、この問題を迅速に解決できるサブ問題はNP困難です。^[8]

区間グラフと弦グラフでは、頂点が完全な消去順序の逆順に並べられている場合、各頂点の前の隣接頂点はクリークを形成する。この特性により、貪欲彩色は各クリークに必要な色数以上の色を使用しないため、最適な彩色を生成する。消去順序は、存在する場合、線形時間で見つけることができる。^[9]

より強い言い方をすれば、任意の完全な消去順序は遺伝的に最適であり、グラフ自体とそのすべての誘導サブグラフの両方にとって最適であることを意味する。完全に順序付け可能なグラフ（弦グラフ、比較可能性グラフ、距離遺伝グラフを含む）は、遺伝的に最適な順序付けを持つグラフとして定義される。^[10]完全に順序付け可能なグラフを認識することはNP完全でもある。^[11]

与えられたグラフの最悪の順序付けに対する貪欲彩色によって生成される色の数は、そのグラフのグランディ数と呼ばれる。^[12] 貪欲彩色のための良い頂点順序付けを見つけることが難しいのと同様に、悪い頂点順序付けを見つけることも難しい。与えられたグラフGと数kに対して、貪欲アルゴリズムがk色以上を使用するようなGの頂点順序付けが存在するかどうかを判断することは NP 完全である。特に、これはGの最悪の順序付けを見つけることが難しいことを意味する。^[12]

よく色付けされたグラフとは、すべての頂点順序で生成される色数が同じグラフのことである。これらのグラフでは、この色の数は彩色数とグランディ数の両方に等しい。^[12]これらにはコグラフが含まれており、これはまさにすべての誘導された部分グラフがよく色付けされているグラフである。^[13]しかし、グラフがよく色付けされているかどうかを判断することはコNP完全である。 ^[12]

エルデシュ・レーニイモデルから各辺が一定の確率でランダムグラフを描画した場合、グラフの辺とは独立に選択された頂点の順序は、高い確率で最適値の2倍に近い色の数になる。これらのグラフの有意に優れた色付けを見つける多項式時間法があるかどうかは不明である。^[3]

最適な頂点順序付けは難しいため、最適な色数を保証せずに色の数を減らすヒューリスティックが使用されてきた。貪欲彩色でよく使用される順序付けは、最小次数の頂点v を選択し、 v を削除したサブグラフを再帰的に順序付けし、v を順序付けの最後に配置することである。このアルゴリズムが遭遇する削除された頂点の最大次数は、グラフの退化と呼ばれ、 dと表記される。貪欲彩色のコンテキストでは、同じ順序付け戦略は最小最終順序付けとも呼ばれる。^[14]この頂点順序付けと退化は、線形時間で計算できる。^[15] これは、頂点を次数の降順で並べ替える以前の頂点順序付け方法である最大優先順序付けの改良版と見なすことができる。^[16]

退化順序では、貪欲彩色は最大d  + 1色を使用します。これは、彩色時に、各頂点が最大d 個の既に彩色された隣接頂点を持つため、最初のd  + 1色のうちの 1 つが自由に使用できるためです。^[17]退化順序での貪欲彩色は、木、疑似森林、クラウングラフなど、特定のグラフのクラスに対して最適な彩色を見つけることができます。^[18] Markossian、Gasparian、Reed (1996) は、 およびのすべての誘導サブグラフに対して、彩色が退化に 1 を加えた値に等しい場合、グラフを -完全であると定義しています。これらのグラフでは、退化順序での貪欲アルゴリズムは常に最適です。^[19] すべての-完全グラフは、偶数サイクルの彩色数が 2 で退化が 2 であり、-完全グラフの定義における等式と一致しないため、偶数ホールのないグラフでなければなりません。グラフとその補グラフの両方が偶数ホールフリーである場合、それらは両方とも -完全である。完全グラフかつ -完全グラフであるグラフは、まさに弦グラフである。より一般的には、偶数ホールフリーグラフでは、退化順序は最適な色数を最大で最適な色数の2倍以内に近似する。つまり、その近似率は2である。^[20]単位円グラフでは、その近似率は3である。 ^[21]三角柱は、その退化順序の1つが最適でない色付けにつながる最小のグラフであり、正方形反柱は、その退化順序のいずれを使用しても最適に色付けできない最小のグラフである。^[18]${\displaystyle G}$${\displaystyle \beta}$${\displaystyle G}$${\displaystyle G}$${\displaystyle \beta}$${\displaystyle \beta}$${\displaystyle \beta}$${\displaystyle \beta}$

ブレラズ (1979) は、貪欲彩色における頂点の順序付けに、順序付けの構築と彩色処理を交互に行うDSaturと呼ばれる戦略を提案している。彼のバージョンの貪欲彩色アルゴリズムでは、各ステップで彩色する次の頂点は、近傍に最も多くの異なる色を持つ頂点として選択される。同点の場合は、同点の頂点の中から、彩色されていない頂点のサブグラフ内で最大次数の頂点が選択される。各ステップで近傍色の集合とその濃度を追跡することにより、この方法を線形時間で実装することができる。^[22]

この方法は、二部グラフ、^[23]すべてのサボテングラフ、すべての車輪グラフ、最大6頂点のすべてのグラフ、およびほぼすべての -色付け可能なグラフの最適色付けを見つけることができます。^[24] Lévêque & Maffray (2005) は当初、この方法がメイニエルグラフの最適色付けを見つけると主張しましたが、後にこの主張に対する反例を発見しました。^[25]${\displaystyle k}$

貪欲な色付けアルゴリズムのバリエーションを定義することもできます。このバリエーションでは、特定のグラフの頂点が特定の順序で色付けされますが、各頂点に選択される色は必ずしも最初に利用可能な色ではありません。これらには、グラフの色が付けられていない部分がアルゴリズムに知られていない方法や、基本的な貪欲なアルゴリズムよりも優れた色付けを選択する自由がアルゴリズムに与えられる方法が含まれます。

代替の色選択戦略は、オンラインアルゴリズムの枠組みの中で研究されてきた。オンライングラフカラーリング問題では、グラフの頂点が任意の順序で1つずつカラーリングアルゴリズムに提示され、アルゴリズムは、すでに処理された頂点の色と頂点間の隣接性のみに基づいて、各頂点の色を選択する必要があります。この文脈では、色選択戦略の品質は、その競合比、つまり使用される色の数と特定のグラフに最適な色の数の比率によって測定されます。^[26]

グラフに追加の制約が与えられていない場合、最適な競争比率はわずかに線形以下になります。^[27]ただし、区間グラフでは一定の競争比率が実現可能であり、^[28]二部グラフと疎グラフでは対数比率が実現できます。実際、疎グラフでは、利用可能な最初の色を選択する標準的な貪欲着色戦略によってこの競争比率が実現され、任意のオンライン着色アルゴリズムの競争比率の一致する下限を証明することができます。^[26]

与えられたグラフと頂点の順序に対する倹約的彩色は、与えられた順序で頂点を彩色し、以前のすべての色が与えられた頂点に隣接している場合にのみ新しい色を導入し、既存の色を再利用できる場合は使用する色を選択できる（常に最小の色を選択するのではなく）貪欲アルゴリズムによって生成される彩色と定義されています。順序付き彩色数は、このようにして与えられた順序で取得できる色の最小数であり、無彩色数は、与えられたグラフのすべての頂点彩色の中で最大の順序付き彩色数です。定義は異なりますが、無彩色数は常にグランディ数に等しくなります。^[29]

貪欲彩色は高速で、多くの場合、使用する色数が少ないため、最適ではないが優れたグラフ彩色が必要なアプリケーションで使用できます。貪欲アルゴリズムの初期の応用の 1 つは、コース スケジューリングなどの問題でした。コース スケジューリングでは、一連のタスクを特定のタイム スロットに割り当て、互換性のないタスクが同じタイム スロットに割り当てられないようにする必要があります。^[4]また、コンパイラーでレジスタ割り当てに 使用することもできます。これは、頂点がレジスタに割り当てられる値を表し、辺が同じレジスタに割り当てることができない 2 つの値の競合を表すグラフに適用します。^[30]多くの場合、これらの干渉グラフは弦グラフであるため、貪欲彩色によって最適なレジスタ割り当てを生成できます。^[31]

組合せゲーム理論では、頂点がゲームの位置を表し、辺が1つの位置から別の位置への有効な動きを表す有向非巡回グラフとして明示的に与えられた公平なゲームに対して、貪欲彩色アルゴリズム（グラフの位相順序の逆を使用）が各位置のnim値を計算する。これらの値は、任意の単一のゲームまたは任意のゲームの分離和における最適なプレイを決定するために使用できます。^[32]

最大次数Δのグラフの場合、貪欲彩色では最大Δ + 1色しか使用されません。ブルックスの定理によれば、2 つの例外 (クリークと奇数サイクル) を除き、最大でΔ色が必要です。ブルックスの定理の証明の 1 つは、最初の 2 つの頂点が最後の頂点に隣接しているが、互いに隣接しておらず、最後の頂点以外の各頂点には少なくとも 1 つの後続の頂点があるような頂点の順序付けを見つけることです。この特性を持つ順序付けの場合、貪欲彩色アルゴリズムでは最大でΔ色が使用されます。^[33]