随机图中的循环数

Question

在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个顶点),有(n-2)个其他顶点来选择第三个三角形点.所以(n-2)在第一学期.

接下来,最后一个术语是因为我们选择以三角形为基础的最后一侧将最左边和最右边的三角形已经被我们选择的第一个边和它的前一个边.

中间项是剩余边数和可能三角形的乘积.

      .--------.

.                   .


.                   .

      .        .

通过上面的8个顶点集,人们可以在视觉上轻松地思考它.(如果需要更好的图表,我将做必要的!).因此对于v = 8,C(8)= 40.因此,边缘的概率是1/2...

方法2 来自n个点的三角形数是nC3,其中C是"组合".但是,预计这些边缘的一半不会存在...

我不确定如何超越这一点.任何正确方向的提示都会很棒.顺便说一句,这不是一个功课问题.

Answer 1

你有nC3可能的三角形.要显示三角形,必须存在所有三条边 - 因此出现特定三角形的概率为1/8.

然后是预期的三角形数量(nC3) / 8.

在你的情况下,8C3 / 8或7.