📂グラフ理論

グラフのホモーモルフィズム

定義 ¹

二つのグラフ$G_{1}$と$G_{2}$が与えられたとする。$G_{1}$のある細分$G_{1} '$と$G_{2}$のある細分$G_{2} '$の間にグラフアイソモーフィズムが存在すれば、$G_{1}$と$G_{2}$はホメオモーフィック^homeomorphicであるという。

---

• グラフ$G$に次の条件を満たす頂点$w$を次々に加えたグラフを$G$の細分^subdivision$G'$という。 $$\begin{align*} u \sim_{G} v & \implies \begin{cases} u \nsim_{G'} v \\ u \sim_{G'} w \\ w \sim_{G'} v \\ \deg w = 2 \end{cases} \end{align*}$$
• $x \sim_{A} y$はグラフ$A$で二つの頂点$x,y$が隣接していることを意味する。

説明

簡単に言うと、元のグラフで繋がっていたエッジを切ってその間に$w$が加わったグラフのことを言う。下の図を見ると理解しやすい。

右にある二つのグラフは、左に与えられたグラフ$G$の細分の二つの例を示している。加える頂点は必ずしも一つである必要はなく、同時に一つのエッジに入れても良い。

次はホメオモーフィックな二つのグラフの例である。

このような細分をよく見ると、頂点を加えても元のグラフで真っ直ぐ通っていた接続関係は変わらなかったことが確認できる。この概念を使えば、次のように二つのグラフが実質的に同じであるという話ができる。グラフホメオモーフィズムは、正確には構造的な同一性に関するグラフアイソモーフィズムとは異なり、実質的に空間的な同一性を扱い、その言葉自体も位相数学のホメオモーフィズムから来ている。

参照

• 位相数学でのホメオモーフィズム
• グラフアイソモーフィズム