グラフ理論#1「閉路・切断・全域木」

$v \in B_G^1(E(C)) ⇔ v \in \sum_{e \in E(C)}e ⇔ v \in e となるeがE(C)に奇数個ある$

$v \in V(C)$の場合は$v \in e$となる$e \in E(C)$は丁度2つある。
$v \not\in V(C)$の場合は0。

よって、$B_G^1(E(C))=0$
ゆえに、$E(C) \in \ker(B_G^1) = \mathcal{C}(G)$

後で証明する。

$V \in \mathcal{V}(G)$をとる。

\begin{align} e \in \ ^tB_G^1(V) &⇔ e \in \sum_{v \in V}E_G(v) \\ &⇔ V内にeに接続している頂点が奇数個ある\\ &⇔ V内にeに接続している頂点がちょうど1個ある\\ &⇔ VとV(G)\setminus Vの両方にeに接続している頂点がある \\ &⇔ e \in (\bigcup_{v \in V}{E_G(v)})\cap(\bigcup_{v \in V(G)\setminus V}{E_G(v)}) \\ &⇔ e \in D(V) \end{align}

$|V(G)|=0 \lor |V(G)|=1$の場合、異なる2点が取れないので、$G$は連結。
また、全ての$V \subset V(G)$に対し$\ ^tB_G^1(V)=0$であり、$V=0 \lor V=V(G)$である。
よって成り立つ。

$|V(G)| \geq 2$の場合
[$⇐$]
$v_0,v_{n-1} \in V(G)\ (v_0 \not= v_{n-1})$をとる。
$V_0=\{v_0\}$とおく。$V_0 \not =0 \land V_0 \not= V(G)$である。
仮定の対偶より$\ ^tB_G^1(V_0) \not=0$
よって、$v_0$に隣接している$V(G) \setminus V_0$の元が存在する。
そのような元を1つ取り、$v_1$とおく。
$v_1=v_{n-1}$ならば、$P=(\{v_0,v_1\},\{\{v_0,v_1\}\})$が$v_0,v_1$を結ぶ道。
そうでないならば、$V_1=\{v_0,v_1\}$と置く。$V_1 \not =0 \land V_1 \not= V(G)$である。
仮定の対偶より$\ ^tB_G^1(V_1) \not=0$

ハイパーグラフに対して成り立つので。

[存在性]
$T$は木だから連結。よって$v,v'$を結ぶ道が存在する。

