グラフ中の三角形や四角形(長さ3, 4の単純閉路)の数を求めたい
グラフはすべてループや多重辺を含まない無向の単純グラフとする
三角形の数を求める
グラフのどの頂点同士が結びついてるかを01であらわした隣接行列を\(A\)とすると
グラフ中の三角形の数は\(\frac{1}{6}\mathrm{tr}(A^3)\)で求められる
試しに次のグラフの三角形の数を求める
隣接行列は次のようになる
0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0
これを\(3\)乗すると次のようになり\(\frac{1}{6}\mathrm{tr}(A^3) = 1\)となる
2 3 4 1 3 2 4 1 4 4 2 3 1 1 3 0
これがなぜうまくいくかというと隣接行列の\(k\)乗はある頂点からある頂点への長さ\(k\)のウォークの個数を表しているから。
なのでたとえば隣接行列の\(k\)乗の\((i, i)\)成分を\(a_{ii}^{(k)}\)とすると、これは頂点\(i\)から出発して、頂点\(i\)へ戻ってくる長さ\(k\)の閉路の個数となる
つまり\(\frac{1}{6}\mathrm{tr}(A^3)\)という式はそれぞれの頂点についての長さ\(3\)の閉路の数の総和を\(6\)で割っていることになる
\(6\)で割る理由は、三角形のそれぞれ\(3\)個の頂点と右回り左回りの\(2\)種類について重複してカウントしているからである
四角形の数を求める
四角形の場合は次の式\(\frac{1}{8}(\mathrm{tr}(A^4) - 2q - 4\sum_{i < j} a_{ij})\)で求められる
ここで\(q\)はグラフの辺の数、\(a_{ij}^{(2)}\)は隣接行列の\(2\)乗\(A^2\)の\((i, j)\)成分である
なぜ三角形の時のように簡潔な式にならないかというと、長さ\(4\)の閉路には同じ場所を\(2\)回通るような閉路が含まれるからである
なのでその分を\(\mathrm{tr}(A^4)\)から引いている
\(-2q\)の部分は同じ辺を\(2\)往復する分である(どっちを始点にするかで\(2\)通りある)
\(- 4\sum_{i < j} a_{ij}\)の部分は隣り合った\(2\)辺を回る分である(以下の\(4\)通りの回り方がある)
参考
今回の話は主にこの論文の内容の一部
上2つの記事は長さ\(5\)以上の単純閉路についての式も載っている
ソースコード
NumPyを使って三角形の数を求めるコードを書いたので一応載せとく
import numpy as np import numpy.linalg as la A = np.array([[0, 1, 1, 0], [1, 0, 1, 0], [1, 1, 0, 1], [0, 0, 1, 0]]) A3 = la.matrix_power(A, 3) print A3 print A3.trace() / 6