关于强连通图中存在超多项式时间随机游走顶点对的存在性及高最小度有向图实例构造的问询

嘿，这个问题很有意思！我来给你一个经典的构造实例，刚好满足所有条件，还能扩展出超多项式的击中时间：

基础构造步骤 #

假设n是偶数（奇数的话只需微调集合大小），我们把n个顶点分成两个大小均为n/2的集合A和B：

• 集合A的边构造：A是一个完全有向图（任意两个不同顶点之间都有双向边），同时A中的每个顶点都指向B中的所有顶点。这样A中每个顶点的出度为$(n/2 -1) + n/2 = n-1$，远大于n/2；入度也为n-1，完全满足≥n/2的要求。
• 集合B的边构造：B中的每个顶点都指向A中的所有顶点，同时B内部只有一个有向环（比如$b_1→b_2→…→b_{n/2}→b_1$），并且每个B顶点还指向B中除了环上自己前驱之外的所有其他顶点。这样B中每个顶点的出度为$n/2$（到A） + $(n/2 -2)$（到B内部非前驱） +1（环的边）=n-1，同样满足≥n/2的要求。

强连通性验证 #

这个图显然是强连通的：

• A内部任意顶点互相可达（完全有向图）；
• A到B任意顶点直接有边；
• B到A任意顶点直接有边；
• B中任意顶点到环上的前驱顶点，都可以走「该顶点→A中任意顶点→前驱顶点」的路径实现可达。

超多项式击中时间的扩展构造 #

如果我们把这个结构扩展为多层嵌套（比如m层类似A、B的结构，每层大小为n/m），让每一层的顶点仅能直接指向本层和下一层的特定小部分顶点，那么从最外层的s到最内层的t的期望击中时间会变成$O((n/m)^m)$。当m取$\log n$时，这个时间就是$(n/\log n)^{\log n}$，这是一个超多项式的时间（增长速度远超任何多项式），同时每层顶点的出度仍然可以保证≥n/2。

这样的构造完美满足了你提出的所有条件：强连通、每个顶点度数≥n/2，且存在s,t使得随机游走的击中时间超多项式。

备注：内容来源于stack exchange，提问作者n094862