Hallo zusammen.
Ist es möglich, einen Graphen zu zeichnen, ohne dass sich dabei die Kanten überschneiden?
Wenn ich 20 Knoten habe und tatsächlich von jedem Knoten zu jedem andere eine Kante ausgeht, kann man das irgendwie geschickt zeichnen?
Gibt es da irgendeine spezielle Anordnung?
Habt ihr da ein System?
MfG!
Disap
Hallo zusammen.
Ist es möglich, einen Graphen zu zeichnen, ohne dass sich
dabei die Kanten überschneiden?
Wenn ich 20 Knoten habe und tatsächlich von jedem Knoten zu
jedem andere eine Kante ausgeht, kann man das irgendwie
geschickt zeichnen?
Gibt es da irgendeine spezielle Anordnung?
Habt ihr da ein System?
Das hängt von der Topologie und Dimension der Fläche ab, in der die Graphen gezeichnet werden sollen. Wenn es der zweidimensionale Euklidsche Raum sein soll, im Volksmunde auch das Papier genannt, dann ist die Antwort ‚Nein‘. Ab fünf (inklusive) ist dort nämlich Schluss: Im zweidimensionalen Euklid’schen Raum ist die maximale Zahl der Nachbargebiete 4.
Nimmt man als Fläche eine Kaffetasse mit einem Henkel (lässt man also eine Brücke zu = Ringfläche), ist die maximale Zahl der Nachbargebiete 7.
Und bei einer Suppentasse mit zwei Henkeln (Doppelringfläche) hat man maximal 8 Nachbargebiete.
Meines Wissens (Stand ca. 1960) kann man die Zahl der maximalen Nachbargebiete für Flachen mit bis zu 9 Henkeln angeben.
Die Frage ist also nicht trivial. (Für Dimension = 2)
Im 3-dimensionalen Euklid’schen Raum gibt es dafür beliebig viele Nachbargebiete, also kann man dort auch 40 Knoten verbinden, ohne dass sich die Verbindungslinien überschneiden…
MfG!
Disap
Hallo,
Ist es möglich, einen Graphen zu zeichnen, ohne dass sich
dabei die Kanten überschneiden?
Wenn ich 20 Knoten habe und tatsächlich von jedem Knoten zu
jedem andere eine Kante ausgeht, kann man das irgendwie
geschickt zeichnen?
20 Knoten? Es ist – in der gewöhnlichen Ebene – überschneidungsfrei bereits ab 5 Knoten unmöglich. Kritzel einfach mal ein bischen auf einem Schmierzettel herum. Du wirst schnell sehen, dass Du die Aufgabe bei 2, 3 und 4 Punkten sofort lösen kannst, aber bei 5 scheiterst, weil bei 5 Punkten am Schluß immer zwei (bei Kreuzungsverbot) unverbindbar sind. Und Du wirst auch fix dahinterkommen, dass es keinen Unterschied macht, ob Du die 5 Punkte in einer Linie, oder wie das Muster auf einem Spielwürfel, oder sonstwie anordnest, denn das topologische Problem ändert sich duch solcherlei Deformationen nicht.
Gibt es da irgendeine spezielle Anordnung?
Nein mit drei Ausrufezeichen.
Gruß
Martin
Hallo,
für die Plättbarkeit von Graphen in der Ebene, siehe auch
http://de.wikipedia.org/wiki/Satz_von_Kuratowski
Grüße
Thorsten