Beweis von Cayleys Formel < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Vorab: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo zusammen!
Sitze immer noch an den Beweisen für Cayleys Formel für die Anzahl der Bäume. Diesmal am Bijektionsbeweis.
Habe im Buch "Diskrete Mathematik" von Matousek den Wirbeltierbeweis gefunden und finde den ganz gut. Leider verstehe ich darin nicht alles, deshalb hab ich noch einige Fragen:
a) Grundsätzlich: Kann man den Beweis so aufschreiben oder sind Fehler enthalten? (Graphen sollen die Teilnehmer selbst mitmalen, deshalb sind sie für euch aus dem Buch zu entnehmen, z.B. bei google-books)
b) Warum erhält man aus jedem aufspannenden Baum des Kn n² Wirbeltiere? -> Frage selbst beantwortet: Man kann ja die Anfangsmarkierung auf n-Arten wählen und die Schlussmarkierung auf n-Arten, macht also n²?!
c) Warum besitzt eine n-Menge [mm] n^n [/mm] Abbildungen in sich selbst? (Gibt es da einen Satz dazu?) -> Frage ebenfalls selbst beantwortet: Wenn man n Objekte hat, gibt es ja n-Verschiedene Möglichkeiten, es abzubilden, macht also [mm] n^n [/mm] Möglichkeiten.
d) Beweise für Injektivität und Surjektivität: Weiß nicht, wie ich das anstellen soll... Ich tu mich schon schwer, bei der genauen Benennung der Abbildung. Ist diese f: W->V ? Also von der Menge der Wirbeltiere zu der Eckenmenge eines gerichteten Graphen? Oder verstehe ich das falsch?!
Wär super, wenn mir jemand weiterhelfen könnte!
Geg.: Aufspannender Baum des vollständigen Graphen [mm] K{}_{n}
[/mm]
Markiere eine Ecke mit [mm] \squareund [/mm] die andere mit [mm] \mathcal{\text{◯}}
[/mm]
Bäume mit solchen Markierungen werden im Folgenden Wirbeltiere genannt. Schreibe [mm] \mathcal{W} [/mm] für die Menge aller Wirbeltiere.
Aus jedem aufspannenden Baum des [mm] K{}_{n}erhalten [/mm] wir n² Wirbeltiere. Also ist die Anzahl [mm] T(K{}_{n}) [/mm] aller aufspannenden Bäume gleich [mm] \frac{\left|W\right|}{n\text{\texttwosuperior}}.
[/mm]
Bestimme nun die Anzahl der Wirbeltiere.
Lemma: Es git eine Bijektion F zwischen der Menge [mm] \mathcal{W} [/mm] aller Wirbeltiere und der Menge aller Abbildungen der Eckenmenge [mm] \mathcal{V} [/mm] in sich selbst.
Eine n-Menge besitzt [mm] n{}^{n}Abbildungen [/mm] in sich selbst. Also gibt es nach dem Lemma ebensoviele Wirbeltiere.
[mm] \Longrightarrow [/mm] Es gibt also [mm] n{}^{n-2}aufspannende [/mm] Bäume im [mm] K{}_{n}.
[/mm]
Beweis Lemma:
Betrachte die Wirbelsäule von [mm] \mathcal{\text{◯}}bis \squareund [/mm] schreibe wie folgt:
[mm] \begin{array}{ccccccc}
3 & 4 & 7 & 8 & 9 & 14 & 15\\
8 & 4 & 14 & 9 & 3 & 7 & 15\end{array}
[/mm]
Definiere den gerichteten Hilfsgraphen H: Die Ecken von H sind die Wirbel und die gerichteten Kanten verlaufen von den Wirbeln aus der ersten Zeile zu den Wirbeln aus der zweiten Zeile. Weil in jede Ecke je eine Kante hinein- und eine hinausführt, ist H disjunkte Vereinigung gerichteter Kreise.
[mm] \Longrightarrow [/mm] Die Wirbelsäule definiert eine Permutation der Wirbel und H besteht aus Zyklen dieser Permutation.
Zeichne die Zyklen von H:
Betrachte nun wieder das komplette Wirbeltier W. Wenn man die Kanten aus der Wirbelsäule entfernt, zerfällt das Wirbeltier in Komponenten, die wieder Bäume sind. Richte die Kanten in den Komponenten so, dass sie zu dem einen Wirbel in dieser Komponente zeigen.
Definiere einen weiteren gerichteten Hilfsgraphen auf der Eckenmenge V: Seine Kanten sind alle gerichteten Kanten aus den Komponenten plus die Kanten von H.
Zeichne vollständigen gerichten Graphen G:
Behauptung: G ist der Graph einer Abbildung, d.h. as jeder Ecke führt genau eine Kante heraus.
Für die Wirbel ist das klar: H besteht aus gerichteten Zyklen, also hat jede Ecke in H Aus-Grad=Ein-Grad=1, im weiteren Verlauf der Konstruktion von G kommen nur Kanten dazu, die zu den Wirbeln hin gerichtet sind. Für die anderen Ecken stimmt die Behauptung, weil es einen eindeutigen Weg von jeder Ecke von W zur Wirbelsäule gibt.
Der gerichtete Graph G definiert uns folgende Abbildung:
f: [mm] \left\{ 1,2,\ldots,n\right\} \rightarrow\left\{ 1,2,\ldots,n\right\} [/mm] : [mm] \forall i\in [/mm] V: f(i) = j mit j als diejenige Ecke aus G, in der die eindeutige Kante, die aus i herausführt, endet.
In unserem Beispiel:
[mm] 1\mapsto7, 2\mapsto15, 3\mapsto8, 4\mapsto4, 5\mapsto2, 6\mapsto5, 7\mapsto14, 8\mapsto9, 9\mapsto3, 10\mapsto4, 11\mapsto10, 12\mapsto4, 13\mapsto12, 14\mapsto7, 15\mapsto15, 16\mapsto7, 17\mapsto16, 18\mapsto1, 19\mapsto8
[/mm]
kurz:
f [mm] =\left(\begin{array}{ccccccccccccccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19\\
7 & 15 & 8 & 4 & 2 & 5 & 14 & 9 & 3 & 4 & 10 & 4 & 12 & 7 & 15 & 7 & 16 & 1 & 8\end{array}\right)
[/mm]
So erhält man zu jedem Wirbeltier W eine Abbildung F(W).
Bleibt nur noch zu zeigen, dass diese Abbildung eine Bijektion ist:
a) F ist injektiv [mm] \Leftrightarrow\forallW{}_{1},W{}_{2}\in\mathcal{W}: W{}_{1}\neq W_{2}folgt F(W_{1})\neq F(W_{2})
[/mm]
Beweis durch Widerspruch: Sei [mm] W{}_{1}= W{}_{2}\Rightarrow??? [/mm] wie geht es weiter?!
b) F ist surjektiv [mm] \Leftrightarrow\forallf(W) \inF(W) \existsW \in\mathcal{W}: [/mm] F(W) = f(W) ???
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Di 14.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
