2

質問が述べているように。紙と鉛筆の結果に対応する式がわかりません。無向グラフで三角形の最大数を得る式を探しています。

三角形は、サイクルを形成するパス長 3 のノードの任意の接続として定義されます。たとえば、1<->2<->3<-> のグラフがある場合、1 は三角形です (<-> は無向接続です)。三角形とは何かが不明な場合は、2 ページ目の上部に、このコンテキストでの三角形とは何かを示す図がありますhttp://arxiv.org/pdf/1202.5230v1.pdf。

ありがとう

4

1 に答える 1

6

C(3,n) で十分です。基本的に、グラフ ノードのセット全体から 3 つの多数の組み合わせが必要です。

編集: omegamath が収益化を望んでいるため、リンクがダウンしているため、さらに説明する必要があります。(N!)/(M!*(N-M)!)C(m,n) は、N 個の異なる要素のうちの M 個の要素の可能な組み合わせの数で!あり、 は階乗演算、つまり に等しくなりN! = 1*2*3*...*Nます。

C(3,n) = (N*(N-1)*(N-2))/(1*2*3)

于 2012-10-05T08:21:40.340 に答える