0 Daumen
688 Aufrufe

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?

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community