グラフの同型性判定

説明

二つのグラフ 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 くらいでも一瞬で終わる(隣接行列表示している分 O(V^2) の壁は破れないので，これはそんなに悪い結果ではない)．

使い方

具体的な置換は p: gs[i].index → hs[i].index で与えられる．

ソースコード

typedef vector< vector<int> > Matrix;

typedef pair<int, int> VertexInfo;
#define index second
#define degree first
bool permTest(int k, const Matrix &g, const Matrix &h,
    vector<VertexInfo> &gs, vector<VertexInfo> &hs) {
  const int n = g.size();
  if (k >= n) return true;
  for (int i = k; i < n && hs[i].degree == gs[k].degree; ++i) {
    swap(hs[i], hs[k]);
    int u = gs[k].index, v = hs[k].index;
    for (int j = 0; j <= k; ++j) {
      if (g[u][gs[j].index] != h[v][hs[j].index]) goto esc;
      if (g[gs[j].index][u] != h[hs[j].index][v]) goto esc;
    }
    if (permTest(k+1, g, h, gs, hs)) return true;
esc:swap(hs[i], hs[k]);
  }
  return false;
}
bool isomorphism(const Matrix &g, const Matrix &h) {
  const int n = g.size();
  if (h.size() != n) return false;
  vector<VertexInfo> gs(n), hs(n);
  REP(i, n) {
    gs[i].index = hs[i].index = i;
    REP(j, n) {
      gs[i].degree += g[i][j];
      hs[j].degree += h[i][j];
    }
  }
  sort(ALL(gs)); sort(ALL(hs));
  REP(i, n) if (gs[i].degree != hs[i].degree) return false;

  return permTest(0, g, h, gs, hs);
}

Verified