グラフの準同型について

Homomorphisms of Graphsを参考に理解する。

Homomorphisms of Graphsより準同型は写像fについて、演算◯が写像後も同じ関係を保てること

群$ Gにおいて、

$ x, y, z \in Gについて、 $ x◯y = zならば、$ f(x)◯f(y) = f(z)

が成り立つことを準同型という。

グラフでも同じように考えて、

$ G = (V_g, E_g)

$ u, v \in V_gについて、

辺$ uv \in E_gのとき

$ H = (V_h, E_h)

$ f: G \rightarrow Hが準同型とは

$ f(u), f(v) \in V_hについて、

辺$ f(u)f(v) \in E_hとなること

$ fが全単射かつ$ f^{-1}も準同型なら$ Gと$ Hは同型

（準同型は同型を緩めたもの）

完全グラフ：任意の2頂点に対して辺があること（全部の頂点に辺がある）

References