ISSN:1042-9832    

DOI:10.1002/rsa.3240040302

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractLimiting distributions are derived for the sparse connected components that are present when a random graph onnvertices has approximately 1/2nedges. In particular, we show that such a graph consists entirely of trees, unicyclic components, and bicyclic components with probability approaching √2/3 cosh √5/18 ≈ 0.9325 asn→∞. The limiting probability that it is consists of trees, unicyclic components, and at most one another component is approximately 0.9957; the limiting probability that it is planar lies between 0.987 and 0.9998. When a random graph evolves and the number of edges passes 1/2n, its components grow in cyclic complexity according to an interesting Markov process whose asymptotic structure is derived. The probability that there never is more than a single component with more edges than vertices, throughout the veolution, approaches 5 π/18 ≈ 0.8727. A “uniform” model of random graphs, which allows self‐loops and multiple edges, is shown to lead to formulas that are substanitially simpler than the analogous formulas for the classical random graphs of Erdõs and Rényi. The notions of “excess” and “deficiency,” which are significant characteristics of the generating function as well as of the graphs themselves, lead to a mathematically attractive structural theory for the uniform model. A general approach to the study of stopping configurations makes it possible to sharpen previously obtained estimates in a uniform manner and often to obtain closed forms for the constants of interest. Empirical results are presented to complement the analysis, indicating the typical behavior when n is near 2oooO.

ISSN:1042-9832    

DOI:10.1002/rsa.3240040303

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240040301

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY