グラフ正規化

グラフ理論は数学の一分野であり、グラフの正準化とは、与えられたグラフGの正準形式を見つける問題です。正準形式とは、 Gと同型なラベル付きグラフCanon( G )であり、 Gと同型なすべてのグラフはGと同じ正準形式を持ちます。したがって、グラフの正準化問題の解から、グラフの同型性の問題も解くことができます。2 つのグラフGとH が同型であるかどうかをテストするには、それらの正準形式 Canon( G ) と Canon( H ) を計算し、これら 2 つの正準形式が同一であるかどうかをテストします。

グラフの標準形は、完全グラフ不変量の一例です。同型なグラフはすべて同じ標準形を持ち、同型でないグラフはすべて異なる標準形を持ちます。^{[ 1 ] [ 2 ]}逆に、グラフのすべての完全不変量を使用して標準形を構築できます。^{[ 3 ]} n頂点グラフの頂点集合は1 からnまでの整数と同一視でき、このような同一視を使用して、グラフの標準形をその頂点の順列として記述することもできます。グラフの標準形は、標準ラベル付けとも呼ばれ、^{[ 4 ]}グラフの標準化は、グラフの標準化とも呼ばれることがあります。

グラフ同型性問題は、2 つの有限グラフが同型であるかどうかを判定する計算問題です。明らかに、グラフ正規化問題は、少なくともグラフ同型性問題と同じくらい計算が困難です。実際、グラフ同型性問題は、AC ⁰還元可能で、グラフ正規化問題に帰着します。しかし、この 2 つの問題が多項式時間で等価であるかどうかは、まだ未解決の問題です。^{[ 2 ]}

2019年、ラースロー・ババイは、グラフ正規化のための準多項式時間アルゴリズム、すなわち実行時間が${\displaystyle 2^{O((\log n)^{c})}}$ある固定値に対して${\displaystyle c>0}$[ ^{5 ]}グラフ同型性に対する（決定論的）多項式時間アルゴリズムの存在は、計算複雑性理論において未解決の問題であるが^、 1977年にLászló Babaiは、少なくとも 1 − exp( − O( n )) の確率で、単純な頂点分類アルゴリズムが、すべてのn頂点グラフの集合から一様にランダムに選択されたグラフの正準ラベルを、わずか 2 つの改良ステップの後生成することを報告した。小さな修正と深さ優先探索ステップの追加により、このような一様に選択されたランダムグラフの正準ラベルが線形期待時間で生成される。この結果は、報告されている多くのグラフ同型性アルゴリズムが実際にうまく機能する理由についていくらか光を当てている。^{[ 6 ] [ 7 ]}これは確率的複雑性理論における重要なブレークスルーであり、原稿の形で広く知られるようになり、シンポジウムで報告されてから長い間「未発表原稿」として引用され続けた。  

よく知られている標準形は、同型クラス内の辞書式最小のグラフであり、これは、線形文字列とみなされる隣接行列が辞書式最小のクラスのグラフです。しかし、辞書式最小のグラフの計算はNP困難です。^{[ 8 ]}

木構造の場合、 O ( n )の空間を必要とする簡潔な多項式時間正規化アルゴリズムがRead(1972)によって提示されている。^{[ 9 ]}まず、各頂点に文字列01をラベル付けする。葉以外の各xについて、 xの先頭の0と末尾の1を繰り返し削除する。のラベル。次に、xをソートします。のラベルと、隣接するすべての葉のラベルを辞書式順序で連結します。これらのソートされたラベルを連結し、先頭に 0、末尾に 1 を追加して、これをxの新しいラベルとし、隣接する葉を削除します。頂点が 2 つ残っている場合は、それらのラベルを辞書式順序で連結します。

グラフの正規化は、多くのグラフ同型アルゴリズムの本質です。主要なツールの1つはNautyです。^{[ 10 ]}

グラフ正規化の一般的な応用例は、グラフィカルデータマイニング、特に化学データベースアプリケーションである。^{[ 11 ]}

SMILESやInChIなどの化学物質の識別子の多くは、計算に正規化ステップを使用しており、これは基本的に分子を表すグラフの正規化です。^{[ 12 ] [ 13 ] [ 14 ]}これらの識別子は、分子情報をエンコードするための標準的な（そして時には人間が読める）方法を提供し、データベースやウェブ上でそのような情報を検索しやすくするように設計されています。

• 標準形– 数学的対象の標準的な表現 
• 正規化– データを「標準」、「通常」、または正規形式に変換するプロセス