Chain Lengths in Certain Random Directed Graphs
Chain Lengths in Certain Random Directed Graphs
复制标题
某些随机有向图中的链长
DOI：
10.1002/rsa.3240030304
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
C. Newman
中科院分区：
文献类型：
--
作者：
C. Newman
研究了顶点集为{1，…的随机有向图，n}，其中有向边(i，j)以概率Cn/n独立出现，对于i&⩽j，概率为零。设Mn(分别为，Ln)表示最长路径的长度(分别为从顶点1开始的最长路径)。当Cn有界于0且∞为n∞时，作者和J.E.Cohen以前的工作分析了Mn的渐近行为.这里，消除了对Cn的所有限制，也得到了Ln的渐近行为。特别地，如果Cn/ln(N)∞而Cn/N0，则Mn/Cn和Ln/Cn都以概率收敛于常数e。
We study the random directed graph with vertex set {1, …, n} in which the directed edges (i, j) occur independently with probability cn/n for i<j and probability zero for i ⩽ j. Let Mn (resp., Ln) denote the length of the longest path (resp., longest path starting from vertex 1). When cn is bounded away from 0 and ∞ as n∞, the asymptotic behavior of Mn was analyzed in previous work of the author and J. E. Cohen. Here, all restrictions on cn are eliminated and the asymptotic behavior of Ln is also obtained. In particular, if cn/ln(n)∞ while cn/n0, then both Mn/cn and Ln/cn are shown to converge in probability to the constant e.