グラフ理論#2「多次元グラフ」
今回の目標
グラフの多次元への一般化をしてみよう！
ちょっと書きかけ
面空間
2次元面空間
次を満たす1次元閉路集合$C \in \mathcal{C}(G)$を2次元面と呼ぶ。
- $C\not=0$
- $C_0,C_1 \in \mathcal{C}(G), C=C_0+C_1 ⇒ |C| \leq |C_0| \lor |C| \leq |C_1|$
(極小な閉路を面とみなす。)
グラフ$G$の2次元面の集合$F^2$があるとき、$G=(V(G),E(G),F^2)$を2次元面付きグラフと呼ぶ。
この$F^2$を$F^2(G)$と書く。
2次元面付きグラフはグラフとしても扱う。
2次元面付きグラフ$G$に対し、$\mathcal{F}^2(G):=2^{F^2(G)}$に頂点空間や辺空間と同様に和とスカラー倍を定義したものを$G$の「2次元面空間」と呼ぶ。
$F^2(G)$の元の1点集合全体を$\mathcal{F}^2(G)$の標準基底と呼ぶ。
$F^2_{G}: E(G) → \mathcal{F}^2(G)$
$F^2_{G}(e)=\{f \in F^2(G)\ |\ e \in f\}$
($e$を含む$F^2(G)$内の2次元面全体)
$B_{G}^2:\mathcal{F}^2(G) → \mathcal{E}(G)$
$$B_{G}^2(F^2):=\sum_{f_2 \in F^2}f_2$$
$^tB_{G}^2:\mathcal{E}(G) → \mathcal{F}^2(G)$
$$^tB_{G}^2(E):=\sum_{e \in E}F^2_{G}(e)$$
$B_G^2$を2次元境界写像、$^tB_G^2$を2次元余境界写像と呼ぶ。
n次元面空間
同様に
$C \in \ker(B_{G}^2)$が3次元面とは
- $C\not=0$
- $C_0,C_1 \in \ker(B_{G}^2), C=C_0+C_1 ⇒ |C| \leq |C_0| \lor |C| \leq |C_1|$
$G$の3次元面の族$F^3$を取り、$G=(V(G),E(G),F^2(G),F^3(G))$とおく。
$\mathcal{F}^3(G):=2^{F^3(G)}$を$G$の「3次元面空間」と呼ぶ。
(多面体空間と呼んでもいいかもしれない。)
$F^3(G)$の元の1点集合の族を$\mathcal{F}^3(G)$の標準基底と呼ぶ。
$F^3_{G}: F^2(G) → \mathcal{F}^3(G)$
$F^3_{G}(f_2)=\{f_3 \in F^3(G)\ |\ f_2 \in f_3\}$
($f_2$を含む$F^3(G)$内の3次元面全体)
$B_{G}^3:\mathcal{F}^3(G)→\mathcal{F}^2(G)$
$F^3 \subset F^3(G)$に対し、$$B_{G}^3(F^3):=\sum_{f_3 \in F^3}f_3$$
$^tB_{G}^3:\mathcal{F}^2(G) → \mathcal{F}^3(G)$
$$^tB_{G}^3(F^2):=\sum_{f_2 \in F^2}F^3_G(f_2)$$
これを繰り返して$n\geq2$に対して$n$次元面空間が定義出来る。
$F^n(G)$が空でなければ、$G$の$n+1$次元面の個数は$n$次元面の個数未満である。
$F_i$として$i$次元面全体を取る。
$F^n$が空でなければ、
$$\dim(\mathcal{F}^n(G)) > \dim(\mathcal{F}^{n+1}(G))$$
になって、どこかで0空間になるんだったらその直前の$n$を$G$の次元として定義できそう。
同じ方法で頂点空間から辺空間を構成することが出来る。
$B_G^0:\mathcal{V}(G) → \mathbb{F}_2;V ↦ 0$と定める。
$C \in \ker(B_G^0)が$1次元面とは
- $C \not= 0$
- $C_0,C_1 \in \ker(B_G^0), C=C_0+C_1⇒|C|\leq|C_0|\lor|C|\leq|C_1|$
$F^1$を1次元面の集合とする。
$F^1$に対し、$\mathcal{E}(G)=\mathbb{F}_2^{F^1}$とおく。
これは$F^1$を辺集合とした辺空間ということができる。
このとき$B_G^1$の定義は上の定義と一致する。
この意味でグラフとはハイパーグラフであって「極小」なものを辺としているものであると思える。
双対グラフ
辺双対
$G$:グラフ
$v \in V(G)$
$\deg_G(v) := |E_G(v)|$
$\deg_G(v)$を$v$の次数と呼ぶ。
これは$v$に接続している辺の個数のこと。
全ての頂点の次数が$k$であるグラフを$k$-頂点正則グラフと呼ぶ。
2-頂点正則グラフ$G$に対し、$G$の辺双対を次で定める。
$L_1(G):=(E(G),\{E_G(v) \ |\ v \in V(G) \})$
$V(G)$と$E(L_1(G))$は一対一に対応する。
$E(G)$と$V(L_1(G))$は一対一に対応する。
$d_v:V(G)→E(L_1(G));v ↦ E_G(v)$
$d_e:E(G)→V(L_1(G));e ↦ e$
とすると$d_v,d_e$は全単射。
$\mathcal{V}(L_1(G)) \simeq \mathcal{E}(G)$
$\mathcal{E}(L_1(G)) \simeq \mathcal{V}(G)$
閉路の辺双対は同じ閉路
$L_1(C_n) \simeq C_n$
$C_n$の頂点の次数は全て2。
$C_n=(\{v_0,v_1,...,v_{n-1}\},\{\{v_0,v_1\},\{v_1,v_2\},...,\{v_{n-1},v_0\}\})$とおく。
$v_i=v_{i \mod n} \ (i \geq n)$とする。
$\phi:V(C_n)→V(L_1(C_n))$
$\phi(v_i)=\{v_i,v_{i+1}\}$
と定める。
任意の$\{v_i,v_{i+1}\} \in E(G)$に対し、$\phi(\{v_i,v_{i+1}\})=\{\{v_i,v_{i+1}\},\{v_{i+1},v_{i+2}\}\}=E_G(v_{i+1}) \in E(L_1(G))$
よって、これはグラフ準同型。
$\psi:V(L_1(C_n))→V(C_n)$
$\psi(\{v_i,v_{i+1}\})=v_i$
と定める。
任意の$\{\{v_i,v_{i+1}\},\{v_{i+1},v_{i+2}\}\} \in E(L_1(G))$に対し、$\psi(\{\{v_i,v_{i+1}\},\{v_{i+1},v_{i+2}\}\})=\{v_i,v_{i+1}\} \in E(G)$
よって、これもグラフ準同型。
$\phi$と$\psi$は互いに逆写像。
よって、$L_1(C_n) \simeq C_n$
連結成分ごとにとってもok
$G=H_1 \sqcup H_2 ⇒ L_1(G)=L_1(H_1) \sqcup L_1(H_2)$
$G=(V(G),E(G))=(V(H_1) \sqcup V(H_2), E(H_1) \sqcup E(H_2))$とする。
$L_1(G)=(E(G),\{E_G(v) \ |\ v \in V(G) \})$
$L_1(H_1)=(E(H_1),\{E_{H_1}(v) \ |\ v \in V(H_1) \})$
$L_1(H_2)=(E(H_2),\{E_{H_2}(v) \ |\ v \in V(H_2) \})$
[頂点集合が非交和になっていること]
$V(L_1(G))=E(G)=E(H_1) \sqcup E(H_2)=V(L_1(H_1)) \sqcup V(L_1(H_2))$
[辺集合が非交和になっていること]
$e \in E(L_1(G))$をとる。
$v=d_v^{-1}(e) \in V(G)$とおく。
$V(G)=V(H_1) \sqcup V(H_2)$だから、$v$は$V(H_1)$と$V(H_2)$のどちらか一方に入っている。
よって、$e$は$E(L_1(H_1))$と$E(L_1(H_1))$のどちらか一方に入っている。
ゆえに、$E(L_1(G))=E(L_1(H_1)) \sqcup E(L_1(H_1))$
$L_1(G) \simeq G$
全ての頂点の次数が2だから、$G$はいくつかの閉路の非交和で表される。(ここ非自明)
補題より$L_1(G) \simeq G$
2次元面双対
$G$:2次元面付きグラフ
$e \in E(G)$に対し、$e$の$F^2(G)$に関する次数を次で定める。
$\deg_{G}(e):=|F^2_{G}(e)|$
全ての辺の次数が$k$である2次元面付きグラフを$k$-辺正則グラフと呼ぶ。
$G,G'$:2次元面付きグラフ
$\phi:V(G)→V(G')$が2次元面付きグラフ準同型とは、
$\phi(E(G)) \subset E(G')$
$\phi(F^2(G)) \subset F^2(G')$
が成り立つこと。
$\phi$の像の像や像の像の像を取っていることに注意。
互いに逆な2次元面付きグラフ準同型があるとき、2次元面付きグラフとして同型という。
全ての頂点の次数が1以上である2-辺正則グラフ$G$に対して、$G$の2次元面双対を次で定める。
$V'=F^2(G)$
$E'=\{F^2_{G}(e) \ |\ e \in E(G) \}$
$F^2\\'=\{F^2_{G}(E_G(v)) \ |\ v \in V(G) \}$
$L_2(G):=(V',E',F^2\\')$
$v \in V(G)$に対し、$F^2_{G}(E_G(v))$は$L_2(G)$の2次元面
つまり2次元面双対の定義はwell-defined
$v \in V(G)$をとる。
$E=F^2_{G}(E_G(v)) \in \mathcal{E}(L_2(G))$とおく。
[$E \in \ker(B_{L_2(G)}^1)$]
$f \in V(L_2(G))$をとる。
$$[f \in B_{L_2(G)}^1(E)]=\sum_{e^* \in E(L_2(G))}[e^* \in E][f \in e^*]$$
$f \in e^*$とすると、$e^*$はもう一つ異なる面を持つ。その面を$f'$とおく。
$\{f,f'\}=e^*$である。
[$E$は極小]
$C_0,C_1 \in \ker(B_{L_2(G)}^1),E=C_0+C_1$とする。
??????
$V(G)$と$F^2(L_2(G))$は一対一に対応する。
$E(G)$と$E(L_2(G))$は一対一に対応する。
$F^2(G)$と$V(L_2(G))$は一対一に対応する。
$L_2(L_2(G)) \simeq G$
$V(L_2(G))=F^2(G)$
$E(L_2(G))=\{F^2_{G}(e) \ |\ e \in E(G) \}$
$F^2(L_2(G))=\{F^2_{G}(E_G(v)) \ |\ v \in V(G) \}$
$V(L_2(L_2(G)))=F^2(L_2(G))$
$E(L_2(L_2(G)))=\{F^2_{L_2(G)}(e) \ |\ e \in E(L_2(G)) \}$
$F^2(L_2(L_2(G)))=\{F^2_{L_2(G)}(E_{L_2(G)}(v)) \ |\ v \in V(L_2(G)) \}$
$\phi:V(G)→V(L_2(L_2(G)))$
$v ↦ F^2_{G}(E_G(v))$
と定める。
任意の$\{v_0,v_1\} \in E(G)$に対し、
\begin{align}
\phi(\{v_0,v_1\}) &= \{\phi(v_0), \phi(v_1)\} \\
&= \{F_{G}^2(E_G(v_0)),F_{G}^2(E_G(v_1))\} \\
&= \{F_{G}^2(\{e_0,...,e_{n-1}\}),F_{G}^2(\{e_0',...,e_{m-1}'\})\} \\
&= \{\{F_{G}^2(e_0),...,F_{G}^2(e_{n-1})\},\{F_{G}^2(e_0'),...,F_{G}^2(e_{m-1}')\}\} \\
&= \{\{\{f_{00},f_{01}\},...,\{f_{n-10},f_{n-11}\}\},\{\{f_{00}',f_{01}'\},...,\{f_{n-10}',f_{m-11}'\}\}\} \\
&= \{\{e_{L0},...,e_{Ln-1}\},\{e_{L0}',...,e_{Lm-1}'\}\}\} \\
&???\\
&\in E(L_2(L_2(G)))
\end{align}
任意の$f=\{e_0,e_1,...,e_{n-1}\} \in F^2(G)$に対し、
全ての辺の$F^2$に関する次数が2であるような$F^2$は存在すればただ一つ。
$\mathcal{C}(L_2(G)) \simeq \mathcal{B}(G)$
$\mathcal{B}(L_2(G)) \simeq \mathcal{C}(G)$
n次元面双対
$G:=(V(G),E(G),F^2(G),F^3(G),...,F^n(G))$
$\deg_{G}(f_{n-1})=|F_{G}^n(f_{n-1})|$
$G,G'$:$n$次元面付きグラフ
$\phi:V(G)→V(G')$
$\phi(E(G)) \subset E(G')$
$\phi(F^2(G)) \subset F^2(G')$
...
$\phi(F^n(G)) \subset F^n(G')$
連結成分空間
頂点連結成分空間
$C \in CC(G)$の$V(C)$に対応する$G$の頂点集合を$V_C$と表す。
$G$の頂点連結成分空間とは
$\mathcal{VCC}(G) \leq \mathcal{V}(G)$:$V_C$全体で生成されるベクトル空間のこと
$V_C$全体は1次独立だから、
$\dim(\mathcal{VCC}(G))=|CC(G)|$
$C \in CC(G)$に対し、
$^tB_G^1(V_C)=0$
$C$に含まれない辺は$^tB_G^1(V_C)$に含まれない。
$C$に含まれる辺は、両端点が$C$に含まれるから、1+1=0で$^tB^1(V_C)$に含まれない。
$\mathcal{VCC}(G)=\ker(^tB_G^1)$
[示すこと:$\mathcal{VCC}(G) = \ker(^tB_G^1)$]
ある$\mathcal{C} \subset CC(G)$があって、
$V=\sum_{C\in\mathcal{C}}V_C$と表せる。
$^tB_G^1(V_C)=0$、$^tB_G^1$は線形写像だから、
$V \in \ker(^tB_G^1)$
$V \not\in \mathcal{VCC}(G)$と仮定する。
ある連結成分について、$V$に入っている頂点と入っていない頂点で隣接しているものが存在する。
その間の辺は$^tB_G^1(V)$に含まれる。
これは$V \in \ker(^tB_G^1)$に反する。
よって、
$V \in \mathcal{VCC}(G)$
辺連結成分空間
$C \in CC(G)$の$E(C)$に対応する$G$の辺集合を$E_C$と表す。
$G$の辺連結成分空間とは
$\mathcal{ECC}(G) \leq \mathcal{E}(G)$:$E_C$全体で生成されるベクトル空間のこと。
1点だけ孤立した連結成分$C$に対する$E_C$はゼロベクトル。
それ以外の$E_C$は1次独立。
よって、
$\dim(\mathcal{ECC}(G)) \leq |CC(G)|$
シリーズ
この記事を高評価した人
この記事に送られたバッジ
投稿者
