On the number of cycles in a random non-equiprobable graph
On the number of cycles in a random non-equiprobable graph
复制标题
关于随机非等概率图中的循环数
DOI：
10.1515/dma.1992.2.1.109
复制
发表时间：
1992
影响因子：
3.7
通讯作者：
V. I. Khokhlov
中科院分区：
文献类型：
--
作者：
V. F. Kolchin;V. I. Khokhlov
我们考虑一个非等概率随机图 Gn,#，具有 n 个标记顶点和 N 个边，这是通过 N 个独立试验获得的。在每次试验中绘制一条边：它以概率 2ρ,·ρ;· 连接顶点 i 和 j，或者以概率 p?; 在顶点 i 处形成环； i, j = 1,..., n, pi,..., pn > 0, Pi + 。 。 。 + Pn = 1。本文的主要结果是以下断言。假设 p,· = α,·/η 其中 a,· = α,·(η), 0 < ε < a,· < Ε < oo, i = 1,..., η, ε 和 Ε 为常数，极限 1 n 2 l · · * · V~^ 2 a = hm -2_X „_>oon^ 存在。那么，如果 n 和 N 趋于无穷大，则 2N/n -» λ 和 λα < 1，图中的循环数分布收敛于参数 Λ = —| ln(l λα) 的泊松分布 1. 主要陈述 在许多研究随机图的论文中（结果调查可以在 [1-3] 中找到），只有少数出版物涉及以不等概率取值的随机图 [4-6]。在许多情况下，必须毫无疑问地研究在严格等概率条件下获得的结果，以及知道在等概率情况下如何修改结果以及什么水平的概率偏差可以被视为保留对等概率情况有效的结果是有用的。在本文中，研究了在参数条件下的多个等概率图模型。趋向于一个图没有巨分量，循环数受限于泊松分布。在[7]中指出，对于具有 n 个顶点和 TV 边的随机等概率图，可以通过矩量法表明循环数分布 an,jv 收敛于参数为 -|ln(l) 的泊松分布，即 η, Ν -> oo, 2N/n -> λ, Ο < λ < 1。 λ) λ/2 λ/4。在[8]中证明了具有 n 个顶点的随机图，其中任意边独立于其他边存在，在本文中，我们考虑一个非等概率图 Gn^，其 n 个顶点标记为数字 1,2,..., n 并通过以下过程获得 TV 边。一条边连接两个不同的顶点或形成一个环；带有标签 i 和 j 的顶点以 2pipj 连接，并且顶点 i 处的环由 *UDC 519.12 最初发表于 Diskretnaya Matematika (1990) 2, No. 3, 137-145（由 A. V. Kolchin 翻译）。 F. Kolchin 和 Khokhlov 概率 p; ij = l,... ,n, pi,... ,pn > 0, pi + ... + pn = 1。因此，经过 TV 试验，我们得到了随机图 Gn,N，一般来说，该图具有环和多条边。本文的主要结果是以下断言。 假设 pt = α,/π 其中 a, = a,(n), 0 < ε < a,· < jE < oo, i = 1,..., η, ε 和 Ε 为常数，极限 a 2 = lim-Y> ~*°° n i^i 则，如果 η 和 Ν 趋于无穷大，使得 2N/n —> λ, λα < I ，则图 GH,N 中的循环数 an^ 的分布收敛于证明定理时，得到了参数 Λ = — |ln(l λα) 的随机变量 ar 的极限分布，以及 an,..., otTs 的联合极限分布。在定理 1 的条件下，在不要求 λα < 1 的情况下，对于任意固定的 r，随机变量 ar 的分布趋于参数 \T = 的泊松分布。 Aa/(2r)。在定理 1 的条件下，对于任何固定的 1 < r\ < ... < rs ， ari,..., ar 的分布收敛于具有参数 Ar i , \Te 的泊松分布。这些情况可能解释了这样一个事实：即使对于等概率情况，也从未公布过通过矩量法得出的完整的 ρτοοί。因此，我们将在下一节中给出详细的证明。 2. 主要陈述的证明 用 ar 表示随机图 Gn,w· 中不存在长度为 r 的自交的循环数，让我们给出该变量的更精确的定义。对于 r 个不同的顶点 n,...,ir 假设 &!,...,,·,. = 1，如果在 GH,N 中存在由这 r 个顶点组成且正好包含图 GU,N 的 r 个边的环（这样的环称为无自交环），在其他情况下假设 &,,...,,,. = 0。则 «r = Σ &I.-..V, (1) «l,..M*r 求和在具有顶点 zi , ,z r 的所有 CN 不同无序集合中，存在恰好包含 r 个边的 (r 1)1/2 个循环，并且将这些循环标记为随机变量 &aph 111 j = 1, . , (r — l)!/2 ，并将随机变量 £,lt...,tr 表示为指标之和： (r-l)!/2 &,-,V = Σ #L,V> (2) j=i 其中 £t^..Mt= 1 如果第 j 个循环（在所选标签下）存在于 <3n,yv 中，否则 f£L«v = 0 在本文中研究了随机变量，其中变量 ar 由 (1) 定义（对于 r > 3），a\ 是循环数，a2 是平行边对的数量。 Gn^。图 GUIN 中的每个循环可以被视为构成该循环的边的集合；因此，需要以下断言来评估 P{£t^..|t-r = 1} 等概率。令 Vr = {(ii,ji),...,(ir,jr)} 为图 Gn,N 中的 r 个不同顶点对的集合，其中 u ^ j k , k l,...,r 表示。 P(Vr) Vr 的所有边都存在于 Gn,N· 引理 1 中的概率。如果 n,N — > oo, 2N/n — > λ, 0 < λ < oo, 0 < ε < α, < Ε < οο, i l, ... , η，则对于任意固定 ε, Ε, r P(VT) = ̂ α,.,α;, ...a,vair (l + O Q) (3) 一致地关于 αϊ, , αn ΖΖ f/ze 提到的边界和所有集合 Vr 。此外，对于任何 δ > 0 ，存在一个常数 c ，使得对于所有 r 和 n 。
We consider a non-equiprobable random graph Gn,# with n labelled vertices and N edges which is obtained by N independent trials. In each trial one edge is drawn: it connects vertices i and j with the probability 2ρ,·ρ;·, or it forms a loop at vertex i with the probability p?; i, j = 1,..., n, pi,..., pn > 0, Pi + . . . + Pn = 1. The main result of the paper is the following assertion. Assume that p,· = α,·/η where a,· = α,·(η), 0 < ε < a,· < Ε < oo, i = 1,..., η, ε and Ε are constants, and the limit 1 n 2 l · · * · V~^ 2 a = hm -2_X „_>oon^ exists. Then, if n and N tend to infinity so that 2N/n -» λ and λα < 1, the distribution of the number of cycles in the graph converges to the Poisson distribution with parameter Λ = —| ln(l λα). 1. THE MAIN STATEMENTS Among a number of papers devoted to random graphs (surveys of the results can be found in [1-3]) only a few publications deal with random graphs which take their values with unequal probabilities [4-6]. However, the stability of the results obtained under the condition of strict equiprobability must be studied without doubts. In a number of cases it is useful to know how the results are modified if the condition of equiprobability is omitted and what level of deviations of the probabilities can be considered as a negligible one which preserves the results valid for the equiprobable case. In the present paper an important characteristic of a random graph, namely the number of cycles, is investigated. For a number of models of equiprobable graphs under the conditions on parameters such that with the probability tending to one the graph has no giant component, the number of cycles has in limit the Poisson distribution. In [7] it is pointed out that for a random equiprobable graph with n vertices and TV edges one can show by the method of moments that the distribution of the number of cycles an,jv converges, as η, Ν -> oo, 2N/n -> λ, Ο < λ < 1, to the Poisson distribution with parameter -|ln(l λ) λ/2 λ/4. The analogous result for a random graph with n vertices, in which any edge exists independently of the others with the probability ρ = λ/η, Ο < λ < 1, is proved in [8]. In the present paper we consider a non-equiprobable graph Gn^ with n vertices labelled with the numbers 1,2,..., n and with TV edges obtained by the following process. One carries out N independent trials in each of which one edge is drawn. The edge connects two different vertices or forms a loop; the vertices with labels i and j are connected with the probability 2pipj, and the loop at vertex i is formed with the *UDC 519.12. Originally published in Diskretnaya Matematika (1990) 2, No. 3, 137-145 (in Russian). Translated by A. V. Kolchin. 110 K F. Kolchin and K /. Khokhlov probability p; ij = l,... ,n, pi,... ,pn > 0, pi + ... + pn = 1. Thus, after TV trials we have a realization of the random graph Gn,N, which, generally speaking, has loops and multiple edges. The main result of the paper is the following assertion. Theorem 1. Assume that pt = α,/π where a, = a,(n), 0 < ε < a,· < jE < oo, i = 1,..., η, ε and Ε are constants, and the limit a 2 = lim-Y> ~*°° n i^i exists. Then, if η and Ν tend to infinity so that 2N/n —> λ, λα < I , the distribution of the number of cycles an^ in the graph GH,N converges to the Poisson distribution with parameter Λ = — |ln(l λα). While proving the theorem, the limit distribution of the random variable ar, which is equal to the number of the cycles of length r, and the joint limit distribution of an,..., otTs are obtained. Theorem 2. Under the conditions of Theorem 1, without the requirement λα < 1, the distribution of the random variable ar for any fixed r tends to the Poisson distribution with parameter \T = Aa/(2r). Theorem 3. Under the conditions of Theorem 1, without the requirement λα < 1, the joint distribution of ari,..., ar, for any fixed 1 < r\ < ... < rs converges to the distribution of s independent random variables which have the Poisson distributions with parameters A r i , . . . , \Te, respectively. The proof will be performed by the method of moments. As one realizes this laborconsuming approach, the natural desire to omit bulky calculations arises. These circumstances, probably, explain the fact that a complete ρτοοί earned out by the method of moments has never been published even for the equiprobable case. Therefore we give detailed proofs in the next section. 2. PROOFS OF THE MAIN STATEMENTS Denote by ar the number of cycles without self-intersections of length r, r > 3, in the random graph Gn,w· Let us give a more precise definition of the variable. For r distinct vertices n,...,ir assume &!,...,,·,. = 1 if in GH,N there exists a cycle composed of these r vertices and containing exactly r edges of the graph GU,N (such cycles are called the cycles without self-intersections); in other cases assume &,,...,,,. = 0. Then «r = Σ &I.-..V, (1) «l,..M*r where the summation is taken over all CN distinct unordered sets of r distinct indices. In the complete graph with vertices zi , . . . ,z r there exist (r 1)1/2 distinct cycles containing exactly r edges. We label these cycles in an arbitrary order with the numbers On the number of cycles in a random &aph 111 j = 1, . . . , (r — l)!/2 and represent the random variable £,lt...,tr as the sum of indicators: (r-l)!/2 &,-,V = Σ #L,V> (2) j=i where £t^..Mt= 1 if the jth (under the labelling chosen) cycle exists in <3n,yv, and f£L«v = 0 otherwise. In the paper the random variable is investigated, where the variables ar are defined by (1) for r > 3, a\ is the number of loops, and a2 is the number of pairs of parallel edges in Gn^. Each cycle in the graph GUiN may be considered as the set of edges which compose this cycle; therefore, the following assertion is needed for evaluating such probabilities as P{£t^..|t-r = 1}. Let Vr = {(ii,ji),...,(ir,jr)} be the set of r distinct pairs of vertices in the graph Gn,N where u ^ j k , k l,...,r. Denote by P(Vr) the probability of the event that all the edges from Vr exist in Gn,N· Lemma 1. If n,N — > oo, 2N/n — > λ, 0 < λ < oo, 0 < ε < α, < Ε < οο, i l, ... , η, then for arbitrary fixed ε, Ε, r P(VT) = ̂ α,.,α;, ...a,vair (l + O Q) (3) uniformly with respect to αϊ, . . . , αη ΖΑΖ f/ze mentioned bounds and to all sets Vr . Moreover, for any δ > 0 there exists a constant c such that for all r and n