algorithm - 谷歌面试算法拼图 : expected size of the largest connected component in a random simple graph (N nodes, N 边)？

Question

Given a random simple graph of N nodes, N edges, and a uniform edge probability p, what is the expected size of the largest connected component?

提供的唯一初始输入参数是 电话 ，表示图中的节点数

该图很简单，这意味着不允许包含任何自环

正好有电话 节点配对，即。边缘列表的格式为 {(1,a), (2,b), (3,c), ..., (N,[next available letter of the alphabet])} .条件是 a!=1, b!=2, c!=3 等等，但除此之外，a,b,c,... 可以取从 1 到 的任何值。电话 全包

与某个其他节点形成边的节点 n 可以用均匀概率分布

来描述。

Foreach 这种由 构成的有效图电话 节点和 电话 边，找到最大连通分量的大小小号

通过连接组件，这被定义为最大的集群/节点组，其中连接组件中的每个节点都可以到达/可以从同一连接组件中的每个其他节点访问

问题是:在构建的所有这些有效图形中， 的期望值是多少？小号 ?

我想知道一种思考/分析/解决这个问题的有效方法可以处理 电话 从 2 到 50 不等。一些用于说明的代码将有助于我的理解。

我编写了以下源代码来天真地暴力破解可能性，希望从中找到一种模式。设法起床 N = 9用这些:

Python

C/C++

两者都尝试根据问题中指定的标准生成所有可能的排列，然后计算 小号 对于通过 BFS 生成的每个图。

到目前为止的输出

至于格式，例如。对于“ N=4: {2:3,4:78} 106/27”这一行，这意味着有3张图最大分量=2，78张图最大分量=4，所以最后的 answer = (3/(78+3))*2 + (78/(78+3))*4 = 106/27 .

N=2: {2:1} 2/1
N=3: {3:8} 3/1
N=4: {2:3,4:78} 106/27
N=5: {3:80,5:944} 155/32
N=6: {2:15,3:640,4:1170,6:13800} 17886/3125
N=7: {3:840,4:21840,5:19824,7:237432} 38563/5832
N=8: {2:105,3:17920,4:229320,5:422912,6:386400,8:4708144} 6152766/823543
N=9: {3:153440,4:786240,5:9634464,6:9273600,7:8547552,9:105822432} 17494593/2097152

编辑: 刚刚发现这个 OEIS sequence #A000435给出了具有 N 个节点和最大尺寸分量 = N 的图数量的答案(公式/列表最多 N=18)。这与我的蛮力输出完全一致，例如。对于 N=9，有 105822432 个图的最大连通分量 = 9。不确定这是否有帮助 - 那里给出的公式之一用于推导出更大的 N 是 a(n) = (n-1)! * Sum (n^k/k!, k=0..n-2) Python implementation
N = 4 的示例:

共有 81 4 个节点的可能边分配(从 1 到 N 的基于 1 的索引)。

以下示例输出的格式为: ((1, 2), (2, 1), (3, 1), (4, 1)): 4表示节点 1 和 2、节点 2 和 1、节点 3 和 1 以及节点 4 和 1 之间存在边。假设边是无向/双向的。对于这样的图，所有 4 个节点 {1,2,3,4} 只有一个连通分量，因此最大(唯一)连通分量的大小为 4。

生成此列表后，预期值为 小号 可以通过 (fraction of all 81 instances where 计算 小号 == 4) * 4 + (fraction of all 81 instances where 小号 == 2) * 2 = 106/27 - 因为唯一的值 小号 需要 2,4。

