📂グラフ理論

グラフの同型写像

定義 ¹

二つのグラフ $G_{1}$ と $G_{2}$ が与えられているとする。$V(G_{1})$ と $V(G_{2})$ の間には全単射が存在し、$G_{1}$ の頂点間のエッジの数とそれに対応する $G_{2}$ の頂点間のエッジの数が一致する場合、その全単射を同型写像と言い、二つのグラフは同型であるという。つまり、以下を満たす全単射 $\phi : G_{1} \to G_{2}$ を同型写像と呼ぶ。 $$ u \sim_{1} v \iff \phi (u) \sim_{2} \phi (v) $$

例

例えば、以下の二つのグラフを見てみよう：

厳密に言えば、この二つのグラフは同じではない。もちろん、グラフを区別する際に外見は重要ではない。しかし、それを除いても、頂点の集合とエッジの集合が異なるので異なる。だが、次のような一対一の対応関係を示せば、二つのグラフは実質的に同じと考えることができる： $$ A \to x \\ B \to y \\ C \to z \\ D \to u \\ E \to v \\ F \to w $$

参照

• 抽象代数学における同型写像
• グラフのホメオモーフィズム