Ich mag würde Sie fragen, ob es irgendwelche Algorithmen sind wie Kantenkreuzungen in Graphen zu minimieren, zum Beispiel, wenn ich eine Übergangsmatrix des Graphen haben.Kantenüberquerung Reduzierung der Graph
fand ich Methoden wie der Versuch, die Knoten um den anderen Knoten zu platzieren, aber ich möchte einige andere Ideen kennen zu lernen. Vielen Dank.
Es gibt eine Reihe von gut etablierten Algorithmen/Bibliotheken, die für Graphzeichnung Anwendungen entwickelt wurden, können Sie ein wenig Hintergrund here bekommen.
Um ungerichtete Graphen zu zeichnen, ist der kraftbasierte Layoutalgorithmus beliebt, bei dem Graphenkanten als Federn (Anziehungskräfte) behandelt werden, während die Ecken wie geladene Teilchen behandelt werden (abstoßende Kräfte). Der Algorithmus arbeitet, indem er die Eckpunktpositionen basierend auf diesen Kräften aktualisiert, bis ein stationärer Zustand erreicht ist. Sie können mehr über erzwungene Methoden lesen here. Da diese Algorithmen Suche nach einer Gleichgewichtslösung oft sie in pseudo-optimalen Layouts führen, ohne viele Kanten Verheddern.
Sie könnten in der Nutzung von einem der vielen Zeichnen von Graphen Bibliotheken interessiert sein, die verfügbar sind. Das Graphviz Paket ist in der Regel ziemlich gut und unterstützt eine Reihe unterschiedlicher Algorithmen für verschiedene Zeichnen von Graphen-Anwendungen.
Sind Sie fragen über Graph * Zeichnung * - das heißt ein Algorithmus, der ein gutes Vertex-Layout (mit minimalen Kantenkreuzungen usw.) für einen Graphen 'G (V, E) geben' ?? –
Ja das habe ich mir gedacht – DropDropped