Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 232 C 問題Graph Isomorphism

AtCoder ABC ABC232 C問題 300 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

[\![N]\!]:=\{1,2, \dots, N\} とする. N 頂点 M 頂点の単純無向グラフ G,H は同型か? ただし,

  • G=([\![N]\!], E), \quad E=\{A_i B_i \mid 1 \leq i \leq M\}
  • H=([\![N]\!], F), \quad F=\{C_j D_j \mid 1 \leq j \leq M\}

とする.

制約

  • 1 \leq N \leq 8
  • 1 \leq M \leq \dfrac{1}{2} N(N-1)
  • グラフ G,H は単純無向グラフ

解法

一般的に, グラフ G=(V,E),H=(W,F) が同型であるとは, 以下を満たす写像 \varphi: V \to W が存在することである.

ここで, [\![N]\!] から [\![N]\!] への全単射の数は N! 通りである. 1つの全単射 \varphi: [\![N]\!] \to [\![N]\!] を固定するごとに, その全単射が同型写像になるかどうかの判定は O(N^2) でできる. よって, 全ての全単射を見ることにより, 計算量 O(N^2 N!) で判定できる.