Rubber bands, convex embeddings and graph connectivity
Rubber bands, convex embeddings and graph connectivity
复制标题
橡皮筋、凸嵌入和图连接
DOI：
10.1007/bf02122557
复制
发表时间：
1988
期刊：
影响因子：
1.1
通讯作者：
A. Wigderson
中科院分区：
文献类型：
--
作者：
N. Linial;L. Lovász;A. Wigderson
我们利用几何、代数和“物理”性质给出了K-点连通图的各种刻画。作为一个例子，图G是k连通的当且仅当指定G的任意k个顶点时，图G的顶点可以用ℝk−1的点表示，使得nok在超平面上，并且每个顶点都在其邻域的凸壳中，除了k个指定的顶点。这个定理的证明符合物理学的要求。通过使图的边表现为理想弹簧并使其顶点处于平衡状态来找到嵌入。作为我们结果的算法应用，我们给出了计算图的连通性的概率(蒙特卡罗和拉斯维加斯)算法。对于Alk≧√n，我们的算法比最著名的(确定性)连通性算法快，对于非常密集的图，蒙特卡罗算法的速度快一个线性因子。
We give various characterizations ofk-vertex connected graphs by geometric, algebraic, and “physical” properties. As an example, a graphG isk-connected if and only if, specifying anyk vertices ofG, the vertices ofG can be represented by points of ℝk−1 so that nok are on a hyper-plane and each vertex is in the convex hull of its neighbors, except for thek specified vertices. The proof of this theorem appeals to physics. The embedding is found by letting the edges of the graph behave like ideal springs and letting its vertices settle in equilibrium.As an algorithmic application of our results we give probabilistic (Monte-Carlo and Las Vegas) algorithms for computing the connectivity of a graph. Our algorithms are faster than the best known (deterministic) connectivity algorithms for allk≧√n, and for very dense graphs the Monte Carlo algorithm is faster by a linear factor.