科研之友
微信
新浪微博
Facebook
分享链接
摘要
记T(n,d)为n个顶点且直径为d的树的集合.对T∈T(n,d),maxi∈V H(π,i)和mini∈V H(π,i)分别表示从平稳分布出发、最终终止于T中某一点的最优终止规则所决定的那些随机游动中所走的平均步数的最大值和最小值.本文通过对树T进行一些图的变换来减小或增大maxi∈V H(π,i)与mini∈V H(π,i),从而确定了T(n,d)中分别取到maxi∈V H(π,i)上界以及mini∈V H(π,i)下界的极图.此外还确定了直径不大于4的树中分别取到maxi∈V H(π,i)下界和mini∈V H(π,i)上界的图.本文的部分结果是对[Graphs Combin.,2013,29(4):757-772]中相应结论的推广.
- 单位
