Baum Abhängigkeit

Neue Frage »

04.01.2010, 15:07	Maria9988	Auf diesen Beitrag antworten »
Baum Abhängigkeit Also habe gerade nen ziemliches Problem eine Aufgabe hier zu lösen. Es sein ein Baum T=(V,E) mit n-Knoten gegeben. Dazu der Durchschnittsgrad d(T):=1/n*\sum\limits_{v e V} deg(v) v e V soll v Element von V bedeuten. Wie groß ist n in Abhängigkeit von d(T) ? Gesucht it also eine Funktion f:\mathbb N ---> \mathbb N , welche den Durchschnittsgrad d(T) auf die Anzahl der Knoten von T abbildet. Komme hier leider nicht weiter bzw finde ich keinen wirklichen Ansatz um diese Aufgabe zu lösen. Wäre nett wenn mir da jemand helfen könnte.
04.01.2010, 15:09	Maria9988	Auf diesen Beitrag antworten »
Also habe gerade nen ziemliches Problem eine Aufgabe hier zu lösen. Es sein ein Baum T=(V,E) mit n-Knoten gegeben. Dazu der Durchschnittsgrad d(T):=1/n* $\begin{eqnarray} \sum\limits_{v e V} deg(v) \end{eqnarray}$ v e V soll v Element von V bedeuten. Wie groß ist n in Abhängigkeit von d(T) ? Gesucht it also eine Funktion f: $\begin{eqnarray} \mathbb N \end{eqnarray}$ ---> $\begin{eqnarray} \mathbb N \end{eqnarray}$ , welche den Durchschnittsgrad d(T) auf die Anzahl der Knoten von T abbildet. Komme hier leider nicht weiter bzw finde ich keinen wirklichen Ansatz um diese Aufgabe zu lösen. Wäre nett wenn mir da jemand helfen könnte.
04.01.2010, 15:17	kiste	Auf diesen Beitrag antworten »
Hallo, wie viele Kanten besitzt den ein Baum? Kannst du die Anzahl der Kanten mit der Summe über die Grade in Beziehung bringen?
04.01.2010, 15:53	Maria9988	Auf diesen Beitrag antworten »
also ein Baum mit n-Knoten sollte ja n-1 Kanten haben oder? Bsp: n=4 also 4 Knoten --> 3 Kanten also habe ich mind 2 Knoten mit dem Grad von 2(restlichen 2 Knoten mit grad=1) oder einen Knoten mit dem grad 3 (restliche Knoten mit grad=1) Nun kann ich mir das schon gut vorstellen aber daraus eine Abhängigkeit zu bilden klappt nicht wirklich, da ich ja auch noch verschiedene Möglichkeiten habe wie der Baum aussehen soll....
04.01.2010, 16:06	kiste	Auf diesen Beitrag antworten »
Ja, das stimmt. Da wird über alle Grade summieren macht es aber nichts aus wie konkret der Baum aussieht. Versuche doch einmal einen Zusammenhang zwischen der Anzahl der Kanten und der Summe über alle Grade zu finden. Wenn du eine Kante hast, wie trägt diese dann zu den Graden bei?
04.01.2010, 16:28	Maria9988	Auf diesen Beitrag antworten »
Eine Kante hat eigentlich immer 2 Knoten. UNd diese 2 Knoten hätten jeweils einen Grad von 1 (in diesem Fall) bei 4 Kanten: mind 5 Knoten und habe je nachdem wie ich den Baum zeichne ein Knoten mit Grad von 4 (maximum) und 4 Knoten mit dem grad von 1 (minimum) also wäre der Maximale Grad eines Knoten bei 4 Kanten = 4 . maximal grad eines beliebigen Knotens = anzahl der Kanten stimmt das so?
Anzeige

04.01.2010, 16:34	kiste	Auf diesen Beitrag antworten »
"Eine Kante hat eigentlich immer 2 Knoten." Genau. Also zählt eine Kante 2mal zu den Graden dazu. Versuche doch jetzt einmal einen Zusammenhang zwischen $\begin{eqnarray} \sum_{v\in V} d_v \end{eqnarray}$ und $\begin{eqnarray} \|E\| \end{eqnarray}$ zu finden. Falls du es nicht direkt siehst mache ein paar Beispiele und rechne jeweils diese beiden Terme für die Beispiele aus
05.01.2010, 08:22	Maria9988	Auf diesen Beitrag antworten »
der Zusammenhang ist der das die Summe aller Grade genau doppelt soviel ist wie es Kanten gibt. bei 3 Kanten ist die Summe der Grade = 6 bei 4 Kanten ist die Summe der Grade = 8 wäre n jetzt gleich: n*2 ? Was bedeutet das nun hinsichtlich des Durchschnittsgrades?
05.01.2010, 08:38	kiste	Auf diesen Beitrag antworten »
Na den Rest darfst du wohl selbst umformen. Du hast doch jetzt: n-1 = e n*d(T) = 2e Jetzt das ganze nur noch umstellen
05.01.2010, 08:53	Maria9988	Auf diesen Beitrag antworten »
ja jetzt sollte es gehen wollte mich nur noch mal versichern das dass was ich gemacht habe richtig ist bzw ich auf dem richtigen Weg bin danke für deine Hilfe

Neue Frage »

Antworten »

Baum Abhängigkeit

Verwandte Themen