matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieBeweis von Cayleys Formel
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Graphentheorie" - Beweis von Cayleys Formel
Beweis von Cayleys Formel < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Beweis von Cayleys Formel: Bijektionsbeweis mit Tieren
Status: (Frage) überfällig Status 
Datum: 11:01 Mo 29.11.2010
Autor: Espresso-Junkie

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) ???

        
Bezug
Beweis von Cayleys Formel: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:20 Di 14.12.2010
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]