Anzahl der Spannbäume

Neue Frage »

mathisfun Auf diesen Beitrag antworten »
Anzahl der Spannbäume
Meine Frage:
Ich habe folgende Aufgabe und eine Musterlösung dafür. Nun ist mir sie zu kurz zusammengefasst. Wie kommt man auf die Formel für die Anzahl der Spannbäume mit einer bestimmten Kante drin?
Danke!

Meine Ideen:
Satz von Cayley ist klar.l Es ist auch klar, dass es in jedem Baum die Anzahl von Kanten um 1 weniger ist als die Anzahl von seinen Knoten.Nun muss ich bestimmen, in wie vielen Spannbäumen die zu enfernende Kante liegt. Das sieht nach Kombinatorik aus. Ich kann das Kreuzprodukt identifizieren: Anzahl von Kanten in dem Baum, den wir aus dem Graphen Kn kriegen, X Anzahl von allen Spannbäumen des Graphen Kn. Da wir irgendwelche Möglichkeiten doppelt zählen, teilen wir durch n über 2. Liege ich daneben?
Reksilat Auf diesen Beitrag antworten »
RE: Anzahl der Spannbäume
Hallo mathisfun,

Vielleicht fällt es Dir leichter, wenn wir einfach mal diese Mengen Bilden:


Da es Spannbäume gibt und jeder Spannbaum Kanten enthält, hat die Mächtigkeit .
Es ist

Nun ist die Automorphismengruppe des gerade die und diese ist insbesondere transitiv auf den Kanten, d.h. für beliebige Kanten und .
Die Mächtigkeit von ist also gerade die Mächtigkeit von geteilt durch die Anzahl der Kanten im gesamten .

Gruß
Reksilat
mathisfun Auf diesen Beitrag antworten »
RE: Anzahl der Spannbäume
Hallo Reksilat,
danke für die ausführliche Antwort!
Daraus habe ich leider nicht viel verstanden. verwirrt
Also, ich bin so weit, dass ich weiß, dass n über 2 die Anzahl von Kanten im Graphen Kn ist. Ich sehe den Unterschied zwischen der Definitionen für die Mengen M und Me nicht. Ist M die Menge der Spannbäume + die Kante e? Und Me ist dann die Menge mit Spannbäumen, die eine Kante e schon enthalten? Die Menge M kann aber keine Spannbäume enthalten,denn, wenn wir zu einem Spannbaum eine Kante hinzufügen, entsteht doch schon ein Kreis, und dann ist es kein Spannbaum mehr. Sehr verwirrt. unglücklich
Reksilat Auf diesen Beitrag antworten »
RE: Anzahl der Spannbäume
Die Menge besteht aus allen Tupeln (Paaren), wobei der erste Eintrag ein Spannbaum und der zweite eine Kante dieses Stammbaums ist.
Für halten wir eine Kante fest und betrachten nur die Tupel aus , in denen die zweite Komponente gerade ist.

Ich versuch's jetzt aber mal anders: Sei die Anzahl der Spannbäume, in denen Kante enthalten ist. Es gibt insgesamt Kanten und auch jede andere Kante ist genau in x Spannbäumen. Summieren wir also die Spannbäume für alle Kanten auf, erhalten wir Spannbäume.
Dabei haben wir jeden Spannbaum so oft mitgezählt, wie Kanten in ihm enthalten sind.
Die Gesamtzahl aller Spannbäume ist also .

Wie erwähnt ist die Gesamtzahl aller Spannbäume aber auch und somit folgt:
mathisfun Auf diesen Beitrag antworten »

Jetzt habe ich das verstanden. Freude Vielen Dank!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »