有向图上的随机游动

设G=(V,Г)是有向图,G上的随机游动X(G)定义如下:位于某个顶点上的一个粒子将以等概率转移到该顶点的所有后继顶点.令M(j,n)表示随机游动X(G)在前n步内访问顶点j的平均次数,用W(j)表示随机游动X(G)到达顶点j所需要的平均步效.我们对M(j,n)和W(j)的值进行了估计,证明了M(j,n)=O(n),并给出了W(j)的上界.     

无限图的翼和梢的关系

翼和梢是无限图的两个重要概念,在无限图的路分解理论中它们起着关键的作用,探导它们之间的联系是无限图论中的一个重要的理论课题,这个问题的解决将使许多有关无限图的路分解理论得到统一。但还无人在这个领域作出贡献,本文我们全面揭示了它们之间的内在联系,由此指出了C.ST.J.A.Nash—Williams定理同B.Zelinka定理的等价性。     

随机图ξ（n,M）上随机游动的平均返回时间

设 G 是一个连通图,G 上的随机游动是如下的马氏链:其状态空间是 G 的顶点集,从一个顶点总是以等概率转移到相邻的顶点。用 E_(n,M)(k)表示在全体具有 n 个顶点 M 条边的连通图上,随机游动回到具有次数为 h 的项点所用的平均时间。我们得到了以下结果:对任意固定实数 c,令 M_o=[1/2nl_n+cn],那么当→∞时,