グラフホモロジー

代数的位相幾何学とグラフ理論において、グラフホモロジーはグラフのホモロジー群を記述するものであり、グラフは位相空間として考えられている。グラフ内の「穴」の数の概念を形式化する。グラフは単体ホモロジーの特殊なケースであり、グラフは単体複体の特殊なケースである。有限グラフは 1 複体 (つまり、その「面」は頂点 - 0 次元、辺 - 1 次元) であるため、非自明なホモロジー群は 0 番目グループと 1 番目グループのみである。^[1]

位相空間Xの 1 番目のホモロジー群の一般式は次のとおりです。以下の例では、これらの記号と概念をグラフ上で詳しく説明します。 $${\displaystyle H_{1}(X):=\ker \partial _{1}{\big }}\operatorname {im} \partial _{2}}$$

X を3 つの頂点 {x,y,z} と 4 つの辺 {a: x→y, b: y→z, c: z→x, d: z→x}を持つ有向グラフとします。このグラフにはいくつかのサイクルがあります。

• 1 つのサイクルはループ a+b+c で表されます。ここで、プラス記号はすべてのエッジが同じ方向に移動するという事実を表します。加算演算は可換であるため、+ 記号はループ a+b+c、b+c+a、c+a+b がすべて同じサイクルを表すという事実を表します。
• 2 番目のサイクルはループ a+b+d で表されます。
• 3 番目のサイクルはループ c−d で表されます。ここで、マイナス記号は、エッジ d が逆方向に移動することを表します。

平面をループ a+b+d に沿って切断し、次に c で切断して d で「接着」すると、ループ a+b+c に沿った切断が得られます。これは、次の関係で表すことができます: (a+b+d) + (cd) = (a+b+c)。この関係を正式に定義するために、次の可換群を定義します: ^{[2] : 6:00}

• C _{0 は}頂点集合 {x,y,z} によって生成される自由アーベル群です。C 0 の各要素は0次元連鎖_と呼ばれます。
• C _{1 は}、有向辺の集合 {a,b,c,d} によって生成される自由アーベル群です。C _{1の各要素は}1 次元連鎖と呼ばれます。 上記の 3 つのサイクルは 1 次元連鎖であり、実際、群C ₁では関係 (a+b+d) + (cd) = (a+b+c) が成り立ちます。

C ₁のほとんどの要素はサイクルではありません。たとえば、a+b、2a+5b-c などはサイクルではありません。サイクルを正式に定義するには、まず境界 を定義します。エッジの境界は演算子 で示され、そのターゲットからソースを引いたものとして定義されるため、SoはグループC ₁からグループC _{0へのマッピングです。a、b、c、d は}C ₁の生成元であるため、これは自然にC ₁からC ₀へのグループ準同型に拡張されます。この準同型では、です。同様に、はC ₁の任意のサイクルをC ₀のゼロ元にマッピングします。言い換えると、 C ₁のサイクルの集合はのヌル空間 (カーネル)を生成します。この場合、 のカーネルには2 つのジェネレータがあります。1 つは a+b+c に対応し、もう 1 つは a+b+d に対応します (3 番目のサイクル cd は最初の 2 つの線形結合です⁾。 ${\displaystyle \partial_{1}}$${\displaystyle \partial _{1}(a)=yx,~\partial _{1}(b)=zy,~\partial _{1}(c)=\partial _{1}(d)=xz.}$${\displaystyle \partial_{1}}$${\displaystyle \partial_{1}}$${\displaystyle \partial _{1}(a+b+c)=\partial _{1}(a)+\partial _{1}(b)+\partial _{1}(c)=(yx)+(zy)+(xz)=0}$${\displaystyle \partial_{1}}$ ${\displaystyle \partial_{1}}$${\displaystyle \partial_{1}}$${\displaystyle \ker \partial _{1}}$

一般的な位相空間では、より高次元の連鎖を定義します。特に、C _{2 は}2 次元オブジェクトのセット上の自由アーベル群になります。ただし、グラフにはそのようなオブジェクトがないため、C ₂は自明なグループです。したがって、2 番目の境界演算子の像 も自明です。したがって、これは、グラフに 2 つの「穴」があるという直感的な事実に対応します。指数は穴の数です。 ${\displaystyle \partial_{2}}$$${\displaystyle H_{1}(X)=\ker \partial _{1}{\big }}\operatorname {im} \partial _{2}\cong \mathbb {Z} ^{2}/\mathbb {Z} ^{0}=\mathbb {Z} ^{2}}$$

