A note on the last new vertex visited by a random walk
A note on the last new vertex visited by a random walk
复制标题
关于随机游走访问的最后一个新顶点的注释
作者：
L. Lovász;P. Winkler
从顶点 x 开始的连通图 G 的“覆盖之旅”是一种随机游走，从 x 开始，以相等的概率在每一步中移动到其当前顶点的任何邻居，并在到达 G 的每个顶点时结束。众所周知，循环 Cn 具有一个奇怪的特性，即从任何顶点开始的覆盖之旅同样有可能在任何其他顶点结束；完整的图 Kn 通过对称性简单地共享此属性。罗纳德·L·格雷厄姆 (Ronald L. Graham) 询问是否还有其他具有此属性的图表；我们证明不存在。 © 1993 约翰威利父子公司。
A “cover tour” of a connected graph G from a vertex x is a random walk that begins at x, moves at each step with equal probability to any neighbor of its current vertex, and ends when it has hit every vertex of G. The cycle Cn is well known to have the curious property that a cover tour from any vertex is equally likely to end at any other vertex; the complete graph Kn shares this property, trivially, by symmetry. Ronald L. Graham has asked whether there are any other graphs with this property; we show that there are not. © 1993 John Wiley & Sons, Inc.