はじめに
線形代数というとベクトルや行列が出てきて拒否反応がある人もいると思いますが、そういうものをあまり使わなくても楽しめるような線形空間はあります。ここではその例として、無向グラフの 閉路空間 という線形空間について説明します。
閉路空間は 循環的複雑度 と呼ばれるソフトウェア・メトリクスの理論的な基礎になっています。これについては別記事で書きます。
参考文献
- Wikipedia, Cycle space
- Wikipedia, Cycle basis
- Wikipedia, ベクトル空間
この記事で例としてあげたグラフは、上記記事のグラフに頂点を足したものです。
閉路空間とは
簡易バージョン
理解の容易のために、まずは単純化して述べます。
頂点数$n$、辺数$m$であるような連結無向グラフ$G$において、$G$の閉路の集合はその対称差演算について線形空間をなし、その次元は$m-n+1$である。
連結グラフとは全体がつながっているグラフのことです。正式バージョンも載せておきますが今のところ無視してもOKです。
正式バージョン
頂点数$n$、辺数$m$であり$c$個の連結成分を持つような無向グラフ$G$において、$G$の部分グラフで各頂点の次数が全て偶数であるようなもの集合はその対称差演算について$GF(2)$上の線形空間をなし、その次元は$m-n+c$である。
以下、閉路空間がどのように構成されるかについて説明します。
単純バージョンについて説明
線形空間を構成するためには、空間の元 (ベクトル)、元の和、元のスカラー倍について定める必要があります。
まず、次のような連結無向グラフ$G$をひとつ固定しておきます。連結でない場合については最後に述べます。
閉路空間とその元 (= ベクトル)
そして$G$の閉路全体の集合からなる空間を考え、これが線形空間とできることを見ていきます。
たとえばこのような閉路があります。
なお、これらはどちらも単純閉路 (始点と終点のみが同じ頂点となる閉路) ですが、そうでない閉路も含めて考えます。これらの閉路それぞれが閉路空間の元になります。
元の足し算
次に、これら2つの閉路の「和」、ベクトル表記でいうと$\vec{a}+\vec{b}$にあたるもの、を定義します。
ここでは 対象差 (symmetric difference) として定義され、どちらかの閉路に のみ 含まれる辺を合わせたものです。先ほどの2つの閉路の和はこのようなパスになります。これは (単純でない) 閉路になっています。
実は、閉路の和は必ず閉路になることが証明できます (略) ので、この空間は和について閉じていることがわかります。
閉路の和が閉路になる、という部分は少し雑に書いています。後で正しく書きます。
元のスカラー倍
線形空間においては元のスカラー倍 (スカラー情報) を考える必要があります。$3\vec{a}$みたいなやつです。係数として許される値の集合は 体 (加減乗除が定義されている集合構造) である必要があります。一般には実数体や有理数体が用いられます。これを線形空間の 係数体 と呼びます。
閉路空間においては係数体として$GF(2)$を採用します。これは$0$および$1$のみを含む体です。計算は2進数1ビットだと思ってやればいいです: $$\begin{gather}0+0=0, 0+1=1, 1+1=0,\\
0-0=0, 0-1=1, 1-0=1, 1-1=0\\
0\times0=0,0\times1=0,1\times1=1\\
0\div1=0,1\div1=1\end{gather}$$
これを用いてスカラー倍を
- ある閉路の$1$倍はその閉路そのまま
- ある閉路の$0$倍は辺が1本もないグラフ (※これも閉路とみなします)
と定義すると、いずれの結果も閉路になるので、この空間はスカラー倍について閉じていることがわかります。
次元と基底
これにより閉路の空間は ($GF(2)$上の) 線形空間になることがわかりました。これが$G$上の閉路空間 (cycle space) と呼ばれるものです。
線形空間の一般的な性質より、閉路空間も決まった次元$d$を持ち (証明略)、すべての閉路は 閉路基底 (cycle basis) と呼ばれる$d$個の閉路の線形結合として表すことができます。基底の取り方には任意性がありますが個数は常に一定です。
$G$閉路空間においては、後述するように次元が$m-n+1$であることがわかります。例のグラフにおいては$d=15-11+1=5$となります。
実際の基底を計算することもできます。例のグラフにおいてはたとえばこのような閉路基底が取れます。
次元の別の意味
$G$の閉路空間の次元には別の意味もあります。それは「全ての閉路をなくすために必要な、取り除くべき辺の最小数」というものです。たしかに例においては、すべての閉路を取り除くためには最低5本の辺を取り除く必要があります。循環的複雑度はこの性質を利用してプログラムまたはフローグラフの複雑度を表すものです。
ここまでで概ね説明は終了です。以下、わかりやすさのために省略した部分を説明します。
単純化した説明の精緻化
閉路の和
「閉路の和は必ず閉路になります」と言ったのはちょっと嘘です。たとえばこの2つを足すと、
こうなります。これは一般には閉路とは呼ばれません。
なので、閉路空間として和について閉じているためには空間の元を閉路ではなくて「閉路の和」とする必要があります。すると「閉路の和」の和は必ず「閉路の和」になります。
ただしこの「閉路の和」なる言い方もやや不正確なので、「すべての頂点の次数が偶数であるような$G$の部分グラフ」と言うと数学的に厳密になります。
なお、元の定義をこのようにした場合でも、閉路のみからなる基底を構成できることには変わりません。さらに言うと、単純閉路のみからなる基底を構成することができます。もっと強い性質を持つ基底も構成できますが、これは fundamental basis のところで触れます。
連結成分
はじめに$G$は連結であることを仮定しました。しかし、閉路空間は$G$が連結でない場合も全く同様に、線形空間として構成できます。この場合、連結成分数が$c$であるとすると、空間の次元 (= 基底の個数) は$m-n+c$となります。単純バージョンで紹介した次元は$c=1$の場合であることがわかります。
まだ説明していないこと
この記事に追加するか、だいぶ長くなってきたので別記事にするかにします。
- 次元の計算
- Fundamental basis