寻找一个算法可能Dijkstra

我正在寻找一种算法，分布在一个平面上的节点，使边缘是所有相同的大小。我认为这是迪克斯特拉，但我不记得了。任何人都听说过这种算法吗？寻找一个算法可能Dijkstra

2012-04-29 tarrasch

一个简单的反例：如果你有一个节点'a'连接到其他许多'b_1'，'b_2'， ...那么算法必须将所有'b_i'布置在以'a'为中心的圆上。但是，如果你还将每个“b_i”连接到它的邻居，那么如果你的邻居太多，你将会用尽周围。 – katrielalex 2012-04-29 08:38:53

一般来说这是不可能的。实际上，您需要与tilings of the plane中的有限图片类似的内容。

有一些简单的例子 - 规则多边形和几个包含连接多边形的图形，但即使是像4点（四面体）完整图形那样简单的事情也是不可能的。

如果你想尝试平衡不可能的约束，请尝试graphviz及其neato程序。

2012-04-29 07:46:57

谢谢。还要记住，许多图形不能在没有交叉边缘的情况下嵌入到平面中。请参阅：http：//en.wikipedia.org/wiki/Planar_graph，将K5和K3,3作为简单且众所周知的示例。 – 2012-04-30 13:34:51

那么如果你想创建任何图形具有这样的属性，那么有一些图可以帮助你，例如：一条线，一个环，一棵树等。但在这里，你是决定包含或排除哪些边缘的人。

如果你有一个特定的图形，并且你想要所有边的大小相同，那么这是不可能的（因为有些情况） - 比如：一个包含3个以上节点的完整图，主人和超过5个奴隶，以及直接彼此接近的奴隶是邻居。 [我相信其他帖子中的例子告诉你更多]

一个特殊情况，给出一个图$ G（V，E）$，绘制$ G $，使得$ e \ in中每个边的长度E $小于一个单位。这是一个NP难题。 [也就是说，你不能决定是否一个任意图$ G $是一个单位磁盘图]

2012-04-29 15:52:34 AJed

回答