グラフの辺集合 \(E\) の部分集合 \(F\) は各辺 \(e \in E\) が”辺集合 \(F\) に含まれる/含まれない”をベクトルの各要素の”0/1″に対応させることで \(\mathbb{Z}/2\mathbb{Z}\) ベクトルと一対一対応する。このとき、ベクトルの和は辺集合の対称差と対応づく(図を参照)。辺集合がなすこのベクトル空間を辺空間と呼ぶ。
この記事では辺空間 \(\mathcal{E}(G)\) の部分空間であるサイクル空間、カット空間の基底について解説する。
サイクル空間 \(\mathcal{C}(G)\) とはサイクルの辺集合全体が生成する \(\mathcal{E}(G)\) の部分空間、またカット空間 \(\mathcal{B}(G)\) とはカットの辺集合全体が生成する \(\mathcal{E}(G)\) の部分空間と定義する。ここでカットとは頂点集合の分割 \(V={A}\coprod{B}\) を用いて、$$E(A,B)=\{ab \in E : a\in V,b\in V\}$$ と書ける辺集合のことである。例えば最大流に登場する最小カットはカットの一例である。簡単のために、この記事では辺集合 \(F \in \mathcal{E}(G)\) と \(G\) の部分グラフ \((V,F)\) を区別せずに使う。
以下に述べるように、サイクル・カット空間の基底は全域木を用いて簡単に列挙することができる。適当な全域木 \(T \) を取る。\(T\) に含まれない \(G\) の辺 \(e \in E(G) \setminus E(T)\) を \(T\) に加えた時にできる唯一の閉路 \(C_e\) を \(T\) に関する \(e\) の基本閉路と定義する。また、\(f \in E(T)\) を除いた \(T-f\) の 2 つの連結成分を横切るカット \(D_f\) を \(T\) に関する \(f\) の基本カットと定義する。このとき次の事実が成り立つ。
証明:\(e \notin T\) は基本閉路のうち \(C_e\) のみに含まれる辺であるから、基本閉路は一次独立。同様に \(f \in T\) は基本カットのうち \(D_f\) にのみ含まれる辺であるから基本カットも一次独立。
あとは基本閉路と基本カットがそれぞれサイクル空間とカット空間の全ての元を生成することを示せば良い。サイクル空間の元 \(C+\sum_{e \in C \setminus T} C_e\) は \(T\) の辺のみで構成されるが、そのような回路は存在しない(辺空間での足し算であることに注意)。従って \(C+\sum_{e \in C \setminus T} C_e=\emptyset\) つまり \(C=\sum_{e \in C \setminus T} C_e\) となる。サイクル空間の任意の元 \(C\) が基本閉路で生成できた。同様にカット空間の元 \(D+\sum_{f \in C \cap T} D_f\) は \(T\) の辺を含まないが、そのようなカットは存在しない。従って、\(D=\sum_{f \in D \cap T} D_f\) である。カット空間の任意の元 \(D\) が基本カットで生成できた。
ここから基本閉路・基本カットの数を数えることで \(\mathrm{dim}\ \mathcal{C}(G)=m-(n-1), \mathrm{dim}\ \mathcal{B}(G)=n-1\) が成り立つ。
ところで頂点 \(v\) に接続する辺集合 \(E(v)=E(\{v\},V\setminus\{v\})\) はカットであるが、実はこの形のカットがカット空間全体を生成する。また、連結グラフの任意の一頂点 \(q\) を除い \(n-1\) 個のこの形のカットは基底をなす。基底を求めるだけなら基本カットよりもこちらのほうが求めやすいと思う。
演習
ネタバレを避けるために出典は黒塗りにしている。
参考文献
- Diestel, Reinhard. “Graph theory. 1997.” Grad. Texts in Math 2 (2016). Capter1.9. (preview)
- この記事では扱わなかった、サイクル空間とカット空間が互いに直交補空間であるという話題が載っています。
- [AtCoder 参加感想] 2020/10/12:ARC105 (maspyさんのHP)
- 問題1の原題をカット空間と関連させて解いています(省いてしまいましたが、問題1には続きがあります)。
Comments