Satz von Kirchhoff - spannende Bäume und Wälder

26.09.2019, 17:02	Studentu	Auf diesen Beitrag antworten »
Satz von Kirchhoff - spannende Bäume und Wälder Hallo Community, gegeben folgende Problemstellungen: a) Betrachte die vollständigen, bipartiten Graphen $\begin{eqnarray} K_{2,n} \end{eqnarray}$ . Berechne die Anzal der $\begin{eqnarray} T_n \end{eqnarray}$ der spannenden Bäume von $\begin{eqnarray} K_{2,n} \end{eqnarray}$ für $\begin{eqnarray} n \in \{1,2\} \end{eqnarray}$ . Beweise zudem allgemein die Rekursion $\begin{eqnarray} T_n = n \cdot 2^{n-1} \end{eqnarray}$ . b) Berechne die Anzahl der spannenden Wälder vom Graph <V(G), E(G)>, wobei $\begin{eqnarray} V(G):=\{1,2,3,4,5,6,7\} \end{eqnarray}$ und $\begin{eqnarray} E(G):=\{(1,2),(2,3),(3,1)\}\cup\{(4,5), (5,6), (6,7), (7,4), (5,7)\} \end{eqnarray}$ . Der Satz von Kirchhoff besagt: Sei G ein schlichter ungerichteter zusammenhängender Graph mit Knotenmenge V(G) = $\begin{eqnarray} \{v_1, \dotsc, v_n\} \end{eqnarray}$ und Adjazenzmatrix A(G). Weiters bezeichne D(G) die Diagonalmatrix der Knotengrade diag( $\begin{eqnarray} d(v_1), \dotsc, d(v_n) \end{eqnarray}$ ), so ist jeder Kofaktor der Matrix D(G) - A(G) die Anzahl der spannenden Bäume von G. Zu den Definitionen: Ein spannender Baum T eines schlichten ungerichteten zusammenhängenden Graphen G ist ein Baum mit V(T) = V(G) und $\begin{eqnarray} E(T) \subseteq E(G) \end{eqnarray}$ . Was das bedeutet, ist mir klar. Ein spannender Wald W eines schlichten ungerichteten Graphen G ist ein Wald mit V(W) = V(G) und $\begin{eqnarray} E(W) \subseteq E(G) \end{eqnarray}$ und denselben Zusammenhangskomponenten wie G. Das verstehe ich nicht ganz. Was ist überhaupt ein Wald? Soweit ich mich erinnern kann, ein Graph bestehend aus mehreren Bäumen oder? Zu a): Für $\begin{eqnarray} K_{2,1} \end{eqnarray}$ erhalte ich als Anzahl 1. Für $\begin{eqnarray} K_{2,2} \end{eqnarray}$ lautet meine Adjazenzmatrix $\begin{eqnarray} \begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\1 & 1 & 0 & 0 \end{pmatrix} \end{eqnarray}$ und D(G) = diag(2,2,2,2). Somit erhalte ich als Kofaktor aber -4, was ja offensichtlich falsch sein muss. Oder darf ich den Betrag davon nehmen und die Lösung ist 4? (4 habe ich auch durch Aufzeichnen erhalten.) Das allgemeine BEWEISEN DER ANGEGEBENEN REKURSION verstehe ich leider nicht. Ich kann bisher kein Rekursionsmuster erkennen, aus dem ich diese Rekursion herleiten könnte. Zu b): Hilft hier auch der Satz von Kirchhoff? Muss ich separat für die beiden Zusammenhangskomponenten jeweils die Anzahl an spannenden Bäumen bestimmen und die beiden Anzahlen dann miteinander multiplizieren, um die Anzahl aller spannenden Wälder zu bekommen?
27.09.2019, 16:31	Studentu	Auf diesen Beitrag antworten »
Hallo allerseits, besonders der Beweis der Rekursion $\begin{eqnarray} T_n = n \cdot 2^{n-1} \end{eqnarray}$ würde mich sehr interessieren, weil man wohl "nur" die richtigen Überlegungen dazu anstellen muss, ohne großes Hintergrundwissen.
30.09.2019, 15:23	Studentu	Auf diesen Beitrag antworten »
Falls doch noch jemand weiß, wie man die Rekursion allgemein zeigt/erklärt/interpretiert, würde ich mich über eine Antwort nach wie vor sehr freuen!
01.10.2019, 14:28	URL	Auf diesen Beitrag antworten »
Also mir ist die Sache mit den spannenden Bäumen offenbar nicht klar. Betrachten wir mal den Fall n=2. Spannende Bäume sind dann nach meinem Verständnis alle mit drei oder vier Kanten. Davon gibt es fünf Stück, während die Rekursion vier liefert Die Rekursion könnte man folgendermaßen begründen: Damit sich ein Baum ergibt, müssen die beiden Knoten der einen Partition über einen Knoten der anderen Partition verbunden werden. Für die Auswahl dieses Ping-Pong-Knotens hat man n Möglichkeiten. Für die übrigen n-1 Knoten kann man dann jeweils entscheiden, zu welchem der beiden Knoten der anderen Partition man verbinden will. Auf diese Art bekommt man nach meinem Verständnis aber nur spannende Bäume, die in gewisser Weise minimal sind, d.h. mit der minimalen Anzahl von n+1 Kanten auskommen.
01.10.2019, 15:31	Studentu	Auf diesen Beitrag antworten »
Hallo URL, vielen, vielen Dank für deine Beteiligung und Hilfe!! Ich habe mir bzgl. der Definition und Rekursion dasselbe gedacht wie du und bin mit Google dann zu dem Ergebnis gekommen, dass die Rekursion nur spannende Bäume umfasst, die ungleich dem Gesamtgraphen sind, also eine echte Kantenteilmenge. Mir ist leider nicht ganz klar, wie deine Erklärung mit für die Rekursion zu verstehen ist. Also wir haben am Anfang einfach zwei Knotenmengen, eine mit 2 Knoten und eine mit n Knoten. Nun verbinden wir die zwei Knoten mit einem der n Knoten. Das sind n Möglichkeiten. Und jeden der restlichen (n-1) Knoten müssen wir dann auch noch mit einem der zwei Knoten verbinden, um einen vollständigen Graphen zu erhalten. Darum 2^(n-1). Dann fehlt aber noch die Möglichkeit, dass man mit beiden Knoten verbindet, das hast du wohl auch so festgestellt. Müsste es dafür dann 3^(n-1) heißen? Also ist es eigentlich sicher, dass die Rekursion, so wie sie dasteht, nur minimale Spannbäume umfasst. Aber der Satz von Kirchhoff ist schon auch für die anderen (ausschließlich denen, die gleich der vollständigen Kantenmenge sind) oder?
01.10.2019, 16:31	URL	Auf diesen Beitrag antworten »
Diese Bäume sind nicht nur ungleich dem Gesamtgraphen sondern haben nur n+1 Kanten der möglichen 2n. Du hast meine Erklärung schon richtig verstanden. Ich gehe eben davon aus, dass jeder der n-1 Knoten nur mit genau einem der beiden anderen verbunden wird. Dadurch zeichnet sich der Ping-Pong-Knoten aus, er ist der einzige mit zwei Verbindungen. 3^(n-1) stimmt nicht, wenn man mehrere Verbindungen zulässt, weil man Bäume doppelt zählen würde. Ich weiß weder, was eine Adjazenzmatrix ist noch was Knotengrade sind, kann also zu Kirchhoff nichts sagen
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »