随机映射图的局部图

Local Image of Random Mapping Graphs

讨论了当n趋向无穷大时,n个顶点的随机映射图的k-局部图收敛于随机生长过程时刻k的二叉图,这儿,k-局部图是随机映射图前k个顶点{1,2,…,k}所生成的最小图.在这种意义下,称随机映射图为渐近二叉的.

The authors prove that in a random mapping graph with n vertices,when the size n goes to infinity,the k-local image,namely,the smallest graph generated by the first k vertices {1,2,…,k},converges to a random birth process of binary graphs indexed by k. In this sense,the random mapping graph is asymptotically locally binary.