グラフ同型
グラフ同型(グラフどうけい、英: graph isomorphism)
ループや多重辺を含まないものは単純グラフ
グラフ同型の条件
グラフ$ G=(V_G, E_G) 、$ H = (V_H, E_H) があるとする (C1) 頂点集合が対応する
頂点$ V_G 、$ V_H が1対1対応(全単射)となる写像$ f がある。このとき$ f : V(G) \to V(H) 頂点の数$ n が$ G, H で等しい
(C2) 辺の対応が保たれる
グラフ$ G の辺がグラフ$ H のすべての辺に1対1対応する
辺の数が同じで、対応する辺も同じ
(同型写像の条件には全単射であることが含まれている) 数学的には全単射写像$ f と言えるならグラフ同型であるといえる。 グラフ同型判定の計算量は擬似多項式時間(quasi-polynomial time)で$ \exp(O(\log n)^{O(1)} かかるらしい 定義(工事中)
頂点集合$ V(G), V(H) 、辺集合$ E=\{(v, w) | v,w \in E\}
写像$ f : V(G) \to V(H)
例
$ V(G) := \{ 1, 2, 3 \} 、$ E(G) := \{\{1, 2 \}, \{2, 3 \},\{3, 1 \} \}
$ V(H) := \{ a, b, c \} 、$ E(G) := \{\{a, b \}, \{b, c \},\{c, a \} \}
写像$ f が以下のように定義できる。
$ f(1) = a
$ f(2) = b
$ f(3) = c
グラフ$ G, H の頂点が対応していて、辺も対応、本数が同じとなって構造的に同じといえるのでグラフ同型となる。
確認用
Q. グラフ同型
関連
参考
メモ