{((1, 2), (2, 1), (3, 1), (4, 1)): 4,
 ((1, 2), (2, 1), (3, 1), (4, 2)): 4,
 ((1, 2), (2, 1), (3, 1), (4, 3)): 4,
 ((1, 2), (2, 1), (3, 2), (4, 1)): 4,
 ((1, 2), (2, 1), (3, 2), (4, 2)): 4,
 ((1, 2), (2, 1), (3, 2), (4, 3)): 4,
 ((1, 2), (2, 1), (3, 4), (4, 1)): 4,
 ((1, 2), (2, 1), (3, 4), (4, 2)): 4,
 ((1, 2), (2, 1), (3, 4), (4, 3)): 2,
 ((1, 2), (2, 3), (3, 1), (4, 1)): 4,
 ((1, 2), (2, 3), (3, 1), (4, 2)): 4,
 ((1, 2), (2, 3), (3, 1), (4, 3)): 4,
 ((1, 2), (2, 3), (3, 2), (4, 1)): 4,
 ((1, 2), (2, 3), (3, 2), (4, 2)): 4,
 ((1, 2), (2, 3), (3, 2), (4, 3)): 4,
 ((1, 2), (2, 3), (3, 4), (4, 1)): 4,
 ((1, 2), (2, 3), (3, 4), (4, 2)): 4,
 ((1, 2), (2, 3), (3, 4), (4, 3)): 4,
 ((1, 2), (2, 4), (3, 1), (4, 1)): 4,
 ((1, 2), (2, 4), (3, 1), (4, 2)): 4,
 ((1, 2), (2, 4), (3, 1), (4, 3)): 4,
 ((1, 2), (2, 4), (3, 2), (4, 1)): 4,
 ((1, 2), (2, 4), (3, 2), (4, 2)): 4,
 ((1, 2), (2, 4), (3, 2), (4, 3)): 4,
 ((1, 2), (2, 4), (3, 4), (4, 1)): 4,
 ((1, 2), (2, 4), (3, 4), (4, 2)): 4,
 ((1, 2), (2, 4), (3, 4), (4, 3)): 4,
 ((1, 3), (2, 1), (3, 1), (4, 1)): 4,
 ((1, 3), (2, 1), (3, 1), (4, 2)): 4,
 ((1, 3), (2, 1), (3, 1), (4, 3)): 4,
 ((1, 3), (2, 1), (3, 2), (4, 1)): 4,
 ((1, 3), (2, 1), (3, 2), (4, 2)): 4,
 ((1, 3), (2, 1), (3, 2), (4, 3)): 4,
 ((1, 3), (2, 1), (3, 4), (4, 1)): 4,
 ((1, 3), (2, 1), (3, 4), (4, 2)): 4,
 ((1, 3), (2, 1), (3, 4), (4, 3)): 4,
 ((1, 3), (2, 3), (3, 1), (4, 1)): 4,
 ((1, 3), (2, 3), (3, 1), (4, 2)): 4,
 ((1, 3), (2, 3), (3, 1), (4, 3)): 4,
 ((1, 3), (2, 3), (3, 2), (4, 1)): 4,
 ((1, 3), (2, 3), (3, 2), (4, 2)): 4,
 ((1, 3), (2, 3), (3, 2), (4, 3)): 4,
 ((1, 3), (2, 3), (3, 4), (4, 1)): 4,
 ((1, 3), (2, 3), (3, 4), (4, 2)): 4,
 ((1, 3), (2, 3), (3, 4), (4, 3)): 4,
 ((1, 3), (2, 4), (3, 1), (4, 1)): 4,
 ((1, 3), (2, 4), (3, 1), (4, 2)): 2,
 ((1, 3), (2, 4), (3, 1), (4, 3)): 4,
 ((1, 3), (2, 4), (3, 2), (4, 1)): 4,
 ((1, 3), (2, 4), (3, 2), (4, 2)): 4,
 ((1, 3), (2, 4), (3, 2), (4, 3)): 4,
 ((1, 3), (2, 4), (3, 4), (4, 1)): 4,
 ((1, 3), (2, 4), (3, 4), (4, 2)): 4,
 ((1, 3), (2, 4), (3, 4), (4, 3)): 4,
 ((1, 4), (2, 1), (3, 1), (4, 1)): 4,
 ((1, 4), (2, 1), (3, 1), (4, 2)): 4,
 ((1, 4), (2, 1), (3, 1), (4, 3)): 4,
 ((1, 4), (2, 1), (3, 2), (4, 1)): 4,
 ((1, 4), (2, 1), (3, 2), (4, 2)): 4,
 ((1, 4), (2, 1), (3, 2), (4, 3)): 4,
 ((1, 4), (2, 1), (3, 4), (4, 1)): 4,
 ((1, 4), (2, 1), (3, 4), (4, 2)): 4,
 ((1, 4), (2, 1), (3, 4), (4, 3)): 4,
 ((1, 4), (2, 3), (3, 1), (4, 1)): 4,
 ((1, 4), (2, 3), (3, 1), (4, 2)): 4,
 ((1, 4), (2, 3), (3, 1), (4, 3)): 4,
 ((1, 4), (2, 3), (3, 2), (4, 1)): 2,
 ((1, 4), (2, 3), (3, 2), (4, 2)): 4,
 ((1, 4), (2, 3), (3, 2), (4, 3)): 4,
 ((1, 4), (2, 3), (3, 4), (4, 1)): 4,
 ((1, 4), (2, 3), (3, 4), (4, 2)): 4,
 ((1, 4), (2, 3), (3, 4), (4, 3)): 4,
 ((1, 4), (2, 4), (3, 1), (4, 1)): 4,
 ((1, 4), (2, 4), (3, 1), (4, 2)): 4,
 ((1, 4), (2, 4), (3, 1), (4, 3)): 4,
 ((1, 4), (2, 4), (3, 2), (4, 1)): 4,
 ((1, 4), (2, 4), (3, 2), (4, 2)): 4,
 ((1, 4), (2, 4), (3, 2), (4, 3)): 4,
 ((1, 4), (2, 4), (3, 4), (4, 1)): 4,
 ((1, 4), (2, 4), (3, 4), (4, 2)): 4,
 ((1, 4), (2, 4), (3, 4), (4, 3)): 4}

Answer 1

这还不是解决方案，而是一些观察结果。

首先有 n 个边和 n 个顶点，每个顶点都连接到除自身之外的其他顶点，该图中大小为 k 的任何强连通分量必须恰好有 k 个边。这来自

任何大小为 k 的 SCC 必须至少有 k-1 条边。在这个图中，任何 SCC 都不可能恰好有 k-1 条边，因为如果是这种情况，那么 SCC 中必须有一个顶点连接到另一个不在 SCC 中的顶点，因此使这个 SCC 的假设无效大小 k。

在这个图中也不可能任何 SCC 有超过 k+1 条边，因为每个顶点都恰好连接到另一个顶点。

现在假设我们要计算这个问题中构造的有效图的总数，并且 dp[n][k]是具有 n 个顶点和最大 SCC 大小为 k 的有效图的总数。然后 dp[n][k]是

以某种方式从 n 个顶点中选择 k 个顶点并形成 SCC，然后

剩余的 n-k 个顶点的 SCC 不得大于 k。

因此 DP 公式变为:

dp[n][k]=C(n,k)*dp[n-k][k] + 
         C(n,k)*dp[n-k][k-1] +
         C(n,k)*dp[n-k][k-2] + 
         ...
         C(n,k)*dp[n-k][2] +
         C(n,k)*dp[n-k][1]

哪里 C(n,k)是 n!/[(n-k)!k!]
(我不确定这是否正确，但希望在正确的方向上)

n个顶点的有效图总数为 (n-1)**(n-1) .最大 SCC 的期望大小可以从期望的基本原理计算出来。