グラフのコホモロジーを簡単な場合に計算してみた

目的

グラフ$\Gamma$（に付随する位相空間）の, アーベル群$A$を係数とするコホモロジー群$H^i(\Gamma, A) \ (i=0,1)$を計算できるようになる.

予備知識

• アーベル群, その準同型, 核, 余核

グラフ

ここでのグラフとは, 有向有限グラフであり, 多重辺やループを許す.
もう少し抽象的に言うと, グラフ$\Gamma$とは辺の集合$E$と頂点の集合$V$という有限集合の組で, 次の性質を持つ:

• 各辺$e \in E$に対して, 始点$v_1(e)=x \in V$と終点$v_2(e)=y \in V$という2点が定まっている（$x=y$でもよい).

コホモロジー群（定義）

コチェイン複体

$A$をアーベル群とする.
グラフ$\Gamma$に対して,
$$C^0(\Gamma,A)=\bigoplus_{x \in V}A_x, \ C^1(\Gamma,A)=\bigoplus_{e \in E}A_e$$
とおく. ここで, $A_x=A, A_e=A$たちは$A$のコピーである.
各辺$e \in E$の始点$x$と終点$y$に対して, $f_{e,y}: A_y \to A_e$を恒等写像$\operatorname{id}_A$と定め, $f_{e,x}: A_x \to A_e$を$-\operatorname{id}_A$と定める.
$$\partial=\partial_{\Gamma, A}:=\sum f_{e,x} : C^0(\Gamma,A)\to C^1(\Gamma,A)$$
と定める. ここで, 和は全ての辺$e\in E$と, その始点（または終点）$x$を走る.

グラフのコホモロジー

前節の記号の下,
$$H^0(\Gamma, A)= \ker (\partial), \ H^1(\Gamma, A)= \operatorname{coker} (\partial)$$
と定義し, グラフ$\Gamma$の$A$係数の$0$（または$1$）次コホモロジー群とよぶことにする.

オイラー標数

$A$は体であるとし, $h^0,h^1$をコホモロジー群$H^0(\Gamma, A), H^1(\Gamma, A)$の$A$ベクトル空間としての次元とする.
$\chi(\Gamma)=h^0-h^1$をオイラー標数という.
このとき, $\chi=\# V - \#E$が成り立つ.

コホモロジー群（計算例）

$A=\mathbb{Q}$係数のコホモロジー群を計算してみる.
$\Gamma=(E,V)$をグラフとする.

例1

