エッジがすべて同じサイズになるように、平面上にノードを分散するアルゴリズムを探しています。ダイクストラによるものだと思いますが、思い出せません。このアルゴリズムについて聞いたことがある人はいますか？
質問する
122 次
2 に答える
1
一般に、これは不可能です。事実上、平面のタイリングの有限画像に似たものが必要です。
いくつかの単純なケースがあります - 正多角形と結合された多角形を含むいくつかのグラフですが、4 点 (四面体) の完全なグラフのような単純なものでさえ不可能です。
不可能な制約のバランスをとろうとするものが必要な場合は、graphvizとその neato プログラムを試してください。
于 2012-04-29T07:46:57.553 に答える
0
このようなプロパティを使用してグラフを作成したい場合は、線、リング、ツリーなど、その作成に役立つグラフがいくつかありますが、ここで何を決定するかはあなた次第です。含めたり除外したりするエッジ。
特定のグラフがあり、すべてのエッジを同じサイズにしたい場合、これは不可能です (場合によっては)。たとえば、3 つ以上のノードの完全なグラフ、1 つのマスターと複数のマスターを持つスター トポロジなどです。 5 つのスレーブ、および互いに直接に近いスレーブはネイバーです。[他の投稿のケースがより多くのことを教えてくれると思います]
特殊なケースとして、グラフ $G(V,E)$ が与えられ、$e \in E$ の各辺の長さが 1 単位未満になるように $G$ を描画します。これは NP 困難な問題です。[つまり、任意のグラフ $G$ が単位円板グラフかどうかを判断できない]
于 2012-04-29T15:52:34.590 に答える