上記の例は、任意の連結グラフ G = ( V , E ) に一般化できます。T をGの全域木とします。 E \ Tのすべての辺はサイクルに対応します。これらはまさに線形独立サイクルです。したがって、グラフの最初のホモロジー群H ₁は、 | E \ T | 個の生成元を持つ自由アーベル群です。この数は | E |-| V |+1 に等しいため、次のようになります。^[1]切断されたグラフで、C が連結成分の集合である場合、同様の計算により次のことが示されます。特に、最初のグループが自明なのは、Xがフォレストである場合のみです。 $${\displaystyle H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+1}.}$$$${\displaystyle H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+|C|}.}$$

位相空間Xの 0 次ホモロジー群の一般式は次の通りである。$${\displaystyle H_{0}(X):=\ker \partial _{0}{\big /}\operatorname {im} \partial _{1}}$$

3つの頂点{x,y,z}と4つの辺{a: x→y, b: y→z, c: z→x, d: z→x}を持つグラフに戻ります。群C ₀は頂点の集合によって生成されることを思い出してください。(−1)次元の要素がないので、群C ₋₁は自明であり、したがって群C ₀全体は対応する境界演算子の核です: = {x,y,z}によって生成される自由アーベル群。^[3]${\displaystyle \ker \partial _{0}=C_{0}}$

の像には、辺の境界である頂点の各ペアの元が含まれます。つまり、差 {y−x, z−y, x−z} によって生成されます。商群を計算するには、 のすべての元を 「ゼロに等しい」と考えると便利です。つまり、 x、y、z は等価であり、商の同じ同値類にあるということです。言い換えると、は単一の元によって生成されます (どの頂点でも生成できます)。したがって、Zと同型です。 ${\displaystyle \partial _{1}}$${\displaystyle \operatorname {im} \partial _{1}}$${\displaystyle H_{0}(X)}$

上記の例は、任意の連結グラフに一般化できます。任意の頂点から始めて、辺に対応する 1 つ以上の式を追加することで、他の任意の頂点に到達できます (たとえば、 x から始めて、 yx と zy を追加することで z に到達できます)。 の要素はすべて 0 に等しいため、グラフのすべての頂点は単一の同値類に属し、したがってZと同型であることを意味します。 ${\displaystyle \operatorname {im} \partial _{1}}$${\displaystyle H_{0}(X)}$

一般に、グラフには複数の連結成分があります。成分の集合を C とします。すると、連結成分はすべて商群の同値類になります。したがって、各成分から 1 つずつ、任意の | C | 組の頂点 によって生成できます。$${\displaystyle H_{0}(X)\cong \mathbb {Z} ^{|C|}.}$$

多くの場合、連結グラフの 0 次ホモロジーは自明であると仮定すると便利です (つまり、グラフに 1 つの点が含まれている場合、そのすべてのホモロジーは自明です)。これにより、縮小ホモロジーの定義が導かれます。グラフの場合、縮小 0 次ホモロジーは次のようになります。この「縮小」は 0 次ホモロジーにのみ影響します。高次元の縮小ホモロジーは、標準ホモロジーと同じです。 $${\displaystyle {\tilde {H_{0}}}(X)\cong \mathbb {Z} ^{|C|-1}.}$$

グラフには頂点（0 次元要素）と辺（1 次元要素）のみが含まれます。高次元の要素を追加することで、グラフを抽象的な単体複体に一般化できます。すると、グラフホモロジーの概念は単体ホモロジーの概念によって一般化されます。

