Graphen an Hand von gegebenen Knotengraden zeichnen |
| 09.02.2011, 22:10 | Dän1987 | Auf diesen Beitrag antworten » | ||
| Graphen an Hand von gegebenen Knotengraden zeichnen Wie kann ich strukturiert (ohne es nur durch ausprobieren hinzubekommen) einen Graphen zeichnen, wenn ich die Grade der vorkommenden Knoten gegeben habe? Skizziere den Graphen, bei dem die Knotengrade 2,2,2,3,3,4,4,4,4 sind. Meine Ideen: Ich habe mir zunächst überlegt, dass der Graph (logischerweise) 9 Knoten haben muss. Die Summe der Knotengrade beträgt 28, also brauche ich 14 Kanten in einem zusammenhängenden Graphen (?). Wie finde ich aber heraus, welche Kanten genau den gefragten Graph liefern? |
||||
| 10.02.2011, 01:50 | Iridium | Auf diesen Beitrag antworten » | ||
Zunächst einmal weiß ich nicht, ob es bereits einen Algorithmus für genau dieses Problem gibt. Könnte aber sein, dann ist es hilfreich danach zu googeln, am Besten auch mit englischen Schlagwörtern. Wenn es sowas gibt (die Wahrscheinlichkeit ist vielleicht gar nicht so gering, da es ein einfaches, gut definiertes Problem ist). dann findet man auf diese Weise jede Menge Fachliteratur. Man sollte auf jeden Fall auch berücksichtigen, daß es mehrere Graphen mit der gewünschten Eigenschaft geben könnte. Dann wäre interessant: Will man eine vollständige Auflistung aller Möglichkeiten oder reicht ein Repräsentant? Deine Überlegungen sind logisch begründet und soweit ich sehe auch richtig, es gibt im Prinzip auch nur zwei Vorgehensweisen. Entweder du startest bei einem Knoten und fügst der Reihe nach Knoten hinzu, wobei die Randbedingungen, die durch die Sequenz der Knotengrade gegeben ist, jeweils erfüllt werden, wobei nicht klar ist, ob man so nicht auch stecken bleiben kann, im Prinzip muß man auf jeder Stufe alle möglichen Anordnungen prüfen (also ausprobieren, wenn auch systematisch). Oder man beginnt beim vollständigen Graph mit 9 Knoten und löscht eine entsprechende Anzahl von Kanten. Da relativ viele Knoten mit Grad 2 dabei sind (quasi entsprechend den Seiten eines Polygons, wenn man den vollständigen Graphen entsprechend zeichnet), kann man das Problem evtl. schnell auf einen überschaubareren Bereich reduzieren, wenn es nicht noch so sein kann, daß es vielleicht gar keinen Graphen mit dieser Eigenschaft gibt (aber ich setze mal voraus es gibt ihn, denn du tust das offensichtlich auch). Soweit, viele Grüße edit: die Idee mit dem vollständigen Graphen und dem Polygon scheint ganz gut zu sein, habe beim dritten Probieren einen möglichen Graphen gefunden. Tipp: Überlege, i) daß du nur Knoten mit Graden größergleich 2 hast (-> Polygon mit neun Ecken als Grundstruktur), ii) daß die Sequenz von Knoten "symmetrisch" ist (d.h. 1 x 2, 2 x (2,3,2x(4)) ), iii) daß der Graph dichte und weniger dichte Bereiche aufweisen muß, dicht bezüglich der Kanten, weil du etwa gleich viele Knoten mit minimalen wie maximalen Knotengraden hast. Der Übergangsbereich dazwischen ist dagegen sehr klein, denn von Knoten mit Grad 3 gibt es nur zwei Stück. Zusammengenommen führt das vermutlich schnell zur Lösung. Du kannst ja mal eine Skizze hier zeigen, wenn du erfolgreich warst, vielleicht gibt es doch mehrere Möglichkeiten und du findest ein anderes Beispiel, als ich. |
||||
| 10.02.2011, 09:09 | Mystic | Auf diesen Beitrag antworten » | ||
Ich weiß zwar auch nicht, ob es einen Algorithmus für dieses Problem gibt (kenne jedenfalls selbst keinen!), aber habe auch so jetzt beim Frühstück (noch ehe ich die erste Tasse Kaffee zum Mund geführt hatte und ohne Beistift und Papier!) eine Lösung gefunden, welche von Iridium's Lösung jedenfalls verschieden ist... Dazu stelle man sich das "Haus des Nikolaus" mit einem "zweiten Dach" (dort wo eigentlich der Keller sein sollte) vor, wobei auch die zwei Dachspitzen durch eine Kante verbunden sind... Naja, das deckt schon mal die Knotengrade 4,4,4,4,3,3 ab und für die Restfolge 2,2,2 zeichnet man einfach irgendwo in der Ebene und getrennt davon ein Dreieck... Dies beweist insbesondere, dass ein Graph mit diesen Knotengraden nicht zusammenhängend sein muss, eine ohnehin haltlose Vermutung... |
||||
| 10.02.2011, 09:57 | Dän1987 | Auf diesen Beitrag antworten » | ||
Hallo, vielen Dank für Eure Antworten. Habe gerade einmal gesucht und tatsächlich einen Algorithmus gefunden. Algorithmus von Havel und Hakimi Nach einigem ausprobieren hat's dann auch geklappt. Prinzipiell muss man folgendermaßen vorgehen: 1) Beginne mit der leeren Kantenmenge 2) Sortiere die Knoten absteigend ihres Grades (d1,d2,d3,...) 3) verbinde den ersten Knoten d1 mit den folgenden deg(d1) Knoten 4) streiche diesen Knoten aus der Liste 5) sortiere die Liste neu und beginne bei 1) bis alle Gradanforderungen erfüllt sind. Ich hoffe das man das so vielleicht besser nachvollziehen kann als auf der Originalseite und das ich mich gerade nicht vertan habe. Viele Grüße |
||||
| 10.02.2011, 10:17 | Mystic | Auf diesen Beitrag antworten » | ||
Hm, mir geht es umgekehrt so, dass ich den Algorithmus auf der von dir zitierten Seite glaubte verstanden zu haben, aber jetzt nach deinen Anweisungen wieder unsicher geworden bin... Bist du sicher, dass man nach Schritt 5 mit Schritt 1 weitermacht und nicht Schritt 3? Auch dein Schritt 4 scheint mir zu "vage", denn mit einem bloßen "Streichen" des Knotens ohne gleichzeitige Adaption der Knotengrade ist es ja nicht getan... Edit: Ich habe jetzt selber nicht im Internet recherchiert - und schon gar nicht auf der Wikipedia - in der (wie sich nun herausstellt, irrigen) Annahme, diese "Vorarbeiten" wären bereits von dir erledigt worden, bevor du diese Frage hier stellst... 
|
||||
| 10.02.2011, 10:51 | Dän1987 | Auf diesen Beitrag antworten » | ||
Hallo Mystic, hast recht, dass man wieder mit Schritt 3 statt Schritt 5 beginnen muss! Sorry! Ich habe vorher auch schon lange im Internet recherchiert, bin aber (dummerweise) erst durch dich auf die Idee gekommen auch mal auf Englisch zu googlen. Kannst ja gerne mal versuchen mit deutschen Suchanfragen auf diesen Algorithmus zu kommen. Ist mit Sicherheit möglich, aber bei meinen Suchanfragen kamen wirklich keine brauchbaren Ergebnisse raus. |
||||
| Anzeige | ||||
|
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
