1-Factorizations of random regular graphs
1-Factorizations of random regular graphs
复制标题
1-随机正则图的因式分解
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
N. Wormald
中科院分区：
文献类型：
--
作者：
Michael Molloy;Hanna D. Robalewska;R. W. Robinson;N. Wormald
证明了对于每个r3，一个2n阶随机r-正则图在一定意义下等价于2n阶随机选择的r个不交完美匹配的集合，当n！1.两个概率空间序列的这种等价性称为邻接性（contiguity），当一个空间序列中几乎必然的所有事件在另一个空间序列中几乎必然时，就会发生这种等价性，反之亦然。相应的声明也显示为二部图，并从这表明，一个随机r-正则简单有向图几乎必然是强r-连通的所有r 2。
It is shown that for each r 3, a random r-regular graph on 2n vertices is equivalent in a certain sense to a set of r randomly chosen disjoint perfect matchings of the 2n vertices, as n ! 1. This equivalence of two sequences of probabilistic spaces, called contiguity, occurs when all events almost sure in one sequence of spaces are almost sure in the other, and vice versa. The corresponding statement is also shown for bipartite graphs, and from this it is shown that a random r-regular simple digraph is almost surely strongly r-connected for all r 2.