グラフと線形代数
tanzaku さん主催の Competitive Programming Advent Calendar ８日目
この記事では、「グラフと線形代数」 をテーマに、競技プログラミングに関係ありそうなトピックを 2 つ紹介します。
なるべく難しい線形代数を使わないものを選びました。
グラフの基礎的なこと、行列のかけ算、行列式の計算法を知っていれば読めると思います。
1 つめのトピックは、グラフの交差しない閉路の数え上げです。
ここでは、自己ループ、多重辺をもたない無向グラフ G を考えます。
n を G の頂点数、m を G の辺数とします。
まずは、隣接行列 ( adjacency matrix ) の復習からはじめましょう。
G の隣接行列とは、n × n の行列で、その ( i, j ) 成分が
・ 頂点 i と j が辺で結ばれているときは 1
・ そうでないときは 0
であるもののことをいいます。
たとえば、次のグラフ
の隣接行列は
となります。
このグラフは以下でも例として登場します。
G の隣接行列を
とします。
A を 2 乗してみましょう。
A2 の ( i, j ) 成分は
です。
この式を注意深く見てみると、これは
であるような k の個数を数えていますね。
aik = akj = 1 というのは、つまり 「頂点 i, k 間に辺があり、かつ頂点 k, j 間に辺がある」 ということです。
すなわち、A2 の ( i, j ) 成分は i, j を結ぶ長さ 2 の道の個数を表しています。
特に、A2 の ( i, i ) 成分は i から始まる長さ 2 の閉路の個数を表しています。
向きが違えば別々の閉路だと思って数えてしまっていることに注意しましょう。
たとえば、例のグラフでは
A2 の (0, 0) 成分 = 2
で、これは
0 → 1 → 0
0 → 2 → 0
という 2 つの閉路があることに対応しています。
一般に、
Ak の ( i, j ) 成分は i, j を結ぶ長さ k の道の個数
Ak の ( i, i ) 成分は i から始まる長さ k の閉路の個数
となります。
上記の方法は、同じ頂点を 2 回以上通るケースもカウントしています。
例のグラフでは、
頂点 0 から始まる長さ 4 の閉路は
0 → 1 → 0 → 1 → 0
0 → 1 → 0 → 2 → 0
0 → 1 → 2 → 1 → 0
0 → 1 → 2 → 3 → 0
0 → 2 → 0 → 1 → 0
0 → 2 → 0 → 2 → 0
0 → 2 → 3 → 1 → 0
0 → 2 → 3 → 2 → 0
と 8 個も見つかってしまいます。
これはあまり嬉しくないですね。
0 → 1 → 2 → 3 → 0
だけに興味があるわけです。
では、同じ頂点を 2 回以上通らないような閉路、つまり交差しない閉路だけを数え上げたい場合はどうすればいいでしょうか?
これはかなりなかなか大変です。
閉路の長さ k が小さい場合のみ、いい方法が知られています。
どうすればいいでしょう？
がんばって場合わけ？
そのとおりです！
k = 3, 4, 5, 6 のときの公式を書いておきます。
長さ k の交差しない閉路の個数 ck は次のようになります。
} "\fn_phv c_3 = \frac{1}{6}\sum_{i=0}^{n-1}a_{i,i}^{(3)}")
} - 2m - 2\sum_{i \ne j}a_{i,j}^{(2)} \right ) "\fn_phv 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 )")
} - 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 ) "\fn_phv 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 )")
} - 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 + 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)} - 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 ) "\fn_phv 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 + 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)} - 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 )")
ここで、} "\fn_phv a_{i,j}^{(k)}")
は Ak の ( i, j ) 成分、
は頂点 i の次数です。
この結果は以下の論文やサイトから引用しました。
・ On the number of cycles in a graph
c3, c4, c5 の式が載っています。
有向グラフの場合も考察しています。
・ The number of fixed length cycles in an undirected graph. Explicit formulae in case of small lengths
c7 の公式と一般の ck の公式の作り方が載っています。
・ On interesting walks in a graph
交差しない閉路ではなく、交差しない道を数えている論文です。
・ Вывод явных формул для подсчёта циклов фиксированной длины в неориентированных графах
c6 の公式と一般の ck の公式の作り方が載っているようです。 ( 読めない )
・ Explicit formulae for counting k-cycles in undirected graphs - FlowProblem -
c3 から c12 までの公式を導いて、それを実装した C++ のソースコードが公開されています。
残念ながら公式は載せていないようで、ソースコードを解読しないといけません。
二部グラフの場合も考察しています。
論文では何やらすごそうなことをやっているように見えますが、閉路を分類してある程度まとめて数え上げているだけで、要は気合で場合分けしているにすぎません。
さて、せっかく計算方法を知ったので、この問題を解きましょう。
PKU 2861 : Cycle with 6 vertices
まぁ、想定解法は別にあるのだと思いますが・・・
2 つめのトピックは、無向グラフの全域木の数え上げです。
上と同じように、次のグラフ
を例にしながら進めます。
まず、無向グラフ G のラプラシアン行列 ( Laplacian matrix ) を定義します。
G のラプラシアン行列とは、n × n の行列で、その ( i, j ) 成分が
・ i ＝ j のとき、頂点 i の次数
・ i ≠ j のとき、隣接行列の ( i, j ) 成分の -1 倍
であるもののことをいいます。
例のグラフのラプラシアン行列は
となります。
この行列の第 n 行、第 n 列を取り除いてできる n-1 × n-1 行列を L と置きます。
このとき、L の行列式 det(L) の値が G の全域木の個数になります。
これを行列木定理 ( Matrix-Tree Theorem ) と言います。
実際、例のグラフでは det(L) = 4 で、4 通りの全域木があります。
※ より詳しくは、「ラプラシアン行列の任意の余因子の値が等しくなり、その値が G の全域木の個数である」 ということが言えますが、わかりやすさを重視して上のように書きました。
ここでは証明はしませんが、ちょっと高度な線形代数の知識を使えば証明できます。
グラフ理論の本に載っているので、興味のある人は調べてみてください。
最後に、行列木定理を使って解ける例題を挙げておきます。
UVa 10766 : Organising the Organisation
SPOJ 2670 : Count Minimum Spanning Trees
2 問目は応用編です。ぜひチャレンジしてみてください。
ちょうどいい題材を選ぼうとしたら、いつの間にか counting の問題だけになってしまいました。
実は、次のような没案がありました。
・ Codeforces Beta Round #75 Div.1 C : Ski Base の解説 ( 接続行列の rank )
- 私自身が理解できなかったので没
・ マッチングと Tutte 行列
- 蟻本とかぶるので没
・ マトロイド
・ 最短経路問題、ネットワークフローなどを線形計画問題として見直す。双対性の話
- 競技プログラミングから離れすぎたので没
この記事では、「グラフと線形代数」 をテーマに、競技プログラミングに関係ありそうなトピックを 2 つ紹介します。
なるべく難しい線形代数を使わないものを選びました。
グラフの基礎的なこと、行列のかけ算、行列式の計算法を知っていれば読めると思います。
閉路！
1 つめのトピックは、グラフの交差しない閉路の数え上げです。
ここでは、自己ループ、多重辺をもたない無向グラフ G を考えます。
n を G の頂点数、m を G の辺数とします。
まずは、隣接行列 ( adjacency matrix ) の復習からはじめましょう。
G の隣接行列とは、n × n の行列で、その ( i, j ) 成分が
・ 頂点 i と j が辺で結ばれているときは 1
・ そうでないときは 0
であるもののことをいいます。
たとえば、次のグラフ
の隣接行列は
となります。
このグラフは以下でも例として登場します。
G の隣接行列を
とします。
A を 2 乗してみましょう。
A2 の ( i, j ) 成分は
です。
この式を注意深く見てみると、これは
aik = akj = 1 というのは、つまり 「頂点 i, k 間に辺があり、かつ頂点 k, j 間に辺がある」 ということです。
すなわち、A2 の ( i, j ) 成分は i, j を結ぶ長さ 2 の道の個数を表しています。
特に、A2 の ( i, i ) 成分は i から始まる長さ 2 の閉路の個数を表しています。
向きが違えば別々の閉路だと思って数えてしまっていることに注意しましょう。
たとえば、例のグラフでは
A2 の (0, 0) 成分 = 2
で、これは
0 → 1 → 0
0 → 2 → 0
という 2 つの閉路があることに対応しています。
一般に、
Ak の ( i, j ) 成分は i, j を結ぶ長さ k の道の個数
Ak の ( i, i ) 成分は i から始まる長さ k の閉路の個数
となります。
上記の方法は、同じ頂点を 2 回以上通るケースもカウントしています。
例のグラフでは、
頂点 0 から始まる長さ 4 の閉路は
0 → 1 → 0 → 1 → 0
0 → 1 → 0 → 2 → 0
0 → 1 → 2 → 1 → 0
0 → 1 → 2 → 3 → 0
0 → 2 → 0 → 1 → 0
0 → 2 → 0 → 2 → 0
0 → 2 → 3 → 1 → 0
0 → 2 → 3 → 2 → 0
と 8 個も見つかってしまいます。
これはあまり嬉しくないですね。
0 → 1 → 2 → 3 → 0
だけに興味があるわけです。
では、同じ頂点を 2 回以上通らないような閉路、つまり交差しない閉路だけを数え上げたい場合はどうすればいいでしょうか?
これは
閉路の長さ k が小さい場合のみ、いい方法が知られています。
どうすればいいでしょう？
がんばって場合わけ？
そのとおりです！
k = 3, 4, 5, 6 のときの公式を書いておきます。
長さ k の交差しない閉路の個数 ck は次のようになります。
ここで、
この結果は以下の論文やサイトから引用しました。
・ On the number of cycles in a graph
c3, c4, c5 の式が載っています。
有向グラフの場合も考察しています。
・ The number of fixed length cycles in an undirected graph. Explicit formulae in case of small lengths
c7 の公式と一般の ck の公式の作り方が載っています。
・ On interesting walks in a graph
交差しない閉路ではなく、交差しない道を数えている論文です。
・ Вывод явных формул для подсчёта циклов фиксированной длины в неориентированных графах
c6 の公式と一般の ck の公式の作り方が載っているようです。 ( 読めない )
・ Explicit formulae for counting k-cycles in undirected graphs - FlowProblem -
c3 から c12 までの公式を導いて、それを実装した C++ のソースコードが公開されています。
残念ながら公式は載せていないようで、ソースコードを解読しないといけません。
二部グラフの場合も考察しています。
論文では何やらすごそうなことをやっているように見えますが、閉路を分類してある程度まとめて数え上げているだけで、要は気合で場合分けしているにすぎません。
さて、せっかく計算方法を知ったので、この問題を解きましょう。
PKU 2861 : Cycle with 6 vertices
まぁ、想定解法は別にあるのだと思いますが・・・
全域木！
2 つめのトピックは、無向グラフの全域木の数え上げです。
上と同じように、次のグラフ
を例にしながら進めます。
まず、無向グラフ G のラプラシアン行列 ( Laplacian matrix ) を定義します。
G のラプラシアン行列とは、n × n の行列で、その ( i, j ) 成分が
・ i ＝ j のとき、頂点 i の次数
・ i ≠ j のとき、隣接行列の ( i, j ) 成分の -1 倍
であるもののことをいいます。
例のグラフのラプラシアン行列は
となります。
この行列の第 n 行、第 n 列を取り除いてできる n-1 × n-1 行列を L と置きます。
このとき、L の行列式 det(L) の値が G の全域木の個数になります。
これを行列木定理 ( Matrix-Tree Theorem ) と言います。
実際、例のグラフでは det(L) = 4 で、4 通りの全域木があります。
※ より詳しくは、「ラプラシアン行列の任意の余因子の値が等しくなり、その値が G の全域木の個数である」 ということが言えますが、わかりやすさを重視して上のように書きました。
ここでは証明はしませんが、ちょっと高度な線形代数の知識を使えば証明できます。
グラフ理論の本に載っているので、興味のある人は調べてみてください。
最後に、行列木定理を使って解ける例題を挙げておきます。
UVa 10766 : Organising the Organisation
SPOJ 2670 : Count Minimum Spanning Trees
2 問目は応用編です。ぜひチャレンジしてみてください。
余談
ちょうどいい題材を選ぼうとしたら、いつの間にか counting の問題だけになってしまいました。
実は、次のような没案がありました。
・ Codeforces Beta Round #75 Div.1 C : Ski Base の解説 ( 接続行列の rank )
- 私自身が理解できなかったので没
・ マッチングと Tutte 行列
- 蟻本とかぶるので没
・ マトロイド
・ 最短経路問題、ネットワークフローなどを線形計画問題として見直す。双対性の話
- 競技プログラミングから離れすぎたので没
