MULTICYCLIC COMPONENTS IN A RANDOM GRAPH PROCESS

被引：17
作者：
JANSON, S
机构：
[1] Department of Mathematics, Uppsala University, Uppsala, S-751 06
来源：
RANDOM STRUCTURES & ALGORITHMS | 1993年 / 4卷 / 01期
关键词：
D O I：
10.1002/rsa.3240040105
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
A limit theorem is obtained for the number of components with more than one cycle that are created during the evolution of a random graph process. In particular, it is shown that the probability that the process never contains more than one such component is about 0.87.
引用
收藏
页码：71 / 84
页数：14
相关论文
共 10 条
[1]  
Bollobas B., 1985, RANDOM GRAPHS
[2]  
Britikov V.E, 1989, DISKRET MAT, V1, P121
[3]   THE 1ST CYCLES IN AN EVOLVING GRAPH [J].
FLAJOLET, P ;
KNUTH, DE ;
PITTEL, B .
DISCRETE MATHEMATICS, 1989, 75 (1-3) :167-215
[4]   POISSON CONVERGENCE AND POISSON PROCESSES WITH APPLICATIONS TO RANDOM GRAPHS [J].
JANSON, S .
STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 1987, 26 (01) :1-30
[5]  
JANSON S, IN PRESS BIRTH GIANT
[6]  
JANSON S, 1990, RANDOM STRUCT ALGOR, V1, P15
[7]  
Kallenberg O., 1983, RANDOM MEASURES
[8]  
KOLCHIN VF, 1986, THEOR PROBAB APPL, V31, P439
[9]  
LUCZAK T, IN PRESS STRUCTURE R
[10]   PROBABILITY OF CONNECTEDNESS OF A RANDOM GRAPH GM(T) [J].
STEPANOV, VE .
THEORY OF PROBILITY AND ITS APPLICATIONS,USSR, 1970, 15 (01) :55-+
1