摘要
随机相交图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不等式)得到了类似结果.
The random intersection graph G (n,m,p) is deiined as tollows. Let V be a set of n nodes and M a set ot m elements. To each node v ∈ V , We assign a random subset Fv lohtain M , where Fv consists of elements in which each element is randomly and independently included with probability p from M. There is a edge between u and v if and only if Eu∩Fv≠Ф C. Efthymiou and P. G. Spirakis in [3] give sharp thresholds for the Hamilton cycle when re=n^a, where ct is different from 1. We get sharp threshold Pn= logn/n for Hamilton cycle when a = 1 using the second method. n
出处
《邵阳学院学报(自然科学版)》
2009年第2期11-12,共2页
Journal of Shaoyang University:Natural Science Edition