algorithm - Google面试算法难题: expected size of the largest connected component in a random simple graph (N nodes, N边)？

提供的唯一初始输入参数是 N ，它表示图中

的节点数

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

确切有 N个节点配对，即。边缘列表的形式为{(1,a), (2,b), (3,c), ..., (N,[next available letter of the alphabet])}。条件是a!= 1，b!= 2，c!= 3等，但除此之外，a，b，c，...可以取从1到 N 包括

的任何值

可以通过均匀概率分布

描述与其他节点形成边缘的节点n

搜索每个由 N个节点和 N个边构成的有效图，找到最大连接组件 S的大小

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

问题是:在构造的所有此类有效图中， S 的期望值是多少？

我想知道思考/分析/解决这个问题的有效方法，它可以处理 N ，范围从2到50。一些代码说明将有助于我的理解。

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

Python

C/C++

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

到目前为止的输出

至于格式，例如对于“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的示例:

总共有4个节点的 81 可能的边分配(从 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 S == 4) * 4 + (fraction of all 81 instances where S == 2) * 2 = 106/27 来计算 S 的期望值-因为 S 的唯一值是2。

{((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}

最佳答案

这不是一个解决方案，但是有一些观察结果。

首先，具有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的期望大小。

关于algorithm - Google面试算法难题: expected size of the largest connected component in a random simple graph (N nodes, N边)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28527891/