On the Stretch Factor of Randomly Embedded Random Graphs
On the Stretch Factor of Randomly Embedded Random Graphs
复制标题
关于随机嵌入随机图的拉伸因子
DOI：
10.1007/s00454-012-9482-9
复制
发表时间：
2012
影响因子：
0.8
通讯作者：
N. Wormald
中科院分区：
文献类型：
--
作者：
Abbas Mehrabian;N. Wormald
我们考虑一个随机图$$\mathcal{G}(n，p)$$，其基数为$$n，$$的顶点集$$V，$$被随机嵌入到单位正方形中，并且其以概率$$p，$$独立出现的边被赋予等于其末端顶点之间的几何距离的权重。则每对顶点都有赋权图中的距离和欧几里得距离。嵌入图的伸缩因子被定义为这两个距离在所有$u，v\subseteq V上的最大比值。我们给出了伸长因子的上界和下界(几乎必然保持)，并证明了对于不太接近0或1的$$p$$，这些界在某种意义上是最好的。我们的结果表明，当且仅当$$n(1-p)$$趋于0时，拉伸因子以概率趋于1有界，回答了O‘Rourke的一个问题。
We consider a random graph $$\mathcal{G}(n,p)$$ whose vertex set $$V,$$ of cardinality $$n,$$ has been randomly embedded in the unit square and whose edges, which occur independently with probability $$p,$$ are given weight equal to the geometric distance between their end vertices. Then each pair $$\{u,v\}$$ of vertices has a distance in the weighted graph, and a Euclidean distance. The stretch factor of the embedded graph is defined as the maximum ratio of these two distances, over all $$\{u,v\}\subseteq V.$$ We give upper and lower bounds on the stretch factor (holding asymptotically almost surely), and show that for $$p$$ not too close to 0 or 1, these bounds are the best possible in a certain sense. Our results imply that the stretch factor is bounded with probability tending to 1 if and only if $$n(1-p)$$ tends to 0, answering a question of O’Rourke.