6

在 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是“组合”。但由于这些边缘中的一半预计不会存在。. .

我不知道如何超越这一点。任何正确方向的提示都会很棒。顺便说一句，这不是作业问题。

4

2 回答 2

8

你有 nC3 个可能的三角形。要出现一个三角形，所有三个边都必须存在 - 所以特定三角形出现的概率是 1/8。

则预期的三角形数为(nC3) / 8。

在你的情况下，8C3 / 8或 7。

于 2013-02-10T18:33:14.840 回答
0

所以你已经给出了 n 个顶点，现在你有 nC1 方法来选择第一条边。存在该边的概率为 1/2。现在在左 n-1 边中，我们可以选择 (n-1)C1 方式，概率为 1/2，类似地，第三边与 (n-2)C1 的概率为 1/2所以同时这可以做到{nC1*(1/2) (n-1)C1 (1/2)*(n-2)C1*1/2}/3! 我们必须除以 3！因为它要求无序。

于 2018-12-17T06:15:28.287 回答