关于随机相交图中Hamilton圈的门限函数的注记

随机相交图G(n,m,p)的定义如下:记V为一n顶点集.M为一m个元素的集合.对每个顶点v∈V,赋予一随机子集Fv■M,其中从M中独立以概率p选取每个元素构成Fv,顶点u和v之间有边相连当且仅当Fu∩Fv≠Φ.当m=na,a≠1时.C.Efthymiou和P.G.Spirakis得到了G(n,m,p)中Hamilton圈的门限函数.对于a=1情形,本文利用二阶矩方法(Chebyshev不等式)得到了类似结果.

次临界随机相交图的最大连通分支

本文研究次临界情形下(即顶点度数的期望小于1)随机相交图G(n,m,p)的最大连通分支的大小.设m=[n^(r)].当r>1时,随机相交图G(n,m,p)的最大连通分支和最大树分支大小都为Θ(log n),并具有相同形式的弱大数定律;当r=1时,最大连通分支不再是树分支,但最大连通分支和最大树分支的大小也是Θ(log n);当0<r<1时,最大树分支的大小为o(log n),而最大连通分支的大小为Θ(np log n).

无线传感器网络孤立点数目的近似分布

利用微积分计算和Brun's筛法,得到了部署在在单位正方形区域上服从均匀分布n个传感器节点构成的无线安全传感器网络孤立点数目的近似分布.我们证明了对于某个常数c,如果任意两个传感器节点之间最大通信半径rn满足nπr_n^2p'=ln n+c,这里p'是两个传感器节点至少有一个公共密钥的概率,则无线传感器网络孤立点数目近似服从参数为e^(-c)的Poisson分布.