Gib alle möglichen Spannbäume des Graphen an.

Question

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 5³=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?

Answer 1

Der Graph hat genau drei Kreise: 12531, 24352, 12431

Egal welche Kante du entfernst, zwei der Kreise gehen kaputt. Das sind 6 Möglichkeiten.

Aus dem verbleibenden Kreis entfernst du eine weitere Kante. Das sind 4 Möglichkeiten.

Macht in dieser Reihenfolge 24 Möglichkeiten. Dem Spannbaum ist es aber egal, in welcher Reihenfolge er aus dem Graphen erzeugt wurde. Es bleiben 12 Spannbäume übrig.

Comments

Jetzt ist alles klar danke:)