[唯一性]
$v,v'$を結ぶ異なる2つの道があるとする。それを$P_0,P_1$とおく。
$P_0=(\{u_{0},u_{1},...,u_{n-1}\},\{\{u_{0},u_{1}\},\{u_{1},u_{2}\},...,\{u_{n-2},u_{n-1}\}\})$
$P_1=(\{v_{0},v_{1},...,v_{m-1}\},\{\{v_{0},v_{1}\},\{v_{1},v_{2}\},...,\{v_{m-2},v_{m-1}\}\})$
と表す。(ただし$u_{0}=v_{0}=v, u_{n-1}=v_{m-1}=v'$)
$P_1$のラベル付けを固定して考える。

$P_0$と$P_1$は異なるから、$V(P_0) + V(P_1) \not = \varnothing$
$V(P_0) + V(P_1)$の元であってラベルが最小なものの直前の頂点を$v_i$とする。

$v' \in V(P_0) \cap V(P_1)$だから、$\{v_k \in V(P_0) \cap V(P_1) \ |\ k \geq i\} \not = \varnothing$
$\{v_k \in V(P_0) \cap V(P_1) \ |\ k \geq i\}$の元であってラベルが最小なものを$v_j$とする。

$v_i$の次の頂点は2つあり、その頂点から$v_j$にたどり着く道が2つある。
その道を
$P_2=(\{v_i,v_{i+1},...,v_j\},\{\{v_i,v_{i+1}\},...,\{v_{j-1},v_j\}\}) \leq P_0$
$P_3=(\{v_i,v_{i+1}',...,v_j\},\{\{v_i,v_{i+1}'\},...,\{v_{j-1}',v_j\}\}) \leq P_1$
とおく。

$V(P_2) \cap V(P_3) = \{v_i,v_j\}$
(これらの道は$v_i,v_j$以外で交わらない。)

$P_0$と$P_1$を$v_i,v_j$でつなげたグラフ
$C=(\{v_i,v_{i+1},...,v_j,v_{j-1}',...,v_{i+1}'\},\{\{v_i,v_{i+1}\},...,\{v_{j-1},v_j\},\{v_i,v_{i+1}'\},...,\{v_{j-1}',v_j\}\})$

これは$T$上の閉路。

これは木に閉路がないことに矛盾。よって$v,v'$を結ぶ道は唯一つである。

[連結性]
任意の2頂点を結ぶ道が存在するから、$G$は連結。

[閉路がない]
閉路があると仮定し、$G$の閉路$C$をとる。
$e = \{v_0,v_1\} \in E(C)$をとる。
$(e,\{e\})$は$v_0,v_1$を結ぶ道である。
$C \setminus \{e\}$も$v_0,v_1$を結ぶ道である。
これらの道は異なる。
これは異なる2頂点を結ぶ道が唯一つであることに矛盾。
よって$G$に閉路は無い。

$e = \{v_0,v_{n-1}\}$とおく。

[存在性]
$S$は$G$の全ての頂点を持つから、$v_0,v_{n-1}$も持つ。

$v_0,v_{n-1}$は同じ連結成分上にある。
よって、$S$上に$v_0,v_{n-1}$を結ぶ道が唯一つ存在する。その道を
$P=(\{v_0,v_1,...,v_{n-2},v_{n-1}\},\{\{v_0,v_1\},\{v_1,v_2\},...,\{v_{n-2},v_{n-1}\}\})$
とおく。

$e \not\in E(P)$である。
$P+\{e\}$は閉路である。

[唯一性]
$S$に閉路はないから、$S+\{e\}$の閉路は必ず$e$を持つ。
$S+\{e\}$から閉路を2つ取り$C_0,C_1$とおく。
$C_0 \setminus \{e\},C_1 \setminus \{e\}$は$v_0,v_{n-1}$を端点とする$S$上の道である。
よって、$C_0 \setminus \{e\}=C_1 \setminus \{e\}$
従って、$C_0=C_1$

$v_\infty \not\in V(T)$をとる。
$v \in V(T)$をとる。
$e = \{v,v_\infty\}$とおく。
$T'=T + \{e\}$とおく。

[$T'$は連結]
$v' \in V(T') (v' \not= v_\infty)$をとる。
$v' \in V(T)$である。

$v'=v$の場合
$(e,\{e\})$は$v'$と$v_\infty$を結ぶ道である。

$v' \not= v$の場合
$T$は連結だから$v'$と$v$を結ぶ道$P$を取れる。
$P+\{e\}$は$v'$と$v_\infty$を結ぶ道である。

[$T'$に閉路は無い]
$T'$に閉路があるとすると、$T$に閉路は無いから、その閉路は$v_\infty$を含む。
$v_\infty$は$e$以外には接続していない。よって$v_\infty$を含む閉路は存在しない。
よって、$T'$に閉路は無い。

$|E(T)|$に関する帰納法で示す。

$|E(T)|=0$のとき
$T=(\{v\},\{\})$
成り立つ。
$|E(T)|=1$のとき
$T=(\{v_0,v_1\},\{\{v_0,v_1\}\})$
成り立つ。

$|E(T)| \leq k$で成り立つとする。
$|E(T)|=k$となる木$T$をとる。

$T$に辺を1つ追加して新たな木を作りたい。

$T$の頂点を結ぶ辺を追加すると閉路ができる。
$T$に2点以上追加すると連結でなくなる。
よって、辺を追加するためには頂点を1点だけ追加する必要がある。

$T$に1点追加して適当な頂点と結ぶと、これも木になる。この木を$T'$とおく。
帰納法の仮定より、$|E(T')|=|E(T)|+1=|V(T)|=|V(T')|-1$

[1次独立性]
$e \in E(G) \setminus E(S)$に対して、$e$を含む基本閉路集合は$C_{S;e}$だけである。
よって基本閉路は1次独立。

[生成性]
$C \in \mathcal{C}(G)$をとる。

$C+\sum_{e \in C \setminus E(S)}C_{S;e} \subset E(S)$
これは$S$上の閉路の辺集合か空集合。(ここ非自明)
$S$に閉路は無いから、$C+\sum_{e \in C \setminus E(S)}C_{S;e} = 0$
よって、$C = \sum_{e \in C \setminus E(S)}C_{S;e}$

$G$が連結グラフのとき、$C_S$は$\mathcal{C}(G)$の基底を成す。
$|E(S)|=|V(G)|-1$だから、$|E(G) \setminus E(S)|=|E(G)|-|V(G)|+1$
$\dim(\mathcal{C}(G))=|E(G)|-|V(G)|+1$
$|CC(G)|=1$だから成立。

$|CC(G)| \geq 2$のとき、
各連結成分$C \in CC(G)$について$\dim(\mathcal{C}(C))=|E(C)|-|V(C)|+1$が成立。

$G=\bigsqcup_{C \in CC(G)}C$だから、$\mathcal{C}(G)=\bigoplus_{C \in CC(G)}\mathcal{C}(C)$(ここ非自明)
よって、$\dim(\mathcal{C}(G))=\sum_{C \in CC(G)}\dim(\mathcal{C}(C))=|E(G)| - |V(G)| + |CC(G)|$

$G$が連結グラフのとき、$B_S$は$\mathcal{B}(G)$の基底を成す。
$|E(S)|=|V(G)|-1$だから、$\dim(\mathcal{B}(G))=|E(S)|=|V(S)|-1=|V(G)|-1$
$|CC(G)|=1$だから成立。

$|CC(G)| \geq 2$のとき、
各連結成分$C \in CC(G)$について$\dim(\mathcal{B}(C))=|V(C)|-1$が成立。

$G=\bigsqcup_{C \in CC(G)}C$だから、$\mathcal{B}(G)=\bigoplus_{C \in CC(G)}\mathcal{B}(C)$(ここ非自明)
よって、$\dim(\mathcal{B}(G))=\sum_{C \in CC(G)}\dim(\mathcal{B}(C))=|V(G)| - |CC(G)|$