正規のラベルとは何ですか？

グラフ同型の問題を処理するための標準的な方法は、各グラフをそのコードまたは正規ラベルと呼ばれる特定の文字列表現にマップすることです。正規ラベルには、2つのグラフが同型である場合、それらのコードは等しくなければならないという特性があります。

このプロパティを使用すると、グラフの正規ラベルを分析することにより、グラフ同型をテストできます。グラフの正規ラベルを作成するための最初のフェーズは、グラフの隣接行列の記述を見つけることです。与えられたグラフのそのような行列のインスタンスを示しています。

隣接行列の頂点を並べ替える方法はいくつかあるため、グラフには複数の隣接行列の説明を含めることができます。最初の行と列は3つのエッジを持つ頂点aに相関し、2番目の行と列は2つのエッジを持つ別の頂点aに相関します。グラフのすべての隣接行列の記述を変更できます。行列の行のすべての可能な順列を処理しました。

例 −次のマトリックスを検討してください

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

次の置換行列を使用して、最初の行（および列）をM-

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 X M X P13= 11 10 9 12
                    7  6 5  8
                    3  2 1  4
                   15 14 13 16

2番目のステップは、各隣接行列の文字列の説明を決定することです。隣接行列は対称であるため、行列の上三角部分に応じて文字列の説明を作成すると効率的です。

コードは、上三角行列のエントリを列方向にリンクすることによって取得されます。最後のステップは、グラフのすべての文字列の説明を相互に関連付け、辞書式順序の値が最も低い（または最も高い）ものを選択することです。

以前のアプローチは、グラフのすべての可能な隣接行列を決定し、それらの文字列の説明のそれぞれを評価して正規のラベルを見つける必要があるため、コストがかかるように見えます。さらに、k個の頂点を含むグラフごとに処理する必要があるkl順列があります。

このタスクの複雑さを軽減するために開発されたさまざまな方法があります。これには、以前に計算された正規ラベルのキャッシュと、頂点ラベルや頂点の次数などのデータをさらに組み込むことにより、正規ラベルを決定するために必要な順列の数を減らすことが含まれます。