Aufgabe 2 < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:10 Do 03.11.2011 | | Autor: | Mija |
| Aufgabe | Sei $G = (V,E)$ ein endlicher Baum mit $|V| [mm] \ge [/mm] 2$ . Für $n [mm] \in \IN$ [/mm] bezeichne $ n$ die Anzahl Knoten von $G$ mit Grad $n$. Man zeige:
(a) [mm] $\sum\nolimits_{n \ge 1} \alpha_n [/mm] * (2-n) = 2$
(b) [mm] $deg_G \le \alpha_1$ [/mm] für alle $A [mm] \in [/mm] V$ . |
Hallo, ich habe Probleme mit obenstehender Aufgabe und leider leider auch keine Idee dazu, wie ich da rangehen kann.
Ich würde mich sehr freuen, wenn mir jemand weiterhelfen könnte!
|
|
| |
|
Hallo Mija!
> Sei [mm]G = (V,E)[/mm] ein endlicher Baum mit [mm]|V| \ge 2[/mm] . Für [mm]n \in \IN[/mm]
> bezeichne [mm] n[/mm] die Anzahl Knoten von [mm]G[/mm] mit Grad [mm]n[/mm]. Man
> zeige:
> (a) [mm]\sum\nolimits_{n \ge 1} \alpha_n * (2-n) = 2[/mm]
> (b)
> [mm]deg_G \le \alpha_1[/mm] für alle [mm]A \in V[/mm] .
> Hallo, ich habe Probleme mit obenstehender Aufgabe und
> leider leider auch keine Idee dazu, wie ich da rangehen
> kann.
>
> Ich würde mich sehr freuen, wenn mir jemand weiterhelfen
> könnte!
zu a)
Wieviele Kanten $|E|$ hat ein endlicher Baum mit $|V|$ Ecken? Wie hängt $|E|$ mit der Summe der Eckengrade zusammen? Wie hängt [mm] $\sum\limits_n \alpha_n$ [/mm] mit der Anzahl der Ecken zusammen?
zu b)
Wieviele Wege gibt es zwischen zwei Ecken?
LG mathfunnel
|
|
|
|
