ホモロジ群の計算〜グラフver

サイトのTOP→理系インデックス





定義 ( アーベル群 )

G を群とする。

a、b∈G が ab=ba を満たすとき、「 a と b は可換である 」 という。

任意の a、b∈G が可換であるとき、G を 『 アーベル群 』 という。

アーベル群を 『 可換群 』 と呼ぶことも多い。

とくに、アーベル群の積 ab を a+b と表すとき、これを 『 加群 』 または 『 加法群 』 という。

参考 ( 群の作用 )

G を群とし、X を集合とする。

任意の g∈G、x∈X に対し、gx∈X が一意に定まるとする。

次が成り立つとする。

(1) 任意の g、h∈G、x∈X に対し、(gh)x=g(hx) である。

(2) 任意の x∈X に対し、1x=x である。

このとき、「 G は X に作用する 」 という。

参考 ( 左R加群 )

R を単位元をもつ環とする。

M を空でない集合とする。

M は加法群であるとする。

M には R の左からの作用 ax∈M (a∈R、x∈M)が定義されているとする。

R の左からの作用は次を満たすとする。

(1) a(x+y)=ax+ay、(a+b)x=ax+bx

(2) (ab)x=a(bx)

(3) 1x=x

このとき、M を 『 左R加群 』 という。

これを略して、単に 『 R加群 』 という。

また、R の元を 『 スカラー 』 という。

注意 ( Z加群 )

G を加群とする。

a∈G とおく。

いま、a+a+a∈G を考えることができる。

これは自然に 3a∈G と表せる。

同様に、−2a∈G を考えることもできる。

つまり、加群は自然に 加群と見なせる。

もしかしたら、

加群の意味がよく分からない 」

・・・という人がいるかもしれない。

しかし、そこはそれほど気にしなくてよい。

要は、加群に対して、整数によるスカラー倍が自然に定義されることが分かればよい。

定義 ( 部分 Z 加群 )

G を 加群とする。

I を G の部分集合とする。

次が成り立つとする。

(1) 任意の α、β∈I に対し、α+β∈I である。

(2) 任意の α∈I、c∈ に対し、cα∈I である。

このとき、I を 『 G の部分 加群 』 という。

定義 ( 準同型写像〜その1 )

、G を加群とする。

f:G→G を写像とする。

次が成り立つとする。

(*) f(x+y)=f(x)+f(y)

このとき、f を 『 (加群の)準同型写像 』 という。

定義 ( 準同型写像〜その2 )

、G を R 加群とする。

f:G→G を写像とする。

次が成り立つとする。

(1) f(x+y)=f(x)+f(y)

(2) f(cx)=cf(x) ( c∈R )

このとき、f を 『 R準同型写像 』 という。

明らかに、『 加群の準同型写像 』 は 『 加群の準同型写像 』 と見なせる。

定義 ( 商加群 )

I を G の部分加群とする。

α、β∈G に対し、α−β∈I であるとき、α〜βと表す。

明らかに、〜 は同値関係である。

そこで、〜による同値類全体を G/I と表す。

また、αが属する同値類を [α] と表す。

次のように演算を定義する。

(1) [α]+[β]=[α+β]

