8 頂点の無向ランダム グラフで、頂点のペアの間にエッジが存在する確率は 1/2 です。長さ 3 の順序付けられていないサイクルの予想数は?
これが私がそれについて考えた方法です：
方法 1 基本的に、長さ 3 のサイクル (「順序付けされていない」頂点を任意の順序で取得できることを意味すると仮定しています) は三角形になります。
頂点の数 = v とし、そのようなサイクルの数を C とします。
n=3 の場合、C = 1
n = 4 の場合、c = 4. (2 つの対角線がある正方形。4 つの固有の三角形)。....
n>3 の場合、C(n) = (n-2) + (n-2)(n-3) + (n-4)、一般化。
これは、外側のエッジから始めて、それをベースとして可能な三角形を考えてみましょう。選択した最初のエッジ (2 つの頂点がそこに移動) については、三角形の 3 番目の点を選択する (n-2) 個の他の頂点があります。したがって、最初の項では (n-2) です。
次に、最後の項は、三角形のベースとして選択した最後の辺の左端と右端の三角形が、選択した最初の辺とその直前の辺によって既に取得されているためです。
中間項は、残りのエッジ数と可能な三角形の積です。
.--------.
. .
. .
. .
上記の 8 つの頂点のセットを使用すると、簡単に視覚的に考えることができます。(より良い図が必要な場合は、私が必要なだけやります!)。したがって、v=8 の場合、C(8) = 40 です。したがって、エッジの確率は 1/2 です。. .
方法 2 n 点からの三角形の数は nC3 です。ここで、C は「組み合わせ」です。しかし、これらのエッジの半分は存在しないと予想されます。. .
この点を超えて進む方法がわかりません。正しい方向へのヒントは素晴らしいでしょう。ところで、宿題の質問ではありません。