色彩調整アルゴリズム

グラフ理論と理論計算機科学において、色彩改良アルゴリズムは、ナイーブ頂点分類、またはワイスファイラー・レーマンアルゴリズムの1次元バージョンとしても知られ、2つのグラフが同型であるかどうかをテストするために使用されるルーチンです。^[1]ほぼすべてのグラフのグラフ同型性を解決しますが、すべての通常グラフなど、色の改良を使用して区別できないグラフもあります。

このアルゴリズムは、頂点を持つグラフを入力として受け取ります。反復処理が進行し、各反復処理で頂点の新しい色付けが生成されます。正式には、「色付け」とは、このグラフの頂点から何らかのセット (「色」) への関数です。各反復処理で、頂点の色付けのシーケンスを次のように定義します。 ${\displaystyle G}$${\displaystyle n}$${\displaystyle \lambda_{i}}$

• ${\displaystyle \lambda_{0}}$は初期色付けです。グラフにラベルが付いていない場合には、初期色付けによって各頂点に単純な色が割り当てられます。グラフにラベルが付いている場合には、頂点のラベルになります。${\displaystyle \lambda _{0}(v)}$${\displaystyle v}$${\displaystyle \lambda_{0}}$${\displaystyle v}$
• すべての頂点に対して、 を設定します。${\displaystyle v}$${\displaystyle \lambda _{i+1}=\left(\lambda _{i}(v),\{\{\lambda _{i}(w)\mid w{\text{ は }}v の近傍である\}\}\right)}$

言い換えれば、頂点の新しい色は、前の色とその近傍の色の多重集合から形成されるペアです。このアルゴリズムは、現在の色付けを改良し続けます。ある時点で、色付けは安定します。つまり、 です。この最終的な色付けは、安定色付けと呼ばれます。 ${\displaystyle v}$${\displaystyle \lambda_{i+1}\equiv \lambda_{i}}$

色の改良は、重要な計算問題であるグラフ同型性のサブルーチンとして使用できます。この問題では、入力として 2 つのグラフがあり、それらが同型であるかどうかを判断することがタスクです。非公式には、これは 2 つのグラフが頂点の再ラベル付けまで同じであることを意味します。 ${\displaystyle G,H}$

と が同型かどうかをテストするには、次の操作を試します。両方のグラフで色の調整を実行します。生成された安定した色が異なる場合、2 つのグラフは同型ではないことがわかります。ただし、2 つのグラフが同型ではないにもかかわらず、同じ安定した色が生成される可能性があります。以下を参照してください。 ${\displaystyle G}$${\displaystyle H}$

頂点グラフを入力として色の改良を行うと、最大で 回の反復後に安定した色付けが生成されることがわかります。逆に、この境界が実現されるグラフも存在します。^[2]これは、頂点の数と辺の数である実装につながります。 ^[3]この複雑さは、合理的な仮定の下で最適であることが証明されています。^[4]${\displaystyle n}$${\displaystyle n-1}$${\displaystyle O((n+m)\log n)}$${\displaystyle n}$${\displaystyle m}$

2 つのグラフと が色の調整によって区別される とは、アルゴリズムが と で異なる出力を に対して生成する場合を言います。色の調整によって区別されないグラフの簡単な例があります。たとえば、長さ 6 の閉路と三角形のペアは区別されません ( ^[5]の例 V.1 )。それにもかかわらず、このアルゴリズムは、ランダム グラフがアルゴリズムによって漸近的にほぼ確実に識別されるという点で非常に強力です。^{[6]さらに強力なのは、 が増加するにつれて、色の調整によって識別され}ないグラフの割合がの順序で指数関数的に減少することが示されていることです。^[7]${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle n}$${\displaystyle n}$

色の洗練の表現力には論理的な特徴もあります。2つのグラフを色の洗練によって区別できるのは、それらをカウント付きの第1階述語論理の2つの変数フラグメントによって区別できる場合のみです。^[8]