Beweis von Cayleys Formel < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen!
Muss für einen Seminarvortrag Cayleys Formel auf unterschiedliche Arten beweisen und hänge am Beweis durch Doppeltes Abzählen nach Pitman.
Habe jetzt den Beweis aus diesem Skript durchgearbeitet: http://www.mathematics.uni-bonn.de/events/schuelerwoche/baeume_v3.pdf (S. 9f) und verstehe nicht, wie man von der Mächtigkeit von B(i+1) auf die Mächtigkeit von B(n-1) schließen kann...
Habe mir dazu auch die Beweise in "Diskrete Mathematik" von Matousek und dem "Buch der Beweise" angesehen, aber irgendwie wird mir das zweite Abzählen nicht so wirklich klar.... Ich verstehe die Logik des Wegnehmens bzw. Hinzunehmens von Kanten, aber wie man auf die Formeln kommt, ist mir unverständlich. Am verständlichsten fand ich jedoch noch den Beweis aus dem obigen Skript.
Ich hoffe, ihr könnt mir weiterhelfen.
# Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. Und ja, es ist mein erster Beitrag dieser Art 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:27 So 14.11.2010 | | Autor: | felixf |
Moin!
> Hallo zusammen!
>
> Muss für einen Seminarvortrag Cayleys Formel auf
> unterschiedliche Arten beweisen und hänge am Beweis durch
> Doppeltes Abzählen nach Pitman.
>
> Habe jetzt den Beweis aus diesem Skript durchgearbeitet:
> http://www.mathematics.uni-bonn.de/events/schuelerwoche/baeume_v3.pdf
> (S. 9f) und verstehe nicht, wie man von der Mächtigkeit
> von B(i+1) auf die Mächtigkeit von B(n-1) schließen
> kann...
Es ist $|B(0)| = 1$.
Es wird gezeigt: $|B(i + 1)| = n (n - (i + 1)) |B(i)|$. (Der zweite Teil des Beweises von Satz 6; auf Seite 9 unten und Seite 10 oben.)
Damit ist also
$|B(n - 1)| = n (n - (n - 1)) |B(n - 2)| = n (n - (n - 1)) [mm] \cdot [/mm] n (n - (n - 2)) |B(n - 3)| = n (n - (n - 1)) [mm] \cdot [/mm] n (n - (n - 2)) [mm] \cdot [/mm] n (n - (n - 3)) |B(n - 4)| = [mm] \dots$.
[/mm]
Oder anders aufgezogen:
$|B(1)| = |B(0 + 1)| = n (n - (0 + 1)) |B(0)| = n (n - 1)$,
$|B(2)| = |B(1 + 1)| = n (n - (1 + 1)) |B(1)| = n (n - 2) [mm] \cdot [/mm] n (n - 1) = [mm] n^2 [/mm] (n - 1) (n - 2)$,
$|B(3)| = |B(2 + 1)| = n (n - (2 + 1)) |B(2)| = n (n - 3) [mm] \cdot n^2 [/mm] (n - 1) (n - 2) = [mm] n^3 [/mm] (n - 1) (n - 2) (n - 3)$.
Man zeigt schnell per Induktion, dass $|B(i)| = [mm] n^i \prod_{k=1}^i [/mm] (n - k)$ ist. Fuer $i = n - 1$ ist also $|B(n - 1)| = [mm] n^{n - 1} \prod_{k=1}^{n-1} [/mm] (n - k)$.
Schliesslich ist [mm] $\prod_{k=1}^{n-1} [/mm] (n - k) = [mm] \prod_{k=1}^{n-1} [/mm] k = (n - 1)!$.
Hilft dir das weiter?
Wenn nicht, frag bitte etwas praeziser.
LG Felix
|
|
|
| |
|
Hallo Felix,
vielen Dank für deine Antwort! Tut mir leid, dass ich mich erst jetzt melde, aber Cayley und Pitman haben mich so umgehaun, dass ich krank wurde und erst jetzt wieder ins Forum geguckt habe.
Hat mir sehr weitergeholfen
|
|
|
| |
|
Nachdem ich festgestellt habe, dass der Beweis mit SUKOWUBs vielleicht "wissenschaftlicher" ist (siehe "Diskrete Mathematik" Matousek), wollte ich diesen vorstellen.
Jetzt hänge ich aber gerade wieder am gleichen Problem: Ich komme nicht auf die Anzahl der Möglichkeiten beim 2. Abzählen und bin zu dumm, es von dem anderen Beweis zu übertragen... Denn dort zähle ich ja die Mächtigkeit, also die Anzahl der Wurzelwälder und im SUKOWUB-Beweis ja die Anzahl der Möglichkeiten.
Ich hab da wirklich Schwierigkeiten... Felix hat es so gut aufgeschrieben und isoliert betrachtet, kann ich es nachvollziehen, aber nicht in den SUKOWUB-Beweis einbauen.
Außerdem stellt sich mir noch die Frage, warum B(0)=1... Wenn da jeder Knoten eine Wurzel ist, hab ich sozusagen einen einzigen Wurzelwald, oder wie?! War mir damals noch nicht so bewusst, warum das gilt.
Hier der von mir so aufgeschriebene Beweis:
3.2 Beweis durch doppeltes Abzählen
In diesem Beweis zählt man SUKOWUBs, also SUkzessive KOnstruierte WUrzelBäume.
Ein SUKOWUB ist ein Tripel (T, r, l), bestehend aus einem Baum T auf der Eckenmenge V = {1, 2, ..., n} (mit n als fester, ganzer Zahl), einer Wurzel r [mm] \inV [/mm] und einer Markierung l der Kanten von T mit Zahlen {1, 2, ..., n-1}, d.h. l ist Bijektion: l: E(T) [mm] \rightarrow{1, 2, ..., n}
[/mm]
Beispiel SUKOWUB:
1. Abzählen
Beginne mit der Eckenmenge V und einer leeren Kantenmenge. Konstruiere durch schrittweises Hinzufügen der Kanten einen Wurzelbaum, wobei l die Reihenfolge codiert, in der die Kanten hinzugefügt wurden.
Bei jedem Baum T kann man die Wurzel r auf n Arten und die Markierung l auf (n-1)! Arten wählen.
[mm] \Rightarrow [/mm] Es gibt insgesamt [mm] n*(n-1)!*T(K_{n}) [/mm] SUKOWUBS.
2. Abzählen
Fasse die Wurzelbäume zunächst als orientierte Bäume auf, bei denen alle Kanten auf die Wurzel hin gerichtet sind.
Die Wurzel ist dann die eindeutige Ecke, aus der keione Kante herausführt, d.h. die Wurzel ist die einzige Ecke mit Ausgrad 0. Andererseits korrespondiert jede Orientierung des Baumes, in der genau eine Ecke den Ausgrad 0 hat, zu einem eindeutigen Wurzelbaum.
Bestimme nun, auf wie viele Arten man aus dem leeren gerichteten Graph durch schrittweises Hinzufügen gerichteter Kanten in (n-1) Schritten einen solchen speziell orientierten Baum erzeugen kann.
Dabei müssen folgende Regeln beachtet werden:
(A) Man darf keinen Kreis erzeugen.
(B) Am Ende muss in jeder Ecke außer der Wurzel eine Kante beginnen.
1. Kante: n*(n-1) Möglichkeiten
2. Kante: (n-2)*(n-1)+(n-2) = n*(n-2) Möglichkeiten
k-te Kante: n*(n-k) Möglichkeiten
In jeder Komponente des bisher konstruierten Graphen gibt es genau eine Ecke mit Ausgrad 0. Das folgt aus der Tatsache, dass jede Komponente mit m Ecken m-1 Kanten hat.
Zu dem Zeitpunkt, an dem man bereits k Kanten ausgewählt hat, hat man folglich n-k Komponenten.
Beispiel für k=4
Die nächste Kante, die mit k+1 markiert wird, kann in eine beliebige Ecke hineinführen, beginnen muss sie jedoch in der Wurzel einer anderen Komponente. Dafür hat man n*(n-k-1) Möglichkeiten.
Konstruiere also in n-1 Schritten einen SUKOWUB.
Damit ist die Gesamtzahl aller SUKOWUBs:
[mm] \prod [/mm] n*(n-k-1)= [mm] (n-1)!*n{}^{n-1} [/mm]
Zusammenfassend also:
[mm] n*(n-1)!*T(K_{n}) [/mm] = [mm] (n-1)!*n{}^{n-1}
[/mm]
[mm] T(K_{n})= n{}^{n-2}
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Di 14.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
