スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

グラフと線形代数

tanzaku さん主催の Competitive Programming Advent Calendar 8日目

この記事では、「グラフと線形代数」をテーマに、競技プログラミングに関係ありそうなトピックを 2 つ紹介します。

なるべく難しい線形代数を使わないものを選びました。グラフの基礎的なこと、行列のかけ算、行列式の計算法を知っていれば読めると思います。

閉路

1 つめのトピックはグラフの交差しない閉路の数え上げです。

ここでは、自己ループ、多重辺をもたない無向グラフ $G$ を考えます。
$n$ を $G$ の頂点数、$m$ を $G$ の辺数とします。

まずは、隣接行列 (adjacency matrix) の復習からはじめましょう。
$G$ の隣接行列とは、$n \times n$ の行列で、その $( i, j )$ 成分が
・ 頂点 $i$ と $j$ が辺で結ばれているときは $1$
・ そうでないときは $0$
であるもののことをいいます。

たとえば、次のグラフ

の隣接行列は$$\begin{pmatrix} 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 1\\ 0 & 1 & 1 & 0 \end{pmatrix}$$となります。

$G$ の隣接行列を$$A=\begin{pmatrix} a_{0,0} & a_{0,1} & \cdots & a_{0,n-1}\\ a_{1,0} & a_{1,1} & \cdots & a_{1,n-1}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n-1,0} & a_{n-1,1} & \cdots & a_{n-1,n-1} \end{pmatrix}$$とします。$A$ を二乗してみましょう。$A^2$ の $( i, j )$ 成分は$$\sum_{k=0}^{n-1} a_{i,k} \cdot a_{k,j}$$です。隣接行列の成分は $0$ または $1$ なので、この式は $a_{i,k} = a_{k,j} = 1$ であるような $k$ の個数を数えていることになります。$a_{i,k} = a_{k,j} = 1$ というのは、つまり「頂点 $i, k$ 間に辺があり、かつ頂点 $k, j$ 間に辺がある」ということなので、すなわち、この式は$A^2$ の $( i, j )$ 成分は $i, j$ を結ぶ長さ $2$ の道の個数を表しているということが分かります。特に、$A^2$ の $( i, i )$ 成分は $i$ から始まる長さ $2$ の閉路の個数を表しています。

たとえば、最初の例のグラフでは$$A^2 \ \text{の} \ (0, 0) \ \text{成分} = 2$$で、これは$$0 \to 1 \to 0$$ $$0 \to 2 \to 0$$という 2 つの閉路があることに対応しています。

一般に、$$A^k \ \text{の} \ ( i, j ) \ \text{成分は} \ i, j \ \text{を結ぶ長さ}\ k \ \text{の道の個数}$$$$A^k \ \text{の} \ ( i, i ) \ \text{成分は} \ i \ \text{から始まる長さ} \ k \ \text{の閉路の個数}$$となります。

上記の方法は同じ頂点を $2$ 回以上通るような閉路もカウントしていることに注意しましょう。また、向きが違う閉路は異なるものだとみなして数えています。最初の例のグラフでは、頂点 $0$ から始まる長さ $4$ の閉路は$$0 \to 1 \to 0 \to 1 \to 0$$ $$0 \to 1 \to 0 \to 2 \to 0$$ $$0 \to 1 \to 2 \to 1 \to 0$$ $$0 \to 1 \to 2 \to 3 \to 0$$ $$0 \to 2 \to 0 \to 1 \to 0$$ $$0 \to 2 \to 0 \to 2 \to 0$$ $$0 \to 2 \to 3 \to 1 \to 0$$ $$0 \to 2 \to 3 \to 2 \to 0$$と 8 個の閉路が見つかります。

では、同じ頂点を $2$ 回以上通らないような閉路、つまり交差しない閉路だけを数え上げたい場合はどうすればいいでしょうか? すぐ上で見た「長さ $4$ の閉路」についていえば、$$0 \to 1 \to 2 \to 3 \to 0$$だけを取り出したいというわけです。これはなかなか大変です。

閉路の長さ $k$ が小さい場合のみ、良い方法が知られています。
たとえば $k=3$ のとき、つまりグラフに含まれる三角形の個数を求める問題を考えてみます。上記の方法に従って、隣接行列の三乗を計算して対角成分の和 ($S$ とする) を求めると、一つの三角形に対して、始点違いが 3 通り分、三角形を巡る向き違いが 2 通り分、重複してカウントされてしまいます。つまり、$S/6$ がグラフに含まれる (重複を排除した) 三角形の個数になります。$k$ が大きくなると、より多くのパターンを考慮する必要があり、このような素朴な方法で表式を求めるのは難しくなります。

