algorithm - 如果顶点随机连接，则连接图形所需的预期边数？

Question

我们随机选择两个顶点并将它们连接起来。那么当它变成连接时，图中预期的边数是多少？

我尝试使用归纳法解决它，但无法得出答案。解决这个问题的正确方法是什么？

Answer 1

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

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

The asymptotic number of labeled connected graphs with a given number of vertices and edges 中给出了连通图数的渐近公式爱德华·A·本德 (Edward A. Bender)E. Rodney Canfield、Brendan D. McKay(不要让我解释 :-))

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