おそらくDijkstraでアルゴリズムを探しています

私は、エッジがのすべての同じサイズになるように、ノードをプレーンに配布するアルゴリズムを探しています。私はそれがダイクストラによるものだと思いますが、私は覚えていません。誰もこのアルゴリズムについて聞いたことがありますか？おそらくDijkstraでアルゴリズムを探しています

2012-04-29 tarrasch

単純な反例です： 'b_1'、' b_2'、 ...アルゴリズムは、すべての 'b_i'を中心' a'の円上に配置する必要があります。しかし、それぞれの 'b_i'を隣人にも接続すると、あまりにも多くのものがあれば、周りを使い果たします。 – katrielalex

一般的にこれは不可能です。効果的には有限の画像に似たものがtilings of the planeにあります。

いくつかの単純なケースがあります - 正多角形といくつかのグラフには結合されたポリゴンが含まれていますが、4点（四面体）のグラフ全体が単純なものでも不可能です。

不可能な制約のバランスを取ろうとするものがある場合は、graphvizとそのneatoプログラムを試してみてください。

2012-04-29 07:46:57

ありがとうございます。また、多くのグラフは、エッジを横切らずに平面に埋め込むことはできません。 See：http://en.wikipedia.org/wiki/Planar_graph（K5とK3,3）は、単純でよく知られている例です。 –

このようなプロパティを持つグラフを作成したい場合は、線、輪、木などのグラフを作成するのに役立つグラフがいくつかありますが、ここでは誰がどのエッジを含めるか、または除外するかを決定します。

あるグラフがあり、同じサイズのすべての辺を持つ場合は、3つ以上のノードからなる完全なグラフ、1つのスタートポロジマスターと5つ以上の奴隷、そして互いに直接接近している奴隷は隣人です。 [他の投稿のケースでもっと詳しく説明してくれると信じています]

特別なケースでは、$ G（V、E）$というグラフが与えられ、$ e \の各辺の長さE $は単位未満です。これはNP困難な問題です。 [つまり、任意のグラフ$ G $が単位円グラフであるかどうかを判断することはできません]

2012-04-29 15:52:34 AJed

答えて