Google采访算法难题:随机简单图中最大连通分量的预期大小(N个节点,N个边)？

Question

Google采访算法难题:随机简单图中最大连通分量的预期大小(N个节点,N个边)？

Ade*_* Ho 7 language-agnostic algorithm graph-theory combinatorics

给定N个节点,N个边缘和均匀边缘概率p的随机简单图,最大连通分量的预期大小是多少？

提供的唯一初始输入参数是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
Foreach这样的有效图由N个节点和N个边构成,找到最大连通分量S的大小
通过连接组件,这被定义为最大的群集/节点组,其中连接组件中的每个节点可以到达/可从同一连接组件中的每个其他节点到达

问题是:在构建的所有这些有效图中,S的期望值是多少？

我想知道一种有效的方法来思考/分析/解决这个问题,可以处理从2到50(包括2和50)的N. 一些代码可以帮助我理解.

我编写了以下源代码,天真地强调了可能性,希望从那里找到一个模式.管理以N = 9适应这些:

蟒蛇
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

Run Code Online (Sandbox Code Playgroud)

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

示例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小号== 4) * 4 + (fraction of all 81 instances where小号== 2) * 2 =二十七分之一百〇六 -因为唯一值小号需要是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}

Run Code Online (Sandbox Code Playgroud)

Answer 1

Rer*_*ito 1

我将从有关该问题的一些假设开始：

\n

连接分量的含义：考虑图的变换，其中每条边变得无向。如果在变换（无向）图中两个顶点之间存在路径，则认为两个顶点是连接的。
如果存在连接两个顶点i 、 j 的（有向）边 (i, j )，则仍然可以有另一条从j开始的（有向）边(j,i)。

\n

\n
C(k,n)将表示二项式系数“n 选择 k”。
\n
分析
\n
令G _i (N)为图G(N)的i 个顶点的子集（有C(i,N)个这样的子集）。仅当满足以下两个条件时，G _i (N)才能定义大小为i的连通分量：
\n
\n
从G _i (N)的顶点开始的边以G _i (N)的元素结束：事件e _inGi
\n
从G \\ G _i (N)的顶点开始的边以G \\ G _i (N)结束：事件e _outGi
\n
\n
这两个事件（e _inGi和 e _outGi）是独立的，因为在图构建期间独立选择边。
\n
此外， G _i中至多可以有一个环（即形状为(i,j),(j,k),...,(l,m),(m,i) 的边）。超过一个循环将导致我们考虑的i顶点中有多个连通分量，因为从给定顶点开始只有一条边。这定义了事件e _2-cycles。
\n
因此，具有由子集G _i（事件e _i-cc ）定义的大小为i的连通分量的总体概率为：
\n
\n
p(e _i-cc ) = p(e _inGi ).p(e _2-周期|e _inGi )。p(e_输出Gi )
\n
\n
具有大小至少为 i的连通分量与具有大小为i的连通分量相同，只不过这次我们删除了事件e _outGi施加的约束。这定义了事件e_最少，i
\n
\n
计算概率
\n
在一组孤立的K个顶点中至少有两个循环的概率为：
\n
\n
\n
\n\n
证明：要定义两个循环，我们需要两组顶点，每个顶点至少包含两个顶点。令k ₁和k ₂为这些集合中的顶点数。
\n
在一组顶点上定义循环相当于选择循环顺序并将顶点链接起来。给定定义循环顺序的集合1（分别为2）的常规顺序，存在k ₁（分别为k ₂）其他顺序导致相同的循环顺序（它们属于相同的等价类）。因此有(k ₁ -1)！（分别为k ₂ -1）！) 第 1 组（或第 2 组）的循环订单。这个语句解释了(X-1)！公式的一点点。
\n
我们在考虑的K个元素中选取i 个元素( i > 3)。我们感兴趣的是用这i 个元素构建两个循环（不管剩余的K - i 个元素）。由于我们忽略了剩余部分，因此我们必须使用平衡因子来补偿我们将对相同周期进行多次计数的事实（因此是位）。我们将这i 个元素分成两个集合（因此是 sum ）。我们在i中取出j 个元素。这里，第i个元素中没有剩余元素。然而，在j = ij 的情况下，我们将对每对周期精确计数两次，因此我们使用克罗内克符号 ( )进行平衡1 + C(i, K-i)j=2..i/2delta(i,j) = 1 iif (i = j)
\n
我们有两组，现在我们计算周期数 ( (k ₁ -1) !. k ₁ -1)！其中k ₁ = j和k ₂ = ij ）并将它们除以在i顶点上构建边的可能方式的数量( (K-1)**i)
\n
注意：对此概率的同行评审将不胜感激。
\n
\n
我们现在可以计算在这样一个由N 个顶点和边组成的图中具有基数K的连通分量的概率：
\n
\n
\n
\n\n
注：第一项表示 K 个顶点的选择。奇数1 + C(...)部分是一个平衡因子，用于解释给定 K 组合 X，在考虑其他一些 K 组合时，X 将出现在“NK”一侧。
\n
以下两项表示图的 K 个选定顶点与其余 NK 个顶点之间的相互隔离度。
\n
\n
类似地，具有大小至少为 K 的连通分量的概率与具有大小为K的连通分量相同，只是我们删除了与之前描述的事件e _outGi对应的项：
\n
\n
\n
\n\n
\n
到目前为止，一切都很好。问题是……图中可能有多个连通分量！所以我们不能简单地对上面的公式求平均值......
\n
具有大小为i 的最大连通分量的概率可以使用p _k (N)概率来表示：它是以下事件的合取：
\n
\n
具有基数i的连通分量
\n
在Ni剩余顶点中不具有至少 i+1基数的连通分量。
\n
\n
这两个事件是独立的，因为基数i的连通分量与图的其余部分不相交。
\n
因此，最大连通分量的大小为K的概率为：
\n
\n
p _max (K,N) = p _CCeq (K,N)。(1 - p _CCsup (K+1,NK))
\n
\n
剩下要做的就是平均这个概率。在具有N 个顶点和边的随机图中，最大连通分量的预期大小S(N)为：
\n
\n
S(N) = \xce\xa3 _{2\xe2\x89\xa4K\xe2\x89\xa4N} K.p_最大值(K,N)
\n
\n
\n
快速示例
\n
令N = 5。我们有：
\n
\n
p_最大(1,5) = 0
\n
p_最大(2,5) = 0
\n
p _max (3,5) = C(3,5).(1/2) ³ .(1/4) ² = 10/(2.4 ³ ) = 80/(4 ⁵ )
\n
p_最大(4,5) = 0
\n
p _max (5,5) = (1 - p _2cycles (5)) = 1 - 80/(4 ⁵ )
\n
\n
因此，p _max (k,5)始终为 0，除了k = 3和k = 5 。\n循环公式给出了 4 ^{5 种}可能排列中的 20 对 2-循环/3-循环和 15 对 2-循环/2-循环超过 4 ^{4 种}可能的排列。因此总和为 80/(4 ⁵ )，即p _max (3,5)。
\n
\n
我想您现在可以使用计算机从该公式中获取实际值？:)
\n
免责声明：我手动检查了 N=3,4,5 的 2 周期公式，它似乎成立得很好。然而，外部审查会非常有帮助。请注意，这些计算是根据我的答案开头的假设进行的。
\n
再次感谢@DavidEisenstat 的有用评论，这导致了这个更严格（并且希望是正确的）答案。
\n

在没有论证为什么相应事件是独立的情况下乘以这样的概率通常是一个坏兆头。 (2认同)

归档时间：	11 年，3 月前
查看次数：	1468 次
最近记录：	6 年，8 月前