anu*_*pam 1 python algorithm graph
在过去的3-4天里,我一直在玩python中实现图形和相关结构.除此之外,我还有一个简单的函数来生成随机图,即两个顶点以给定概率连接的图.然后使用graphviz显示图形.
无论如何,在上述活动过程中,我注意到,在一定的概率之上,几乎所有具有给定顶点数的图都始终是连通的.几个问题:
小智 5
好问题!
事实上,随机图的主题是众所周知的,可以追溯到1959年的鄂尔多斯和仁义.
阈值的观察也很好.图的其他属性共享这种"阈值"现象.
实际上,已经证明大多数"单调"属性都具有这种"阈值"属性.Erdös和Rényi证实了这一点(根据下面提到的那本书).
如果n个顶点上的图H具有P意味着H的任何超图G(在n个顶点上)(即H是G的子图)也具有P,则属性P是单调的.例如,哈密顿循环是一个这样的属性.连通性是另一个.
注意:单调性的这种定义可能与图论的其他文本不同.我提到下面的书中提供的那个.
BélaBollobás的随机图谱书应该可以帮到你.有关具有"阈值"的单调属性的讨论,请参见第40页.我必须警告你,那本书使用了一些相当重的数学.