THE LARGEST CONNECTED COMPONENT IN A RANDOM MAPPING

被引：5

作者：

JAWORSKI, J ^{[1
]}

MUTAFCHIEV, L ^{[1
]}

机构：

[1] BULGARIAN ACAD SCI,INST MATH,CTR COMP,BU-1090 SOFIA,BULGARIA

来源：

RANDOM STRUCTURES & ALGORITHMS | 1994年 / 5卷 / 01期

关键词：

RANDOM MAPPINGS; RANDOM FORESTS; RANDOM GRAPHS; LIMITING DISTRIBUTIONS;

D O I：

10.1002/rsa.3240050109

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A random mapping (T; q) of a finite set V = {1, 2, . . . , n} into itself assigns independently to each i is-an-element-of V its unique image j = T(i) is-an-element-of V with probability q for i = j and with probability 1-q/n-1 for j not-equal i. The purpose of the article is to determine the asymptotic behavior of the size of the largest connected component of the random digraph G(T)(q) representing this mapping as n --> infinity, regarding all possible values of the parameter q = q(n). (C) 1994 John Wiley & Sons, Inc.

引用

页码：73 / 94

页数：22

共 12 条

[1] BERG S, 1992, RANDOM GRAPHS 89
[2] Bollobas B., 1985, RANDOM GRAPHS
[3] ERDOS P, 1960, B INT STATIST INST, V38, P343
[4] Feller W., 1957, INTRO PROBABILITY TH
[5] JAWORSKI J, 1990, RANDOM GRAPHS 87, P89
[6] JAWORSKI J, 1985, THESIS A MICKIEWICZ
[7] JAWORSKI J, 1983, GRAPH OTHER COMBINAT, P134
[8] PROBABILITY OF INDECOMPOSABILITY OF A RANDOM MAPPING FUNCTION
KATZ, L
[J]. ANNALS OF MATHEMATICAL STATISTICS, 1955, 26 (03): : 512 - 517
[9] Kolchin V. F., 1986, RANDOM MAPPINGS
[10] Mutafchiev L., 1984, MATH ED MATH, P57

← 1 2 →