同相写像（グラフ理論）

グラフ理論では、2 つのグラフ とが同相であるとは、の何らかの区分から の何らかの区分へのグラフ同型が存在する場合をいう。グラフの辺をある頂点から別の頂点に引かれた線と考えると（通常、図に描かれるように）、2 つのグラフの図が位相的な意味で同相である場合に、2 つのグラフはグラフ理論的な意味で互いに同相である。^[1]${\displaystyle G}$${\displaystyle G'}$${\displaystyle G}$${\displaystyle G'}$

一般に、グラフGの細分化（展開^[2]と呼ばれることもある）は、 G内の辺の細分化から生じるグラフである。端点が { u、v } である辺eの細分化により、 1 つの新しい頂点wと、 e を2 つの新しい辺 { u、w  } と { w、v } に置き換えた辺集合を 含むグラフが得られる 。有向辺の場合、この操作により、その伝播方向が予約される。

たとえば、端点が { u、v } であるエッジeの場合 :

2 つの辺e ₁とe ₂に分割でき、それぞれ次数-2の新しい頂点wに接続します。つまり、有向辺の場合は 入次数-1、出次数-1 です。

グラフGとHに対して、HがGのサブグラフに同相であるかどうかを判断することはNP完全問題である。 ^[3]

逆の操作、つまり 頂点w を wに接する 2 つの辺 ( e ₁、e ₂ )に関して平滑化する操作では、 w を含む両方の辺が削除され、 ( e ₁、e ₂ ) が、その対の他の端点を接続する新しい辺に置き換えられます。ここで強調したいのは、次数-2 (つまり、2 価) の頂点だけが平滑化できるということです。この操作の限界は、次数-2 の頂点がなくなるグラフによって実現されます。

たとえば、2 つのエッジe ₁ { u , w  } とe ₂ { w , v } を持つ単純な接続グラフ :

頂点（つまりw）があり、これを滑らかにすると次のようになります。

重心細分化は、グラフの各辺を細分化します。これは特別な細分化で、常に二部グラフになります。この手順は繰り返すことができ、n^{番目の重心細分化はグラフの}n −1番目の重心細分化の重心細分化になります。2 番目のこのような細分化は常に単純なグラフになります。

グラフを細分化しても平面性は保たれることは明らかである。 クラトフスキーの定理によれば、

有限グラフが平面グラフであるためには、 K 5 ₍ 5つの頂点を持つ完全グラフ) またはK _3,3 ( 6 つの頂点を持つ完全二部グラフで 、そのうち 3 つは他の 3 つの頂点とそれぞれ接続されている) に同相な部分グラフが含まれない必要があります。

実際、K ₅またはK _{3,3に同相なグラフは}クラトフスキー部分グラフと呼ばれます。

ロバートソン・シーモア定理に従う一般化は、各整数 gに対して、グラフの有限障害集合が存在し、グラフH が種数gの曲面に埋め込み可能であることと、Hが のいずれの同相コピーも含まないことが前提となることを主張します。たとえば、はクラトフスキー部分グラフで構成されます。 ${\displaystyle L(g)=\left\{G_{i}^{(g)}\right\}}$ ${\displaystyle G_{i}^{(g)\!}}$${\displaystyle L(0)=\left\{K_{5},K_{3,3}\right\}}$

次の例では、グラフGとグラフH は同相です。

G′がGの外側の辺の細分化によって作成されたグラフであり、H′ がHの内側の辺の細分化によって作成されたグラフである場合、G′とH′は同様のグラフ描画を持ちます。

したがって、 G'とH' の間には同型性が存在し、GとHは同相であることを意味します。

次の混合グラフは同相です。有向辺には中間矢印の先端があることが示されています。

• 副専攻（グラフ理論）
• エッジの収縮

• イエレン、ジェイ、グロス、ジョナサン L. (2005)、『グラフ理論とその応用』、『離散数学とその応用 (第 2 版)』、チャップマン & ホール/CRC、ISBN 978-1-58488-505-4