Existenz eines schlichten Graphen |
| 12.01.2016, 12:40 | uhmdunnolol | Auf diesen Beitrag antworten » |
| Existenz eines schlichten Graphen wollte mal fragen ob mir jemand bei nem gewissen Aufgabentyp vielleicht helfen könnte, bzw Tipps dazu hat. Die Aufgabenstellungen sind z.B.: Untersuchen Sie, ob ein schlichter Graph mit 7 Knoten existiert, der die angegebenen Knotengrade besitzt. Zeichnen Sie gegebenenfalls einen entsprechenden Graphen. (i) 1, 2, 2, 3, 4, 5, 5 (ii) 1, 1, 1, 3, 5, 5, 6 Allgemein wollte ich da so drangehen, dass ich zu erst nach dem Handschlags-Dilemma schaue, also ob die Anzahl der Knoten mit ungeradem Knotengrad gerade ist, denn sonst kann es einen solchen Graph ja nicht geben. Außerdem natürlich ob der maximale Knotengrad nicht überschritten wird. Nun ist das aber bei beiden obigen Beispielen erfüllt. Bei beiden obigen Beispielen komme ich noch drauf, dass der Graph jeweils 11 Kanten haben muss. Meiner Meinung nach wäre das Beispiel II) dann nicht lösbar, da ein Knoten mit allen anderen verbunden wird (=6 Kanten weg) und gleichzeitig die ersten drei Knoten mit Knotengrad 1 dadurch wegfallen. Es bleiben also 3 Knoten und 5 Kanten. Mir fällt hier kein Weg ein, diese 3 Knoten mit zusätzlich 5 Kanten auszustatten, ohne dass es zu Mehrfachkanten/Schlingen kommt. Beim Beispiel I) komme ich auf keinen Widerspruch. Hier wollte ich dann wissen ob jemand einen guten Trick/Algorithmus oder sonstwas kennt, um einen einfachen/schlichten Graphen mit vorgegebenen Knotengraden zu zeichnen, ohne "Rumprobieren". Viele Grüße, uhmdunnolol |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
