 |
 |
 |
 |
 |
 |
Startseite » Forum » Graphentheorie / Möglichen Paare bestimmen
Graphentheorie / Möglichen Paare bestimmen
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Sei ein Baum mit Knoten von Grad eins, alle weiteren Knoten von seien von Grad 4 oder 5. Bestimmen Sie die möglichen Paare an Anzahlen für Knoten mit Grad 4 und 5. (Also beispielsweise für drei 4er Knoten und sieben 5er Knoten.) Argumentieren Sie bitte die Korrektheit und Vollständigkeit Ihrer Lösung Hallo! Ich verstehe hier nicht ganz was ich hier machen muss oder wie ich hier vorzugehen habe. Die Aufgabe scheint eigentlich relativ einfach zu sein, aber vielleicht denke ich auf irgendwie gerade viel zu kompliziert... Kann mir jemand die Aufgabe vielleicht kurz erklären oder zeigen wie man das macht? Würde mich sehr freuen, wenn mir hier jemand helfen könnte. :-) Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo,, ich nenne die Knoten mit Grad 4 und Grad 5 der Kürze halber "Igel". Da der Graph ein Baum sein soll, kann es nur sein, dass er aus einer Kette direkt jeweils über eine Kante miteinander verbundener Igel besteht. Die Enden dieser Kette bestehen dann aus zwei 4-Igeln, zwei 5-Igeln, oder ein Ende ist ein 4-Igel, das andere ein 5-Igel. Nun überlege man sich für jeden dieser drei Fälle, welche Zwischenigel in Frage kommen, um die Anzahl von 14 Blättern zu erhalten. Zum Vergleich: Ich habe als Ergebnis die Paare (ohne Gewähr ;-)) Gruß ermanus |
 |
|
Sehr schöne und ausführliche Erklärung, vielen Dank! :-) Aber... ich denke ich muss da noch ein wenig Theorie nachfragen bevor ich die Aufgabe dann verstehe kann. Was genau bedeuten diese ganzen Grade hier? Ein Knoten mit Grad 4? Heißt das, dass hier sozusagen 4 Kanten diesen Knoten annähern? Und was genau ist ein Baum von Grad 1? Das bedeutet doch, dass die Knoten von Grad dann Blätter heißen, oder? Und wie kann ich mir so ein Graph genau vorstellen? Du hast ja zum Beispiel dieses Paar hier das heißt es gibt 4 mal 5-Igeln. Sieht dann der Graph ungefähr so aus? (Siehe Anhang) Tut mir leid, dass ich dich da gerade mit Fragen überhäufe... :-D)  |
|
|
|
(i) Ja: Grad=Anzahl der Kanten an einen Knoten (ii) Ein Baum ist ein Zykelfreier zusammenhängender Graph. Ein Knoten mit Grad 1 heißt auch Blatt. (iii) siehst du im anhängenden Bild realisiert. Du hast ja dann 14 Blätter und 4 5-Igel. In deinem Bild sind zu viele Blätter und zudem mehrere Knoten mit Grad 2.  |
|
|
|
In meiner Argumentation steckt noch ein Fehler. Die "Igel" müssen nicht in einer Kette vorliegen, sondern können auch anders angeordnet sein, siehe Bild.  |
|
|
|
So soll das ganze also aussehen, jetzt ist mir einiges klar. Wieder mal eine schöne und wunderbare Erklärung, vielen Dank! :-D) Und wie kann ich das ganze irgendwie am Besten beweisen bzw. argumentieren, dass die Lösung so stimmt? |
|
|
|
Vielleicht so: Sei die Anzahl der Knoten vom Grad 4 und der vom Grad 5. In einem Baum gilt notwendig , das bedeutet hier , umgestellt . Das ist nur durch die drei -Paare (6,0), (3,2) und (0,4) erfüllbar, wie ermanus oben schon ausgeführt hatte. Zur vollständigen Lösung gibt man zu jedem der drei Paare auch noch einen passenden Graphen an, das sollte keine Schwierigkeiten machen. |
|
|
|
Oh, ja das ist natürlich ein schöner und kurzer Beweis, vielen Dank dafür! :-D) Damit ich das ganze richtig verstehe: Also in einem Baum gilt ja allgemein das heißt Du hast es quasi umgeformt auf die Anzahl der Knoten, daher haben wir hier . Warum müssen wir die Anzahl der Kanten eigentlich halbieren bzw. durch 2 dividieren, also diesen Teil hier: |
|
|
|
Das ist das Handschlag-Lemma (handshake lemma): Jede Kante zählt bei ihren beiden Endknoten im Knotengrad mit, also insgesamt doppelt. |
 |
|
Oh, dann ist mir jetzt diesmal wirklich ALLES klar. Jetzt gibt es dafür ewige Dankbarkeit von mir! :-D) |
|
|
|
Oh, dann ist mir jetzt diesmal wirklich ALLES klar. Jetzt gibt es dafür ewige Dankbarkeit von mir! :-D) |
1538146
1538070