Graphen Wurzelbäume

Sima · Anmeldungsdatum: 04.05.2005 Beiträge: 9

Wieveile Knoten und wie viele Blätter hat ein Wurzelbaum der Höhe h vom Grad gamma mindestens?Wie viele Knoten hat er höchstens??

kann mir jemand bei dieser fragenstellung mehr auskunft geben oder ein tipp??

ich habe dazu folgende überlegung gemacht:Jeder Baum mit mindestens 2 KNoten hat mindestens 2 Blätter...

mfG

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Also Wurzelbaum verstehe ich, Knoten und Höhe auch. Aber Grad? Meinst du den Maximalgrad eines Knotens, also den maximalen Verzweigungsgrad? Oder den Minimalgrad? Oder muss der Grad für Nicht-Blätter exakt stimmen?

Ist die Wurzel bei euch auch ein Blatt?

Sima · Anmeldungsdatum: 04.05.2005 Beiträge: 9

ich habe da als ergebnis stehen:

Ein Wurzelbaum T der Höhe 3, Grad des Baumes gamma(T)=3
Blätter:ich habe die als Blätter gezählt die keine Nachfolger haben.also deg out=0!
Innere Knoten habe ich aufgezählt und hatte für die Knoten höchstens 4 in meinem Baum raus und 6 Blätter??reicht das???ich weiss jetzt nicht wie das alllgemeiner fasssen sol bezogen auf die frage..denn ich weiss ja nicht ob ich selber ein Wurzelbaum zeichnen soll und dann erklären was was ist???

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Kurz: Was ist gamma(T) ?

Sima · Anmeldungsdatum: 04.05.2005 Beiträge: 9

also dieses gamma zeichen habe ich ausgeschrieben.das bezieht sich auf den grad...also grad=niveau ZB:3 oder 4 oder 2..fängt von der wurzel an..wurzel ist grad 0??das meine ich damit

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

"Grad" kenn ich anders. Sicher, dass du das richtig verstanden hast?

Der Grad eines Knotens ist bei mir die Anzahl der Kanten, die von diesem Knoten ausgehen.

Nun redest du aber vom Grad des Baumes. Also entweder du meinst also den maximalen Verzweigungsgrad oder was ganz anderes?

Sima · Anmeldungsdatum: 04.05.2005 Beiträge: 9

redest du nicht vom ausgangsgrad???

ich meine ein wurzelbaum vom Grad gamma..bei mir in der definition steht gamma(T)=max deg out (v) velement vonV

deg out ist doch der ausgangsgrad??ich glaube ich liege falsch.. unglücklich

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Nene, jetzt weiß ich bescheid.

Gamma(T) = Maximaler ausgehender Grad der Knoten im Baum.

Mehr wollte ich nicht wissen. Deine Beschreibung mit "Niveau" hat mich durcheinander gebracht. Dann weiß ich nicht, wie rum ein Wurzelbaum gerichtet ist. D.h. ist wirklich der Grad der Wurzel 0 oder meinst du den Grad der Blätter. (Ein Blatt hat keinen Nachfolger).

Dann zu deiner Frage:

Sima · Anmeldungsdatum: 04.05.2005 Beiträge: 9

kann ich auch einen vollständigen binärbaum nehmen??oder ist das was anderes

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Ein Binärbaum hat pro Knoten nur maximal 2 Nachfolger (deshalb heißt er Binärbaum). Ein Baum vom Grad gamma hat aber maximal gamma viele Nachfolger.

In dem Bild siehst du einen vollständigen Binärbaum (blau) und einen ternärbaum (rot). Der Ternärbaum hat einen Gamma-Wert von 3, der Binärbaum einen von 2.