正規ラベル（カノニカルラベル）とは？グラフ同型性判定の基本を解説

正規ラベル（カノニカルラベル）とは

グラフの同型性問題を扱う標準的な手法の一つに、各グラフを「コード」あるいは「正規ラベル（カノニカルラベル）」と呼ばれる特定の文字列表現へ変換する方法があります。正規ラベルには、2つのグラフが同型である場合、それらのコードが必ず等しくなるという重要な性質があります。

この性質により、グラフ同型性の判定は、各グラフの正規ラベルを分析・比較するだけで行えるようになります。グラフの正規ラベルを構築するための最初のステップは、そのグラフの隣接行列表現を求めることです。

隣接行列には複数の表現が存在する

隣接行列では頂点の並び順を複数の方法で決められるため、1つのグラフに対して複数の隣接行列表現が存在し得ます。例えば、1行目・1列目が3本の辺を持つ頂点aに対応し、2行目・2列目が2本の辺を持つ別の頂点に対応する、といった具合です。グラフのすべての隣接行列表現を導出するには、行列の行のすべての順列を考慮する必要があります。

順列行列による変換の例

例として、次の行列を考えてみましょう。

M = 1  2  3  4
    5  6  7  8
    9  10 11 12
    13 14 15 16

この行列Mの1行目（および1列目）と3行目を入れ替えるには、次のような順列行列を使用します。

P13 = 0 0 1 0
      0 1 0 0
      1 0 0 0
      0 0 0 1

ここでP₁₃は、単位行列の1行目と3行目を交換することで得られる行列です。1行目と3行目（および列）を入れ替えるには、この順列行列をMに掛け合わせます。

M′ = P13T × M × P13 = 11 10 9  12
                        7  6  5  8
                        3  2  1  4
                        15 14 13 16

文字列表現の決定方法

次のステップは、各隣接行列に対する文字列表現を決定することです。隣接行列は対称行列であるため、行列の上三角部分に基づいて文字列表現を生成するのが効率的です。

コードは、上三角行列の要素を列ごとに連結することで得られます。そして最後のステップとして、グラフのすべての文字列表現を比較し、辞書順で最小（または最大）の値を持つものを正規ラベルとして選択します。

計算量の課題と最適化手法

このアプローチは、グラフのすべての可能な隣接行列を求め、それぞれの文字列表現を評価して正規ラベルを発見する必要があるため、計算コストが高いという課題があります。さらに、k個の頂点を含むグラフに対しては、k!個の順列を考慮しなければならず、頂点数の増加に伴って組合せが爆発的に増大します。

この課題の計算量を削減するために、さまざまな手法が開発されています。具体的には、以下のような工夫が挙げられます。

・以前に計算された正規ラベルをキャッシュとして保存し、再計算を回避する
・頂点ラベルや頂点の次数などの追加情報を取り入れ、正規ラベルの決定に必要な順列の数を削減する

これらの最適化により、実用的な規模のグラフに対しても正規ラベルによる同型性判定を効率的に適用できるようになっています。