我们随机选择两个顶点并将它们连接起来。
那么当图连接起来时,图中的预期边数是多少?
我尝试使用归纳法解决它,但无法找到答案。
解决这个问题的正确方法是什么?
对于给定数量的顶点n并选择边的数量,您就可以得到图连通性的概率,即连通图与所有图的比例。
所有图的个数是以下组合的个数m over n * (n - 1).
连通图数量的渐近公式如下具有给定数量的顶点和边的标记连通图的渐近数量 http://onlinelibrary.wiley.com/doi/10.1002/rsa.3240010202/abstract作者:爱德华·A·本德,
E. Rodney Canfield、Brendan D. McKay(不要让我解释:-))
最后,您必须指定“预期数字”的含义 - 您必须选择一个概率阈值(例如 95%)并搜索m其中该公式给出的概率高于该阈值。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)