$k = 3, 4, 5, 6$ のときの公式を書いておきます。長さ $k$ の交差しない閉路の個数 $c_k$ は次のようになります。
$$c_3 = \frac{1}{6}\sum_{i=0}^{n-1}a_{i,i}^{(3)},$$ $$c_4 = \frac{1}{8}\left( \sum_{i=0}^{n-1}a_{i,i}^{(4)} - 2m - 2\sum_{i \ne j}a_{i,j}^{(2)} \right ),$$ $$c_5 = \frac{1}{10}\left( \sum_{i=0}^{n-1}a_{i,i}^{(5)} - 5\sum_{i=0}^{n-1}a_{i,i}^{(3)} - 5\sum_{i=0}^{n-1}\left( d_i - 2 \right ) a_{i,i}^{(3)} \right ),$$\begin{eqnarray*}c_6 =& \frac{1}{12}\left( \sum_{i=0}^{n-1}a_{i,i}^{(6)} - 6\sum_{i=0}^{n-1}a_{i,i}^{(4)}d_i - 3\sum_{i=0}^{n-1}\left (a_{i,i}^{(3)} \right )^2 + 4\sum_{i=0}^{n-1}d_i^3\right.\\
&+ 6\sum_{i=0}^{n-1}a_{i,i}^{(4)} + 9\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\left (a_{i,j}^{(2)} \right )^2 a_{i,j} + 3\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_{i,j}^{(3)}\\
&\left.- 12\sum_{i=0}^{n-1}d_i^2 + 4\sum_{i=0}^{n-1}d_i - 4\sum_{i=0}^{n-1}a_{i,i}^{(3)} \right ).\end{eqnarray*}ここで、$a_{i,j}^{(k)}$ は $A^k$ の $( i, j )$ 成分、$d_i = \sum_{j=0}^{n-1} a_{i,j}$ は頂点 $i$ の次数です。この結果は以下の論文やサイトから引用しました。

F. Harary, B. Manvel: On the number of cycles in a graph
$c_3, c_4, c_5$ の式が載っています。有向グラフの場合も考察しています。

S. N. Perepechko, A. N. Voropaev: The number of fixed length cycles in an undirected graph. Explicit formulae in case of small lengths
$c_7$ の公式と一般の $c_k$ の公式の作り方が載っています。

W. Brostow, A. Schinzel: On interesting walks in a graph
交差しない閉路ではなく、交差しない道を数えている論文です。

А. Н. Воропаев: Вывод явных формул для подсчёта циклов фиксированной длины в неориентированных графах
$c_6$ の公式と一般の $c_k$ の公式の作り方が載っているようです。(読めない...)

Explicit formulae for counting k-cycles in undirected graphs - FlowProblem -
$c_3$ から $c_{12}$ までの公式を導いて、それを実装した C++ のソースコードが公開されています。残念ながら公式は載せてくれてないようで、ソースコードを解読しないといけません。二部グラフの場合も考察しています。

公式の導出方法については、私もちゃんと読めていないので、気になる方は調べてみてください。

さて、せっかく計算方法を知ったので、この問題を解きましょう。
PKU 2861
おそらく、想定解法は別にあるのだと思いますが。

全域木

2 つめのトピックは、無向グラフの全域木の数え上げです。

上と同じように、次のグラフ

を例に挙げながら進めます。

まず、無向グラフ $G$ のラプラシアン行列 (Laplacian matrix) を定義します。
$G$ のラプラシアン行列とは、$n \times n$ の行列で、その $( i, j )$ 成分が
・ $i = j$ のとき、頂点 $i$ の次数
・ $i \ne j$ のとき、隣接行列の $( i, j )$ 成分の $-1$ 倍
であるもののことをいいます。

例のグラフのラプラシアン行列は$$\begin{pmatrix} 2 & -1 & -1 & 0\\ -1 & 2 & 0 & -1\\ -1 & 0 & 2 & -1\\ 0 & -1 & -1 & 2 \end{pmatrix}$$となります。

ラプラシアン行列の第 $n$ 行、第 $n$ 列を取り除いてできる $n-1 \times n-1$ 行列を $L$ とします。例のグラフに対しては$$L=\begin{pmatrix} 2 & -1 & -1\\ -1 & 2 & 0\\ -1 & 0 & 2 \end{pmatrix}$$となります。

このとき、$L$ の行列式 $\det(L)$ の値が $G$ の全域木の個数になります。この結果は行列木定理 (Matrix-Tree Theorem) と呼ばれています。

実際、例のグラフでは $\det(L) = 4$ で、$4$ 通りの全域木があります。


※ より詳しくは、「ラプラシアン行列の任意の余因子の値が等しくなり、その値が $G$ の全域木の個数である」ということが言えますが、わかりやすさを重視して上のように書きました。

ここでは証明はしませんが、ちょっと高度な線形代数の知識を使えば証明できます。グラフ理論の本に載っているので興味のある人は調べてみてください。

最後に、行列木定理を使って解ける例題を挙げておきます。
UVa 10766
SPOJ 2670
2 問目は応用編です。ぜひチャレンジしてみてください。

2012/08/17 追記
SRM 551 Div.1 Hard (解説)
でも登場。難しい。

2013/12/23 追記
MathJax を導入したので数式を書き直し。文章が変なところを修正。

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。