Aufgabe:
Ein Spannbaum ist ein Teilgraph, der ein Bam ist und alle Knoten enthält. Gib alle möglichen Spannbäume des Graphen an. Vergesst, dass der Baum gerichtet ist. (Deshalb habe ich in der Zeichnung die Pfeile weggelassen, sodass die Kanten nicht gerichtet sind.)
Mein Ansatz:
- Satz von Cayley
n^{n-2} = als Formel benutzen, sodass es 53=125 Möglichkeiten gibt.
Problem: Es sind nicht alle Kanten verbunden!
Ich habe die Verbindungen:
{1,2},{1,3},{2,4},{3,4},{3,5},{5,2}
Es fehlen:
{1,5},{1,4},{2,3},{4,5} (Ich hoffe ich habe keine Verbindung vergessen!)
Das heißt doch, ich kann die Formel jetzt nicht benutzen!
Und das ist auch der Punkt, wo ich nicht mehr weiterkomme.
Soll ich jetzt wirklich alle möglichkeiten aufzeichnen und dann die möglichkeiten wegstreichen, wo die fehlenden Kanten auftauchen? Das würde doch viel zu lange dauern oder nicht?
ich weiß, dass die Formel für ungerichtet Graphen funktioniert und sie alle kombinationen angeben, wenn aber alle Kanten existieren, was hier ja nicht der Fall ist.
Kann man dies einfacher lösen?