上記のグラフの例には、エッジ c と d で囲まれた 2 次元の「セル」を追加できます。これを A と呼び、時計回りに向いていると仮定します。C 2 を、2 次元セルのセットによって生成される自由アーベル群として定義します。_この場合は、シングルトン {A} です。C ₂の各要素は、2 次元チェーンと呼ばれます。

C _1からC ₀への境界演算子を と表記するのと同様に、 C _2からC ₁への境界演算子を と表記します。特に、2 次元セル A の境界は 1 次元のエッジ c と d であり、c は「正しい」方向にあり、d は「逆の」方向にあります。したがって、次のようになります。チェーンと境界演算子のシーケンスは、次のように表すことができます。^[4] 2 次元セル A を追加すると、その境界 cd はもはやホールを表しません (単一の点に同型です)。したがって、「ホール」のグループには単一のジェネレータ、つまり a+b+c が含まれます (a+b+d に同型です)。最初のホモロジー群は、商群として定義されます。ここで、は 1 次元サイクルの群で、Z ²と同型であり、 は2 次元セルの境界である 1 次元サイクルの群で、Zと同型です。したがって、それらの商H _{1 は}Zと同型です。これは、 X に1 つのホールがあることに対応します。以前は、 の像は自明な群であったため、商は に等しかったです。ここで、 となるように、エッジ c と d の間に別の有向 2 次元セル B を追加するとします。これで、C _{2 は{A,B} によって生成される}自由アーベル群になります。これによってH _{1 が}変化することはなく、依然としてZと同型です(X には依然として 1 つの 1 次元ホールがあります)。しかし、今ではC ₂には2 次元サイクル AB が含まれているため、非自明な核があります。このサイクルは、2 次元の穴が 1 つあるという事実に対応する 2 番目のホモロジー グループを生成します。3 セル、つまり A と B で囲まれた 3 次元の固体オブジェクト (C と呼びます) を追加できます。C _{3 を}、{C} と境界演算子によって生成される自由アーベル群として定義します。 C を となるように配置できます。C の境界はC ₂のサイクルであることに注意してください。これで、2 番目のホモロジー グループは次のようになります。2 次元の穴がないという事実に対応します (C は A と B の間の穴を「埋めます」)。 ${\displaystyle \partial _{1}}$${\displaystyle \partial _{2}}$${\displaystyle \partial _{2}(A)=c-d}$ $${\displaystyle C_{2}\xrightarrow {\partial _{2}} C_{1}\xrightarrow {\partial _{1}} C_{0}}$$$${\displaystyle H_{1}(X):=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}}$$${\displaystyle \ker \partial _{1}}$${\displaystyle \operatorname {im} \partial _{2}}$${\displaystyle \partial _{2}}$${\displaystyle \ker \partial _{1}}$${\displaystyle \partial _{2}(B)=\partial _{2}(A)=c-d}$${\displaystyle \partial _{2}}$$${\displaystyle H_{2}(X):=\ker \partial _{2}\cong \mathbb {Z} }$$${\displaystyle \partial _{3}:C_{3}\to C_{2}}$${\displaystyle \partial _{3}(C)=A-B}$$${\displaystyle H_{2}(X):=\ker \partial _{2}{\big /}\operatorname {im} \partial _{3}\cong {0}}$$

一般に、任意の次元の連鎖を定義できます。連鎖の最大次元がkの場合、次のグループのシーケンスが得られます。 ( k +1) 次元セルの任意の境界はk次元サイクルであることが証明できます。言い換えると、任意のkについて、 ( k +1 個の要素の境界のグループ) は ( k次元サイクルのグループ)に含まれています。したがって、商は明確に定義され、 k番目のホモロジー グループとして定義されます。$${\displaystyle C_{k}\xrightarrow {\partial _{k}} C_{k-1}\cdots C_{1}\xrightarrow {\partial _{1}} C_{0}}$$${\displaystyle \operatorname {im} \partial _{k+1}}$${\displaystyle \ker \partial _{k}}$${\displaystyle \ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}}$$${\displaystyle H_{k}(X):=\ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}}$$