Knotengrade < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:41 Di 24.01.2006 | | Autor: | dump_0 |
Hallo.
Sei [tex]D = {d_1,...,d_n} mit n \ge 2[/tex] eine Folge von natürlichen Zahlen größer 0.
Wenn es einen Baum mit Gradseqquenz D gibt, dann gilt:
[tex] \summe_{i=1}^{n}d_i = 2n - 2[/tex].
Nun soll ich mit Induktion über n zeigen das auch die Gegenrichtung hierfür gilt. Könnte mir bitte jemand sagen was hier mit Gegenrichtung gemeint ist, etwa das T ein Baum ist, wenn obige Gleichung gilt ?
Mfg
[mm] dump_0
[/mm]
|
|
| |
|
Hallo [mm] dump_0, [/mm]
und hallo Freunde der Graphentheorie !
Gleich folgt ein feierlicher Moment, Ihr werdet's dann sehen...
Zur Frage:
Du sollst zeigen: Wenn die Sequenz [mm] d_1,\ldots [/mm] , [mm] d_n [/mm] die Eigenschaft
[mm] \sum_{i=1}^nd_i=2n-2 [/mm] hat, dann gibt es einen Baum mit n Knoten und Gradsequenz [mm] d_1,\ldots [/mm] , [mm] d_n.
[/mm]
Konstruiere den einfach via Induktion: Nimm einen Knoten vom Grad [mm] d_1,
[/mm]
dann vereinfacht sich die verbleibende Sequenz usw.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:05 Di 24.01.2006 | | Autor: | dump_0 |
Hallo Mathias.
Danke für deine Antwort.
Ich verstehe leider nicht ganz wie ich den Beweis jetzt beginnen soll.
Wenn ich mir einen Knoten vom Grad [mm] d_1 [/mm] hernehme ex. noch weitere n-1 vom Grad [mm] d_i [/mm] 2 [mm] \le [/mm] i [mm] \le [/mm] n.
Wie soll ich jetzt fortfahren ? :)
Mfg
[mm] dump_0
[/mm]
|
|
|
| |
|
Hallo,
fang also mit einem beliebigen Knoten an, sagen wir [mm] v_1, [/mm] und gib ihm [mm] d_1 [/mm] Nachbarn,
zB [mm] v_2,\ldots [/mm] , [mm] v_{d_1+1}.
[/mm]
Dann ist [mm] v_1 [/mm] erledigt und wir koennen ihn aus der Betrachtung streichen.
Nun ersetzen wir [mm] d_2 [/mm] durch [mm] d_2-1,\ldots [/mm] , [mm] d_{d_1+1} [/mm] durch [mm] d_{d_1+1}-1.
[/mm]
Problem nun: Wir wollen ja jetzt nicht mit Waeldern weiterrechnen (mal es Dir mal auf !), sondern induktiv mit einer Baumkonstruktion.
Also: Kontrahiere [mm] v_2,\ldots v_{d_1+1} [/mm] zu einem Knoten mit d-Wert gleich Summe der
aktualisierten d-Werte der Knoten [mm] v_2,\ldots [/mm] , [mm] v_{d_1+1} [/mm] und den restlichen unveraenderten d-Werten.
Diese neue Sequenz (ich schreib sie mal hin in Termen der urspr. Sequenz [mm] d_1,\ldots d_n)
[/mm]
[mm] d_2-1+\ldots [/mm] + [mm] d_{d_1+1}-1, d_{d_1+2},\ldots d_n
[/mm]
erfuellt wieder die Eigenschaft: wir haben [mm] n-(d_1+1) [/mm] Knoten, und es ist
[mm] \sum_{i=2}^nd_i^{neu} [/mm] = 2n-2 [mm] -2\cdot d_1 [/mm] = [mm] 2(n-d_1-1), [/mm] also konstruiere induktiv einen Baum dafuer und ersetze anschliessend den ersten Knoten durch den Knoten vom Grad [mm] d_1 [/mm] mit [mm] d_1 [/mm] Nachbern, teile die [mm] d_2+\ldots +d_{d_1+1}-d_1 [/mm] Nachbarn
des neuen ersten Knoten unter diesen gemaess der Werte [mm] d_2-1,\ldots d_{d_1+1}-1
[/mm]
auf.
Viele Gruesse,
Mathias
|
|
|
|
