尋找一個算法可能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

回答