图集上随机游动的覆盖时

On the Cover Time of Random Walks on Graphs

研究了有限图上的简单随机游动对它的顶点至少访问一次所需的期望时间，得到了完全图的期望上界为Ｏ（ｎｌｏｇｎ），（其中ｎ为相应图的顶点数）对对称图，也给出了它的覆盖时的上、下界以上结论改进了原有的结果。

The cover time of finite graphs, that is the expected time needed for a random walk on a finite graph to visit every vertex at least one times, are studied. An upper bound of O(nlogn) for the expection of the cover time for complete graphs is given. And the bounds for the expected cover time for symmetric graphs are proved.