论文标题
在最后一个新的顶点，在有向图中随机步行访问
On the Last New Vertex Visited by a Random Walk in a Directed Graph
论文作者
论文摘要
考虑一个简单的图形，其中随机步行以给定的顶点开始。它在每个步骤上以同等的概率移动到其当前顶点的任何邻居，并在访问每个顶点时结束。我们称这种随机步行为随机的封面之旅。众所周知，循环和完整的图具有一个属性，即从任何顶点开始的随机封面游览都可能在任何其他顶点结束。罗纳德·格雷厄姆（Ronald Graham）询问此属性是否还有其他图表。 1993年，LászloLovász和Peter Winkler表明，循环和完整的图是该特性的唯一无向图。我们通过表明循环和完整的图（所有边缘被认为是双向的）是唯一具有此属性的有向图来加强这一结果。
Consider a simple graph in which a random walk begins at a given vertex. It moves at each step with equal probability to any neighbor of its current vertex, and ends when it has visited every vertex. We call such a random walk a random cover tour. It is well known that cycles and complete graphs have the property that a random cover tour starting at any vertex is equally likely to end at any other vertex. Ronald Graham asked whether there are any other graphs with this property. In 1993, Lászlo Lovász and Peter Winkler showed that cycles and complete graphs are the only undirected graphs with this property. We strengthen this result by showing that cycles and complete graphs (with all edges considered bidirected) are the only directed graphs with this property.
