随机生成图的连通性

Question

在过去的3-4天里，我一直在处理python中的实现图和相关结构。除其他外，我还有一个琐碎的函数来生成随机图，即两个顶点与给定概率相关联的图。然后使用graphviz显示这些图形。

无论如何，在进行上述活动的过程中，我注意到在一定概率上，几乎所有给定顶点数的图都是连通的。几个问题：

还有其他经过类似"transition"?

• I的“属性”--
• --肯定是其他人更严格地检查过这件事情。有什么指示吗？

Answer 1

问得好！

事实上，随机图的主题是众所周知的，可以追溯到鄂尔多斯和Renyi，1959年。

对阈值的观察也很好。图的其他特性与这种“阈值”现象有共同之处。

事实上，已经证明了大多数“单调”属性都具有这种“阈值”属性。Erd s和Rényi (根据下面提到的书)证实了这一点。

一个性质P是单调的，如果n个顶点上的图H包含H的任意超图G(n个顶点)(即H是G的一个子图)也有P。例如，Hamiltonian圈就是这样的性质之一。连接是另一回事。

注:单调性的定义可能不同于图论上的其他文本.我指的是以下书中所提供的那一项。

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