$E=\{ e_1, e_2\}$, $V=\{ v_1, v_2, v_3\}$で, $e_1 : v_1 \to v_2$(始点が$v_1$, 終点が$v_2$. 以下もこのように略記することにする), $e_2:v_2 \to v_3$とする.
$\partial : C^0(\Gamma,\mathbb{Q})=\mathbb{Q}^3 \to C^1(\Gamma,\mathbb{Q})=\mathbb{Q}^2$
の行列は$\begin{pmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \end{pmatrix}$で, rankは$2$なので,
$H^0(\Gamma,\mathbb{Q})=\mathbb{Q}, H^1(\Gamma,\mathbb{Q})=0$.

例2（三角形）

$E=\{ e_1, e_2, e_3 \}$, $V=\{ v_1, v_2, v_3\}$で, $e_1 : v_2 \to v_3$, $e_2:v_3 \to v_1$, $e_3 : v_1 \to v_2$とする.
$\partial : C^0(\Gamma,\mathbb{Q})=\mathbb{Q}^3 \to C^1(\Gamma,\mathbb{Q})=\mathbb{Q}^3$
の行列は$\begin{pmatrix} 0 & -1 & 1 \\ 1 & 0 & -1 \\ -1 & 1 & 0 \end{pmatrix}$で, rankは$2$なので,
$H^0(\Gamma,\mathbb{Q})=\mathbb{Q}, H^1(\Gamma,\mathbb{Q})=\mathbb{Q}$.

例3（ループ）

$E=\{ e_1, e_2\}$, $V=\{ v\}$で, $e_i : v \to v$とする.
$\partial : C^0(\Gamma,\mathbb{Q})=\mathbb{Q} \to C^1(\Gamma,\mathbb{Q})=\mathbb{Q}^2$
の行列は$\begin{pmatrix} 0 \\ 0 \end{pmatrix}$なので,
$H^0(\Gamma,\mathbb{Q})=\mathbb{Q}, H^1(\Gamma,\mathbb{Q})=\mathbb{Q}^2$.

例4（多重辺）

$E=\{ e_1, e_2, e_3 \}$, $V=\{ v_1, v_2 \}$で, $e_i : v_1 \to v_2 $とする.
$\partial : C^0(\Gamma,\mathbb{Q})=\mathbb{Q}^2 \to C^1(\Gamma,\mathbb{Q})=\mathbb{Q}^3$
の行列は$\begin{pmatrix} -1 & 1 \\ -1 & 1 \\ -1 & 1 \end{pmatrix}$なので,
$H^0(\Gamma,\mathbb{Q})=\mathbb{Q}, H^1(\Gamma,\mathbb{Q})=\mathbb{Q}^2$.

例5（完全グラフ$K_4$）

$E=\{ e_1, \dots, e_6 \}$, $V=\{ v_1, v_2,v_3, v_4 \}$で, $e_1 : v_1 \to v_2 $, $e_2 : v_1 \to v_3 $, $e_3 : v_1 \to v_4 $, $e_4 : v_2 \to v_3 $, $e_5 : v_2 \to v_4$, $e_6 : v_3 \to v_4$とする.
$\partial : C^0(\Gamma,\mathbb{Q})=\mathbb{Q}^4 \to C^1(\Gamma,\mathbb{Q})=\mathbb{Q}^6$
の行列は$\begin{pmatrix} -1 & 1 & 0& 0 \\ -1 & 0 & 1& 0 \\ -1 & 0 & 0& 1 \\ 0 & -1 & 1& 0 \\ 0 & -1 & 0& 1 \\ 0 & 0 & -1& 1 \\ \end{pmatrix}$でrankは$3$であるので,
$H^0(\Gamma,\mathbb{Q})=\mathbb{Q}, H^1(\Gamma,\mathbb{Q})=\mathbb{Q}^3$.

整数係数コホモロジー群（計算例）

前節の例1~5に対して, $A=\mathbb{Z}$係数のコホモロジー群を計算してみる.
それには, 上で与えた行列の Smith normal form を計算すればよい.

例1

$\partial : C^0(\Gamma,\mathbb{Z})=\mathbb{Z}^3 \to C^1(\Gamma,\mathbb{Z})=\mathbb{Z}^2$
の行列のSmith normal formは$\begin{pmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \end{pmatrix}\to\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$より,
$H^0(\Gamma,\mathbb{Z})=\mathbb{Z}, H^1(\Gamma,\mathbb{Z})=0$.

例2（三角形）

$\partial : C^0(\Gamma,\mathbb{Z})=\mathbb{Z}^3 \to C^1(\Gamma,\mathbb{Z})=\mathbb{Z}^3$
の行列のSmith normal formは$\begin{pmatrix} 0 & -1 & 1 \\ 1 & 0 & -1 \\ -1 & 1 & 0 \end{pmatrix} \to \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} $より
$H^0(\Gamma,\mathbb{Z})=\mathbb{Z}, H^1(\Gamma,\mathbb{Z})=\mathbb{Z}$.

例3（ループ）

$\partial : C^0(\Gamma,\mathbb{Z})=\mathbb{Z} \to C^1(\Gamma,\mathbb{Z})=\mathbb{Z}^2$
の行列のSmith normal formは$\begin{pmatrix} 0 \\ 0 \end{pmatrix}$なので,
$H^0(\Gamma,\mathbb{Z})=\mathbb{Z}, H^1(\Gamma,\mathbb{Z})=\mathbb{Z}^2$.

例4（多重辺）

$\partial : C^0(\Gamma,\mathbb{Z})=\mathbb{Z}^2 \to C^1(\Gamma,\mathbb{Z})=\mathbb{Z}^3$
の行列のSmith normal formは$\begin{pmatrix} -1 & 1 \\ -1 & 1 \\ -1 & 1 \end{pmatrix}\to \begin{pmatrix} 1 & 0 \\ 0 & 0 \\ 0 & 0 \end{pmatrix}$なので,
$H^0(\Gamma,\mathbb{Z})=\mathbb{Z}, H^1(\Gamma,\mathbb{Z})=\mathbb{Z}^2$.

例5（完全グラフ$K_4$）

$\partial : C^0(\Gamma,\mathbb{Z})=\mathbb{Z}^4 \to C^1(\Gamma,\mathbb{Z})=\mathbb{Z}^6$
の行列のSmith normal formは$\begin{pmatrix} -1 & 1 & 0& 0 \\ -1 & 0 & 1& 0 \\ -1 & 0 & 0& 1 \\ 0 & -1 & 1& 0 \\ 0 & -1 & 0& 1 \\ 0 & 0 & -1& 1 \\ \end{pmatrix} \to \begin{pmatrix} 1 & 0 & 0& 0 \\ 0 & 1 & 0& 0 \\ 0 & 0 & 1& 0 \\ 0 & 0 & 0& 0 \\ 0 & 0 & 0& 0 \\ 0 & 0 & 0& 0 \\ \end{pmatrix}$なので,
$H^0(\Gamma,\mathbb{Z})=\mathbb{Z}, H^1(\Gamma,\mathbb{Z})=\mathbb{Z}^3$.