Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Alle möglichen Spannbäume eines Graphen

Alle möglichen Spannbäume eines Graphen

Universität / Fachhochschule

Graphentheorie

Tags: Baum, Cayley, Diskrete Mathematik, Graphentheorie, Kanten, Knoten, möglichkeit

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
MomoMimi

MomoMimi aktiv_icon

17:37 Uhr, 22.11.2015

Antworten
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
⇒nn-2 als Formel benutzen, sodass es 55-2=125 Möglichkeiten gibt.

Problem: Es sind nicht alle Kanten verbunden!
Ich habe die Verbindungen:
{1,2},{1,3},{2,4},{3,4},{2,5},{5,2}
Es fehlen:
{1,5},{1,4},{2,3} (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?
Kann man dies einfacher lösen? Bin für jede Hilfe dankbar!

Unbenannt

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)
Online-Nachhilfe in Mathematik
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.