T = (V, E) Baum mit n Knoten und Durch.grad. d(T) := 1/n * Σ(u∈V)deg(v). Wie groß ist n in Abhängigkeit von d(T)?

Question

Sei T = (V, E) ein Baum mit n Knoten und dem Durchschnittsgrad

d(T) := 1/n * Σ(u∈V)deg(v). Wie groß ist n in Abhängigkeit von d(T)?

Hinweis: Gesucht ist eine Funktion f, die den Durchschnittsgrad d(T) auf die Anzahl der Knoten von T abbildet.

Wie kann man da vorgehen?

Answer 1

Es gibt n-1 Kanten, also einen gesamten Grad von 2n-2.

Mit den n Knoten, ergibt das einen durchschnittlichen Grad von 2 - 2/n.

Jetzt hast du also den durchschnittlichen Grad q.

2 - q = 2/n
(2 - q)/2 = 1/n
2/(2 - q) = n

F (q) = 2 / (2-q) gibt also die Anzahl der Knoten an, die sich aus dem durchschnittlichen Grad eines Knotens in einem Baum ergeben.