Anzahl Spannbäume

02.09.2014, 12:16	Rogerzz	Auf diesen Beitrag antworten »
Anzahl Spannbäume Meine Frage: Sei H der Graph mit $\begin{eqnarray} V(H)=[50] \end{eqnarray}$ , wobei für $\begin{eqnarray} u,v \in V(H), u \neq v \end{eqnarray}$ genau dann $\begin{eqnarray} \left\{ u,v \right\} \in E(H) \end{eqnarray}$ gilt, wenn u+v gerade ist. Man erhalte H' aus H durch Hinzunahme der Kante {11,50}. Machen Sie eine begründete Aussage, ob H' mehr als $\begin{eqnarray} 11^{50} \end{eqnarray}$ Spannbäume hat. Meine Ideen: Leider weiß ich nicht, wie ich vorzugehen hab, wäre super, wenn mir jemand einen Tipp dazu geben könnte.
02.09.2014, 13:05	wdposchmann	Auf diesen Beitrag antworten »
Hallo, naja Du kannst ja doch erstmal herausfinden, wie viele Kanten der Graph $\begin{eqnarray} H \end{eqnarray}$ hat. Nehm Dir dazu den ersten Knoten und überleg Dir, welche Kanten von diesem ausgehend in der Menge $\begin{eqnarray} E(H) \end{eqnarray}$ sind. Die ersten sind $\begin{eqnarray} \left\{ 1,3 \right\}, \left\{ 1,5 \right\}, \ldots \end{eqnarray}$ . Wie geht es dann weiter (auch für die weiteren Knoten und nicht nur den ersten)? Welche Vorgehensweisen kennst Du dann, um herauszufinden, wie viele Spannbäume ein Graph hat?
02.09.2014, 13:29	Rogerzz	Auf diesen Beitrag antworten »
Naja also von jedem Knoten gehen 24 Kanten aus, bis auf Knoten 11 und 50, diese haben den Grad 25. Insgesamt haben wir also 601 Kanten. Wir hatten eigentlich immer mit der Vorgehensweise über die Kirchhoff Matrix die Anzahl der Spannbäume herausgefunden aber dies ist ja nun schon recht schwierig, deswegen weiß ich nicht genau wie ich das machen soll.
02.09.2014, 14:08	wdposchmann	Auf diesen Beitrag antworten »
Genau. Ich kenne rechnerisch auch nur die Kirchhoff-Methode (die hier bei einer 50x50-Matrix händisch sicher nicht sehr schön ist). Betrachte erst mal nur den Graphen $\begin{eqnarray} H \end{eqnarray}$ ohne die zusätzliche Kante und überlege Dir, wie dieser aussehen würde, wenn z.B. $\begin{eqnarray} V(H) = 6 \end{eqnarray}$ , also wenn er nur wenige Knoten hätte (evtl. auch mal zeichnen). Da wirst Du eine gewisse Struktur erkennen, die Dir dann bei Deiner Argumentation behilflich sein kann.
02.09.2014, 14:49	Rogerzz	Auf diesen Beitrag antworten »
Also der Graph H hat ja sozusagen zwei Klassen, in denen nur Kanten innerhalb der Klassen verlaufen. Des Weiteren sind die beiden Klassen des Graphen H für sich vollständig, das heißt die Anzahl der Spannbäume einer Klasse von H wäre $\begin{eqnarray} n^{n-2}=25^23 \end{eqnarray}$ . Könnte man dann folgern, dass der Graph H' $\begin{eqnarray} 2(25^23) \end{eqnarray*}$ Spannbäume hat?
02.09.2014, 15:01	wdposchmann	Auf diesen Beitrag antworten »
Fast. Wie Du schon richtig sagst, hat jede dieser Klassen $\begin{eqnarray} 25^{23} \end{eqnarray}$ Spannbäume. Wenn Du jetzt die "Brücke" zwischen Knoten 11 und 50 hinzufügst, verbindest Du diese Klassen. Jetzt kannst Du jeden Spannbaum der einen Klasse mit jedem Spannbaum der anderen Klasse kombinieren. Du bekommst also $\begin{eqnarray} (25^{23})^2 = 25^{46} > 11^{50} \end{eqnarray}$ Spannbäume.
Anzeige

02.09.2014, 15:14	Rogerzz	Auf diesen Beitrag antworten »
Ah stimmt, eigentlich ja gar nicht so schwer gewesen. Vielen Dank für deine Hilfe!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »