8

n を指定すると、ランダムな nxn 隣接行列を生成する関数を作成しました。行列で表されるグラフの三角形の数を数える方法があるかどうか疑問に思っていました。

4

1 に答える 1

15

隣接行列Aのn乗の ( i , j ) 要素は、iで始まりjで終わる長さnのパスの数をカウントします。

三角形は、同じノードで開始および終了する長さ 3 のパスです。したがって、Aの 3 乗のi番目の対角要素は、ノードの 1 つとしてiを含む三角形の数を数えます。

それぞれの三角形は、グラフ内の 3 つのノードごとに 2 回カウントされます (時計回りと反時計回りの各方向に 1 回)。

したがって、異なる三角形の数は ですtrace(A^3) / 6。

于 2013-07-19T09:02:28.740 に答える