随机图理论

我叔叔的一．随机图过程的基本概念 随机图过程就是图的按照符合某种概率分布的随机规则生长的过程。给定一个初始图，在某时刻t记该图为，以某种概率取一条不在现在的图中的边或边的集合加入该图中,直到没有边可加为止。中止时间称为nature stop time，最后的图叫band graph,记t时刻加的边或边的集合为，这样一个过程与随机算法有关系。下面有一个随机图过程的例子。 例⒈标准随机图过程 假定是一个空图，在某一时刻，任取一条不在现在的图中的边加进该图，记该图为,如此下去直到得到一个完全图为止。每条被取边的概率都是一样的。 研究随机图过程通常考虑渐近性。所谓渐近性主要是指图的顶点个数趋于无穷时，该过程的性质。尤其是最后的图的性质。实际上我们是在处理一个随机过程的序列。 设是一个与随机图过程有关的事件，说事件是渐近的几乎肯定的成立假如它的概率极限趋近于1。 二．随机d过程 令d是一个固定的数，让初始图为空图。每次取两个度数小于d的顶点加入图中并且将它们连起来。假设每次取得的这样的对的概率相等（当然可以不等，但此时研究起来很有难度）。当没有满足这样的条件的顶点时停止。这样的图称为Bmaximal。将d过程看成一个序列。 现在有两个问题: 问题一 ：问最后一个图非饱和顶点的分布情况？ 问题二 ：该过程最后是否几乎肯定的得到一个连通图？ 对于第一个问题，有如下定理（1992年）： 定理1 给定固定常数d，对于最后的图几乎可以肯定为正则图（每点度为d）或者几乎正则图（就是说有且有一个点的度为d-1而其他的度均为d）。 这个结果是用微分及组合的方法得到的。 定理2 当d≥3时渐近的几乎可以肯定的最后的图是一个连通图。 这个结果是2000年得到的。但是d=2时结果不对。这时问题变成一个Hamilton问题。那么我们要问d=2时以多大的概率生成一个连通图或者Hamilton图？ 下面是一些与上面有关的结果。 定理3 对于l≥3的固定正整数，那么在l随机过程里，最终的图的圈的个数服从泊松分布。 定理4 d=2时以概率 （其中c为一个常数）生成一个连通图或者Hamilton图。 定理5 设X n 表示最后一个图中圈的个数，则＝(1/2)Log+常数+ε（ε为随机误差）。