[FRAGE] - Kaiser: wieviele spannende bäume [Archive]

phlow

24-11-2004, 21:57

Frage: Wievele spannende Bäume hat ein gesättigter Graph, wenn man eine Kante entfernt?

Ich hätte gesagt: einen ... aber bin mir total unsicher.

Any Ideas?

seg2

24-11-2004, 22:07

Ich habe das damals in diese Formel gefasst:

n ... Knotenanzahl des vollständigen Graphen
x=(n*(n-1))/2 ... Kantenanzahl des vollständigen Graphen
y=n^(n-2) ... Spannbaumanzahl
z=n-1 ... Kantenanzahl eines Spannbaumes

==> Anzahl = y-yz/x = (y*(x-z))/x

Das ganze baut auf den "Satz von Cayley" auf, der nur beim genauen Hinsehen in Kaisers Skript gefunden wird, und im Wesentlichen aussagt, dass es n^(n-2) Spannbäume gibt.

Kannst ja mal für einfache Fälle wie den K_3 oder K_4 testen (aufzeichnen) - Wird einem dann relativ schnell klar!

baracuda

24-11-2004, 22:24

Ich habe das damals in diese Formel gefasst:

n ... Knotenanzahl des vollständigen Graphen
x=(n*(n-1))/2 ... Kantenanzahl des vollständigen Graphen
y=n^(n-2) ... Spannbaumanzahl
z=n-1 ... Kantenanzahl eines Spannbaumes

==> Anzahl = y-yz/x = (y*(x-z))/x

Das ganze baut auf den "Satz von Cayley" auf, der nur beim genauen Hinsehen in Kaisers Skript gefunden wird, und im Wesentlichen aussagt, dass es n^(n-2) Spannbäume gibt.

Kannst ja mal für einfache Fälle wie den K_3 oder K_4 testen (aufzeichnen) - Wird einem dann relativ schnell klar!
Also ein gesättigter Graph (jetzt von gesättigten Teilgraphen abgesehen) ist das gleich mit einem vollständigen Graphen?

phlow

24-11-2004, 23:28

danke, das hat seh geholfen :-) ich hab die Angabe auch irgendwie falsch interpretiert

VTEC

27-02-2005, 22:16

Also bei K4 kommen nach der obigen Formel 8 raus. Leider weiß ich nicht, worin sich die spannenden Bäume gleichen bzw. unterscheiden sollen. Vielleicht könnte mir das jemand erklären bzw. für K4 aufzeichnen?

Wenn ich z.B. die gleiche Figur immer 90° drehe, so fehlt immer eine andere Kante (wenn die Knoten numeriert sind), da komm ich auf weit über 8. Und wenn ich die Knoten nicht numeriere, dann komme ich nicht auf 8 :confused:

michi204

02-03-2005, 18:03

kann man das nicht mit dem satz von kirchhoff ausrechnen?

lg michi

seimen

09-05-2005, 15:04

also wenn ich es mit dem caylay ausrechne für k=5 komm ich auf 75.

laut diesem thread http://www.informatik-forum.at/archive/index.php/t-18226.html kommt man mit kirchhoff auch auf 75

also anscheinend wurscht wie man rechnet, aber caylay geht schneller