Graphen zeichnen, komplizierter Algorithmus?

[ethrandil]

Hi,
ich hab da noch ne Frage zu nem komplizierten Algorithmus....
Ich habe einen Graphen mit Knoten und Kanten. Die Kanten haben Längen zugewiesen.

Was ich suche sind Koordinaten für die Knotenpunkte, sodass für jede Kante gilt, dass die verbundenen Knoten genau den Abstand der Kantenlänge haben. Es ist außerdem nicht absolut sicher, ob es eine Lösung für den jeweiligen Garaphen gibt.
Als Ausgabe bräuchte ich also: a) geht nicht, oder b) die Koordinaten der Knoten.

Jemand nen Tipp?

- Eth

[Kinman]

könntest du das mal aufzeichnen, weil so wie ich das verstehe wäre es total leicht und daher denke (weiß) ich das ich es falsch verstehe

mfg Kinman

[ethrandil]

oh, ich hatte etwas vergessen. ;-)

Ich formuliere das Problem nochmal anders:
Es gibt N Kreise mit Radius 1 bis N. Jeder Kreis hat einen Mittelpunkt. Der Graph zeigt an, welche Kreise welche berühren! (Die Kantenlänge ist immer radius1 + radius2).

uuund: Kreise dürfen sich nicht überschneiden.

sry. Hab das Problem falsch reduziert.

- Eth

[DocEW]

Ich denke mal es kommt ein wenig auf die Struktur des Graphen an. Bin mir nicht sicher, welchen Schwierigkeitsgrad das Problem allgemein hat, aber folgendes funktioniert vlt. in Deinem Fall:


Mit irgendeiner Kante (also zwei Kreisen) anfangen, den ersten Mittelpunkt z.B. auf (0,0) und den zweiten auf (d,0) zeichnen.
Solange du jetzt einen Knoten v findest, der mit mindestens zwei schon gezeichneten Knoten x und y verbunden ist, ist seine Position eindeutig bestimmt.

Eventuell ist es besser, mit drei Knoten anzufangen, die alle paarweise verbunden sind... dürfte die Chancen, daß der Algorithmus "durchkommt" wesentlich erhöhen.
Oder du erweiterst es so, daß du quasi Teilgraphen anfängst aufzuzeichnen, und sie dann zusammensetzt (unter Anpassung der Koordinaten). Weißt du, was ich meine..? :)

Viele Grüße,

DocEW

[Edit:] Im zweiten Schritt ist die Position doch nicht eindeutig bestimmt, es gibt zwei Möglichkeiten. Allerdings dürfen sich Kanten wahrscheinlich nicht kreuzen, oder? Dann scheidet dadurch evtl. eine aus, ansonsten mittels Backtracking..? Hm, vielleicht war ich etwas zu voreilig. :(