唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

グラフ中の三角形や四角形(長さ3, 4の単純閉路)の数を求める

グラフ中の三角形や四角形(長さ3, 4の単純閉路)の数を求めたい
グラフはすべてループや多重辺を含まない無向の単純グラフとする

三角形の数を求める

グラフのどの頂点同士が結びついてるかを01であらわした隣接行列を\(A\)とすると

グラフ中の三角形の数は\(\frac{1}{6}\mathrm{tr}(A^3)\)で求められる

試しに次のグラフの三角形の数を求める
f:id:sucrose:20141221185809p:plain:h200
隣接行列は次のようになる

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\)通りの回り方がある)
f:id:sucrose:20141221201628p:plain

ソースコード

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