如果顶点是随机连接的,则连接图形所需的预期边数？

Question

我们随机选择两个顶点并连接它们.那么连接时图中边缘的预期数量是多少？

我尝试使用归纳法解决它,但无法达成答案.这个问题的正确方法是什么？

Answer 1

对于给定的顶点数n和选定的边数，您可以得到图连通性的概率，即连通图与所有图的比例。

所有图的数量是m与n * ( n - 1)的组合数。

连通图数量的渐近公式在 Edward A. Bender、E. Rodney Canfield、Brendan D. McKay 的《具有给定数量的顶点和边的标记连通图的渐近数量》中给出（不要让我解释： -) )

最后，您必须指定“预期数字”的含义 - 您必须选择一个概率阈值（例如 95%）并搜索 m，其中该公式给出的概率高于该阈值。