(2) c[α]=[cα] ( c∈

このとき、G/I を 『 商加群 』 という。

つまり、α、β∈I ⇔ [α]=[β] である。

上記の演算(1)と(2)が well-defined であることを確認する必要がある。

しかし、ここでは省略する。

定義 ( 自由加群 )

S={ s、・・・、s } を集合とする。

(S)={ a+・・・+a|a、s∈S } と定義する。

このとき、(S) を 『 Sによって生成される自由加群 』 という。

明らかに、(S) は自然に加群と見なせる。

まず、a+・・・+a、b+・・・+b(S) とおく。

いま、S は単なる集合であるから、上記の元に演算は定まっていない。

そこで、新しく演算 (a+b)s+・・・+(a+b)s(S) を定義する。

また、単位元は 0s+・・・+0s(S) である。

また、a+・・・+a(S) の逆元は (−a)s+・・・+(−a)s(S) である。

P1 ( f は単射 ⇔ Kerf={0} )

f:G→G を加群の準同型とする。

このとき、次は同値である。

(1) f は単射である。

(2) Kerf={0}

証明

(1)を仮定する。

α∈Kerf とおく。

いま、f(α)=0 である。

また、f(0)=0 である。

よって、仮定(1)より、α=0 である。

−−−−−−−−−−−−−−−−−−−−

(2)を仮定する。

f(α)=f(α) と仮定する。

式変形すると、f(α)−f(α)=0 である。

さらに、f(α−α)=0 である。

よって、α−α∈Kerf である。

よって、α−α=0 である。

よって、α=α である。

P2 ( 準同型写像は自由加群を保存する )

f:(S)→(T) を自由 加群の準同型とする。

S={ e、・・・、e } とおく。

このとき、Imf=(f(e)、・・・、f(e)) である。

証明

x∈Imf とおく。

いま、x=f(a) とおく。( a∈(S) )

また、a=a+・・・+a と表せる。

よって、f(a)=f(a+・・・+a)=af(e)+・・・+af(e)∈(f(e)、・・・、f(e)) である。

以上により、Imf⊂(f(e)、・・・、f(e)) である。

−−−−−−−−−−−−−−−−−−−−

x∈(f(e)、・・・、f(e)) とおく。

いま、x=af(e)+・・・+af(e) と表せる。

よって、x=f(a+・・・+a)∈Imf である。

以上により、(f(e)、・・・、f(e))⊂Imf である。

P3 ( 商加群の基本的性質 )

G/I を商加群とする。

このとき、次が成り立つ。

(1) [α]+[β]=[α+β]

(2) c[α]=[cα] ( c∈

(3) α∈O ⇔ [α]=[0]

補足

ただし、O は {0} を意味する。

証明

(1)と(2)は定義そのままである。

(3)も明らかである。

定義 ( 複体 )

、・・・、C を加群とする。

次の列を考える。



ただし、∂n+1、・・・、∂ は準同型である。

また、O は {0} を意味する。

さらに、∂*∂i+1=0 ( i=0、・・・、n ) が成り立つとする。

このとき、上記の列を 『 複体 』 という。

むろん、∂n+1 は零写像である。

よって、∂*∂n+1 は、準同型という仮定のみで零写像となる。

むろん、∂ は零写像である。

よって、∂*∂ は、何も仮定しなくても零写像となる。

定義 ( 複体のホモロジ群 )

次の列を複体とする。



=ker∂ と定義する。( つまり Z⊂C

=Im∂i+1 と定義する。( つまり B⊂C

このとき、B は Z の部分 加群である。(★)

そこで、H=Z/B と定義する。

このとき、H を 『 i 次元のホモロジ群 』 という。

(★)の証明

いま、C は加群である。

よって、C 加群と見なすことができる。

まず、Z と B が C の部分 加群であることを示す。

−−−−−−−−−−−−−−−−−−−−

α、β∈Z とおく。

いま、∂(α+β)=∂α+∂β=0+0=0 である。

よって、α+β∈Z である。

以上により、α、β∈Z ⇒ α+β∈Z である。(★1)

α∈Z、c∈ とおく。

いま、∂(cα)=c∂α=c・0=0 である。

よって、cα∈Z である。

以上により、α∈Z ⇒ cα∈Z である。(★2)

(★1)、(★2)より、Z は C の部分 加群である。

−−−−−−−−−−−−−−−−−−−−

α、β∈B とおく。

いま、ある v、w∈Ci+1 が存在して、∂i+1(v)=α、∂i+1(w)=β となる。

また、∂i+1(v+w)=α+β である。

v+w∈Ci+1 であるから、上では α+β∈B を意味する。

以上により、α、β∈B ⇒ α+β∈B である。(★3)

α∈B とおく。

いま、ある v∈Ci+1 が存在して、∂i+1(v)=α となる。

また、∂i+1(cv)=c∂i+1(v)=cα である。

cv∈Ci+1 であるから、上式は cα∈B を意味する。

以上により、α∈B ⇒ cα∈B である。(★4)

(★3)、(★4)より、B は C の部分 加群である。

−−−−−−−−−−−−−−−−−−−−

最後に、B が Z の部分 加群であることを意味する。

ただし、B と Z が C の部分 加群であることは既に示した。

よって、B が Z の部分集合であることを示せばよい。

α∈B とおく。

いま、ある v∈Ci+1 が存在して、∂i+1(v)=α である。

よって、∂(α)=∂*∂i+1(v)=0 である。(※定義:複体)

よって、α∈Z である。

以上により、B⊂Z である。

定義 ( グラフ )

V、E を集合とする。( V≠φとする )

写像 s:E→V、t:E→V が定まっているとする。

このとき、G=(V、E) と表す。

G を 『 (有向)グラフ 』 という。

上の定義は唐突であろう。

そこで、背景を説明する。

V は頂点 ( vertex ) の集合であり、E は辺 ( edge ) の集合であると考える。

また、辺の両端は頂点であるとする。

また、各辺には向きが定まっているとする。

各 e∈E に対し、その始点は s(e)∈V であり、終点は t(e)∈V である。

例えば、下図を考える。



このとき、s(e)=v、t(e)=v である。

定義 ( 鎖 )

G=(V、E) をグラフとする。

(G)=(V) と定義する。

(G)=(E) と定義する。

つまり、C(G) と C(G) は自由 加群である。

このとき、C(G) を 『 0-鎖群 』 という。

また、C(G) を 『 1-鎖群 』 という。

また、C(G) の元を 『 0-鎖 』 といい、C(G) を 『 0-鎖 』 という。

鎖を 『 チェイン 』 と呼ぶ本も多い。

つまり、C(G)={ x+・・・+x|x、v∈V } である。

また、C(G)={ x+・・・+x|x、e∈E } である。

定義 ( 境界準同型 )

G=(V、E) をグラフとする。

:C(G)→C(G) を ∂(e)=t(e)−s(e) で定義する。

このとき、∂ を 『 境界準同型 』 という。

むろん、∂(E)→(V)である。

上の定義では E の元に対してのみ ∂ の値を定めたように思えるかもしれない。

しかし、この定義だけで C(G) の任意の元に対して値を定めたことになる。

これを確認してみよう。

x∈C(G) とおく。

いま、x=x+・・・+x ( x、e∈E ) と表せる。

よって、

参考 ( ここまでの流れ )



ここまで、上図の 1〜3 を解説した。

このページでは 4 について解説する。

定義 ( グラフの単体複体 )

G=(V、E) をグラフとする。

(G) を 0-鎖群とする。

(G) を 1-鎖群とする。

:C(G)→C(G) を境界準同型とする。

:O→C(G)、∂:C(G)→O を準同型とする。

いま、∂、∂ は自動的に零写像となる。

よって、次は複体である。



このとき、この列を 『 グラフの単体複体 』 という。

この複体に対応する i 次元ホモロジ群を H(G) と表す。

P4

G=(V、E) をグラフとする。

このとき、次が成り立つ。

(1) H(G)=C(G)/Im∂

(2) H(G)=Z/O

(1)の証明

いま、H(G)=H/B である。(※定義:ホモロジ群)

また、Z=ker∂ である。

よって、Z=C(G) である。(※定義:グラフの単体複体)

また、B=Im∂ である。

よって、H(G)=C(G)/Im∂ である。

(2)の証明

いま、H(G)=Z/B である。(※定義:ホモロジ群)

また、B=Im∂ である。

よって、B=O である。(※定義:グラフの単体複体)

よって、H(G)=Z/O である。

P5

G を 加群とする。

このとき、G と G/O は同型である。

補足

よって、P4 において Z/O と Z は同型である。

証明

O は {0} を意味することに注意する。

明らかに、O は G の部分 加群である。

x、y∈G に対し、x−y∈O ⇔ x−y=0 ⇔ x=y である。

つまり、各同値類は 1 つの元からなる。

φ:G→G/O を φ(x)=[x] で定義する。

φ(x)=φ(y) とおく。

いま、[x]=[y] である。

よって、[x−y]=[0] である。(※P3)

よって、x−y∈O である。(※P3)

よって、x=y である。

以上により、φは単射である。

一方、明らかに、φは全射である。

また、φ(x+y)=[x+y]=[x]+[y]=φ(x)+φ(y) である。(※P3)

また、φ(cx)=[cx]=c[x]=cφ(x) である。(※P3)

よって、φは準同型である。

定義 ( グラフ上の道 )

G=(V、E) をグラフとする。

次が成り立つとする。

(*1) v、・・・、vn+1∈V

(*2) e、・・・、e∈E

(*3) v、vi+1 は e の両端である。( i=1、・・・、n )

このとき、Γ={ v、e、・・・、v、e、vn+1 } を 『 G 上の道 』 という。

例えば、下図のようなグラフを考える。



このとき、Γ={ v、e、v、e、v } は道である。

『 道の向き 』 と 『 辺の向き 』 が一致する必要はない。

定義 ( 閉じた道 )

G=(V、E) をグラフとする。

Γ を G の道とする。

s(Γ)=t(Γ) であるとする。

このとき、Γ を 『 閉じた道 』 という。

定義 ( グラフ上の道に対応する鎖 )

G=(V、E) をグラフとする。

Γ={ v、e、・・・、v、e、vn+1 } を G の道とする。

次のように定義する。



このとき、Γ を 『 Γに対応する 1-鎖 』 という。

P6 ( グラフ上の道に対応する鎖の境界=「終点−始点」 )

G=(V、E) をグラフとする。

Γ を G の道とする。

Γ を Γ に対応する鎖とする。

このとき、∂Γ=t(Γ)−s(Γ) である。

証明

Γ={ v、e、・・・、v、e、vn+1 } とおく。

いま、Γ1≦i≦nε(e)e である。

よって、∂Γ1≦i≦nε(e)∂(e)=1≦i≦nε(e)(t(e)−s(e)) である。

ε(e)=1 の場合、ε(e)(t(e)−s(e))=vi+1−v である。

ε(e)=−1 の場合、ε(e)(t(e)−s(e))=−(v−vi+1)=vi+1−v である。

よって、∂Γ1≦i≦n(vi+1−v)=vn+1−v=t(Γ)−s(Γ)である。

定義 ( 連結 )

G=(V、E) をグラフとする。

任意の頂点 v、v∈V に対し、ある道Γが存在して、v と v はΓの両端となるとする。

このとき、「 G は連結である 」 という。

定義 ( 部分グラフ )

G=(V、E)、G’=(V’、E’) をグラフとする。

V’⊂V、E’⊂E であるとする。

s:E’→V’、t:E’→V’ は G のものと一致するとする。

このとき、G’ を 『 G の部分グラフ 』 という。

定義 ( 連結成分 )

G’ を G の部分グラフとする。

次が成り立つとする。

(1) G’ は連結である。

(2) G’ は極大である。

このとき、G’ を 『 G の連結成分 』 という。

「 G’ が極大である 」 とは 「 連結な部分グラフ H が G’⊂H⊂G を満たすならば H=G’である 」 を意味する。

P7 ( 「0次ホモロジ群が同型」⇔「連結成分数が等しい」 )

グラフ G が r 個の連結成分をもつとする。

このとき、次が成り立つ。

(1) H(G) と □・・・□ ( r 個の直和 ) は同型である。

(2) H(G)={ a[v]+・・・+a[v] |v∈G、a } である。

(3) dimH(G)=r

補足

ただし、□・・・□={ (a、・・・、a)|a } である。

補足

r=1 の場合、(1)は連結なグラフのホモロジ群が と同型であることを意味する。

(1)と(2)の証明

まず、r=1 の場合について証明する。

v={ v、・・・、vn+1 } とおく。

いま、C(G)=(V)={ x+・・・+xn+1n+1|v、x } である。

、v∈V とおく。

いま、ある道 Γ が存在して、Γの両端は v と v である。

つまり、s(Γ)=v、t(Γ)=v としてよい。

いま、∂(Γ)=v−v である。(※P6)

また、∂(Γ)∈Im∂ である。

よって、v−v∈Im∂ である。

よって、[ v−v ]=[0] である。

よって、[v]=[v] である。

よって、[v]=・・・=[vn+1] である。(★)

−−−−−−−−−−−−−−−−−−−−

いま、H(G)=C(G)/Im∂ である。(※P4)

(G) の元は [ a+・・・+a ] の形をしている。

(★)より、[ a+・・・+a ]=(a+・・・+a)[v] である。

むろん、a+・・・+a である。

よって、H(G)={ k[v]|k∈ }=([v]) である。

明らかに、([v]) と は同型である。

つまり、H(G) と は同型である。

−−−−−−−−−−−−−−−−−−−−

r=2 の場合について示す。( r≧3 の場合も同様である )

、G を、G の2つの連結成分とする。

=(V、E)、G=(V、E) とおく。

:C(G)→C(G) を境界準同型とする。

( むろん、C(G)=(E)、C(G)=(V) である )

明らかに、∂(E))⊂(V) である。

そこで、∂ の定義域を (E) に制限すると、∂(E)→(V) である。

同様に、∂ の定義域を (E) に制限すると、∂(E)→(V) である。

−−−−−−−−−−−−−−−−−−−−

いま、H(G)=C(G)/Im∂ である。(※P4)

そこで、C(G) と Im∂ に注目する。

={ v、・・・、vn+1 }、V={ v’、・・・、v’n+1 } とおく。

={ e、・・・、e }、E={ e’、・・・、e’ } とおく。

いま、C(G) の任意の元は (a+・・・+an+1n+1)+(a’v’+・・・+a’n+1v’n+1) の形で表される。

また、任意の v、v∈V に対し、ある道 Γ が存在して、Γの両端は v と v となる。

よって、(★)と同様に、[v]=・・・=[vn+1] である。(★1)

同様に、[v’]=・・・=[v’n+1] である。(★2)

いま、C(G) の任意の元は (b+・・・+b)+(b’e’+・・・+b’e’) の形で表される。

(b+・・・+b) は v、・・・、vn+1 の関係式を与える。

(b’e’+・・・+b’e’) は v’、・・・、v’n+1 の関係式を与える。

つまり、v と v’ の関係式を与える Im∂ の元は存在しない。

よって、(★1)、(★2)より、H(G)={ a[v]+a’[v’] |a、a’∈ } である。

明らかに、H(G) は と同型である。

(3)の証明

(2)より明らかである。

P8 ( G が連結 ⇔ 0次ホモロジ群と は同型 )

G をグラフとする。

このとき、次は同値である。

(1) G は連結である。

(2) H(G) と は同型である。

証明

(1)⇒(2)は既に示した。

(2)⇒(1)を対偶で示す。

G は連結でないとする。

G は r 個の連結成分をもつとする。

いま、H(G) と □・・・□ ( r 個の直和 ) は同型である。

よって、H(G) と は同型ではない。

以上により、(2)⇒(1)が示された。

定義 ( オイラー数 )

G=(V、E) をグラフとする。

χ(G)=#V−#E と定義する。

このとき、χ(G) を 『 G のオイラー数 』 という。

ただし、#V は 『 頂点の個数 』 である。

また、#E は 『 辺の個数 』 である。

定義 ( ベッチ数 )

G=(V、E) をグラフとする。

dimH(G) を b(G) と表す。

dimH(G) を b(G) と表す。

を 『 0次ベッチ数 』 という。

を 『 1次ベッチ数 』 という。

定義 ( 辺の反転、辺の細分 )

ある辺 e について、e の向きだけを逆にしたグラフを考えることができる。

この操作を 『 辺の反転 』 という。

−−−−−−−−−−−−−−−−−−−−

ある辺 e について、辺の途中に点を追加して辺を2つに分けたグラフを考えることができる。

この操作を 『 辺の細分 』 という。

−−−−−−−−−−−−−−−−−−−−

2本の辺とつながっている点 v について、その点 v を除去して2本の辺を1本につなげたグラフを考えることができる。

この操作を 『 辺の細分の逆 』 という。

定義 ( グラフの同相 )

、G をグラフとする。

辺の反転、辺の細分、辺の細分の逆を行うことで、G を G へ変形できるとする。

このとき、「 G と G 同相である 」 という。

定義 ( レトラクション )

G=(V、E) をグラフとする。

e∈E を、両端が異なる頂点をもつ辺とする。

このような辺 e を除去し、両端の点を1つにする。

このような操作を 『 レトラクション 』 という。

図示すると、



一方、次のような辺 e に対してレトラクションを行うことはできない。

少し言い方を変えると、レトラクションとは 「 出っ張りをなくす操作 」 である。

例えば、

P9

G をグラフとする。

G にレトラクションを行うことで、「 頂点数=連結成分数 」 となる。

このようなグラフを 『 極小グラフ 』 という。

補足

極小グラフとしては下図のようなものが考えられる。

証明

明らかである。

P10

グラフ G にレトラクションを行い、グラフ G を得たとする。

このとき、次が成り立つ。

(1) H(G) と H(G) は同型である。

(2) H(G) と H(G) は同型である。

(1)の証明

明らかに、レトラクションによって連結成分数は不変である。

よって、H(G) と H(G) は同型である。(※P7)

(2)の証明

これの証明はかなり長くなるので省略する。

P11

G=(V、E) を極小グラフとする。

このとき、次が成り立つ。

(1) h(G)=#V

(2) h(G)=#E

(1)の証明

明らかである。(※P7(3))

(2)の証明

いま、G に属する辺の両端は同じ点である。

よって、E⊂Z(G) である。

また、Z(G) の元は Z(G)/O の元と見なせる。(※P5)

よって、Z(G) の元は H(G) の元と見なせる。(※P4)

よって、b(G)=dimH(G)=dimZ(G)=#E である。

P12

(1) 同相に対してオイラー数は不変である。

(2) レトラクションに対してオイラー数は不変である。

(3) χ(G)=dimH(G)−dimH(G)

(1)の証明

辺の反転に対し、#V と #E は不変である。

よって、#V−#E も不変である。

辺の細分に対し、#V は1増加し、#E も1増加する。

よって、#V−#E は不変である。

よって、同相に対してオイラー数は不変である。

(2)の証明

レトラクションを行うと、#V は1減少し、#E も1減少する。

よって、#V−#E は不変である。

(3)の証明

レトラクションによって G は極小グラフ G’=(V’、E’)に変形できる。(※P9)

いま、(2)より、χ(G)=χ(G’) である。

また、χ(G’)=#V’−#E’=b(G’)−b(G’)=b(G)−b(G) である。(※P11、P10)

P13

グラフ G を下図のようなものとする。



このとき、(b、b、b)=(2、1、0) である。

証明

まず、H(G)=C(G)/Im∂ を求める。

いま、Im∂(∂、∂)である。(※P2)

x∈Im∂ とおく。

いま、[x]=[0] である。

また、x=a(∂)+b(∂) と表せる。

また、∂=v−v、∂=v−v=0 である。

よって、x=a(v−v)である。

よって、[v−v]=[0] である。

よって、[v]=[v] である。

av+bv+cv∈Z とおく。

いま、[av+bv+cv]=a[v]+b[v]+c[v]=(a+b)[v]+c[v] である。

つまり、H(G)=([v]、[v]) である。

よって、b=dimH(G)=2 である。

−−−−−−−−−−−−−−−−−−−−

次に、H(G)=Z/O を求める。

x∈C とおく。

いま、x=ae+be ( a、b∈ ) と表せる。

よって、∂(x)=a(v−v)+b(v−v)=a(v−v)である。

x∈Z の場合について考える。

いま、∂(x)=0 である。

よって、a(v−v)=0 である。

よって、a=0 である。

一方、b は任意でよい。

つまり、x=be と表せる。

つまり、Z(G)={ be|b∈ } である。

よって、H(G)=Z(G)/O={ b[e]|b∈ }=([e]) である。

よって、b=dimH(G)=1 である。

一方、明らかに、b=0 である。

以上により、(b、b、b)=(2、1、0)である。