Graphentheorie Aufgabe |
| 11.06.2012, 12:01 | Shaggz118 | Auf diesen Beitrag antworten » | ||
| Graphentheorie Aufgabe Hallo Leute Wink , Ich sitze immoment vor meinem Diskrete Strukturen Zettel und bin irgendwie am verzweifeln. Die Aufgabe Lautet: Wenn G = (V,E) ein zusammenhängender Graph mit |E| = 21 und deg(v)>=3 für alle v Element V ist, wie groß ist |V| maximal? (Begründen Sie Ihre Antwort oder geben Sie eine Berechnung an.) Irgendwie hänge ich an der Aufgabe. Vermutlich ist die Lösung ganz einfach aber ich komm einfach nich drauf verwirrt . Meine Ideen: Also überlegt habe ich mir: Die maximale Anzahl an Knoten für einen zusammenhängenden Graph mit 21 Kanten wäre ja 22 Knoten. Nun geht das aber nicht weil gefordert wird das der Grad der Knoten mindestens 3 ist. Meine Frage ist nun wie gelange ich an so ein Konstrukt mit dem Grad 3 oder höher? Einfach aufmalen und rumtesten? In der Vorlesung gabs nicht wirklich eine Hilfestellung dazu. MFG Shaggz |
||||
| 11.06.2012, 12:49 | Mystic | Auf diesen Beitrag antworten » | ||
RE: Graphentheorie Aufgabe
Un du bist dir absolut sicher, dass ihr das sog. Handschlaglemma in der Vorlesung nicht gemacht habt? 
Sorry, aber das kann ich einfach nicht glauben, denn das ist ja immer der allererste Satz über Graphen überhaupt... |
||||
| 11.06.2012, 12:59 | Shaggz118 | Auf diesen Beitrag antworten » | ||
Hey also erstmal danke für die Antwort. Ja doch wenn ich mir das so angegucke so was ähnliches haben wir in der Vorlesung gemacht. Aber unser Prof. schreibt sich immer selber Definitionen die etwas undurchsichtig sind. Zur Aufgabe: Wenn ich nach dem Lemma vorgehe nehme ich mir natürlich den niedrigst möglichen Grad, da man son mehr Knoten unterbringen kann. Also 3. Nach dem Lemma muss ich nun also gucken, dass ich mit dem Grad 3 und einer unbekannten Anzahl an Knoten auf 42 komme (2*21Kanten). Somit komme ich dann auf 14 Knoten. Ist das richtig so? |
||||
| 11.06.2012, 13:07 | Mystic | Auf diesen Beitrag antworten » | ||
Nach dem Lemma solltest du darauf achten, dass die Anzahl der Knoten mal deren minimalen Grad 42 nicht übersteigt, das ist ja wohl nicht ganz dasselbe... 
Und ja, daraus kommt man dann auf die von dir genannte maximale Anzahl an Knoten... |
||||
| 11.06.2012, 13:16 | Shaggz118 | Auf diesen Beitrag antworten » | ||
Okay habs verstanden 
Ich danke dir vielmals für die schnelle Hilfe 
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
