我想将一个无向图投影到二维平面中，这样：
欧几里得距离保留了逐步距离（即如果A和B之间的最短路径短于C和D之间的最短路径，那么A和B之间的欧几里得距离小于A和B之间的欧几里得距离）
欧几里得距离和逐步距离之间的最小差异被最小化。理想情况下，如果没有唯一的最小值，则生成或描述一组解决方案。
如果这是不可能的，那么图上使之成为可能的最小约束集是什么？我一般对这个问题很感兴趣，尽管目前我希望它是一个有限晶格，并去除了它的最小值。
问问题
53 次
2 回答
0
我认为第一个要求是不可能的，至少对于一般情况而言。考虑一个由四个节点组成的全连接图，所有路径长度都相等。在 2D 欧几里得空间中选择具有相同属性的四个点是不可能的（除了 4 个重合点）。
有关一些有用信息，请参阅 Diego 的回答（我的图论知识非常有限！）。
于 2012-03-25T18:08:37.727 回答
0
它被称为图嵌入。甚至还有一个定理给出了失真的上限。我最喜欢的嵌入算法是SDE。如果您有SDP库，那么在任何语言上实现都相当容易。
这是一个更简单的算法。
于 2012-03-25T18:09:36.673 回答