随机生成图中的“连通性”

Question

过去3-4天，我一直在玩python中的实现图和相关结构。除此之外，我有一个简单的函数来生成随机图，即其中两个顶点以给定概率连接的图。然后使用graphviz显示图形。无论如何，在上述活动过程中，我注意到，在某种概率以上，几乎所有具有给定数量顶点的图都始终连接在一起。几个问题：

• 是否还有其他“属性”经历了类似的“过渡”？
• 我相信别人必须更严格地检查这整个事情。任何指针？

Answer 1

好问题！

实际上，随机图的主题是众所周知的，可以追溯到鄂尔多斯和仁义，1959

阈的观察也优异。还有其他一些共享这种“阈值”现象的图表属性。

实际上，大多数“单调”属性都证明了这个“阈值”属性。这已经被Erd ö和R e nyi（根据下面提到的书）证明。

如果n个顶点上的图H具有P意味着H（即n的顶点）上的任何超图G（即H是G的子图），则属性P是单调的。例如，哈密尔顿周期就是这样一个属性。连通性是另一个。

注意：这种单调性的定义可能与图论中的其他文本不同。我提到下面这本书中提供的一个。

B＆eacute; la Bollob＆aacute;的书Random Graphs应该让你开始。有关具有“阈值”的单调属性的讨论，请参见第40页。不过，我必须警告你，那本书使用了一些非常重的数学。