グラフの同型性判定

説明 二つのグラフ g, h に対して同型すなわち頂点の置換 p であって (u,v) ∈ E(g) iff (p[u], p[v]) ∈ E(h) なるものが存在するかどうかを判定する． 今のところこの問題は NP 完全かどうかすらわかっていない（多くの人は NP 完全ではないが P でもないと信じていると思う）．しかしバックトラックによる枝刈り付の全探索が多くの場合うまくいくことが実験によって分かっており，ランダムグラフに対しては O(V log V) で動くことも知られている． 以下の実装は次のアルゴリズムによる． g, h の頂点を次数の小さい順にソートする． 同じ次数のものに対して頂点を対応させてみる． それまでに対応を作った部分と整合性を確かめる． 整合していれば再帰的にチェックする． 計算量 最悪 O(V!)．しかしランダムグラフを入力とした実験によると，V = 1000 く