Minimum Spanning Tree

Neue Frage »

sam007 Auf diesen Beitrag antworten »
Minimum Spanning Tree
hallo,
ich sitze gerade an einer aufgabe und finde irgendwie keinen richtigen anfang:

Sei G=(V,E) ein zusammenhängender ungerichteter Graph mit einer Gewichtsfunktion w: E->R+
Alle Kantengewichte sind verschieden und C sei ein Kreis in G.
Zeigen Sie, durch einen indirekten Beweis, dasss die schwerste Kante e in C zu keinem MST von G gehört.

Jemand eine Idee
Abakus Auf diesen Beitrag antworten »
RE: Minimum Spanning Tree
Naja, welche Idee ist naheliegend für einen solchen Spannbaum, wenn die schwerste Kante zu einem Kreis gehört ?

Grüße Abakus smile
sam007 Auf diesen Beitrag antworten »

na man könnte zeigen das der spannbaum keinen kreis hat, somit kann die schwerste kante ach nicht dazu gehören?
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von sam007
na man könnte zeigen das der spannbaum keinen kreis hat, somit kann die schwerste kante ach nicht dazu gehören?


Da fehlt dir noch die Vertrautheit mit den Begriffen: Bäume haben keine Kreise, insbesondere also auch Spannbäume.

Um zu einer Idee zu kommen, solltest du zunächst einen Blick auf die Definition von Spannbäumen und dann auf den recht intuitiven Algorithmus von Kruskal werfen und diesen versuchen an einem Beispiel anzuwenden.

So werden also minimale Spannbäume bzw. Minimalgerüste (ich spreche eher von letzterem) erzeugt.

Dann kannst du mit dem indirekten Beweis anfangen: angenommen, du hättest einen minimalen Spannbaum, welcher die schwerste Kante enthält. Ferner führe ein Kreis durch die schwerste Kante. Gesucht ist ein Widerspruch.

Jetzt kannst du versuchen, einen anderen Spannbaum mit geringerem Gewicht zu konstruieren. Wenn du den hast, wäre das ein Widerspruch zur Voraussetzung.

Grüße Abakus smile
sam007 Auf diesen Beitrag antworten »

Also nach dem algorithmus von Kruskal werden ja alles kanten nicht mehr betrachtet die einen kreis bilden könnten, wenn man sie auswählt.

Wenn e die schwerste kante ist und alle anderen kannten verschieden und somit geringer gewichtet sind als alle anderen, wird diese Kante e nach diesem Algorithmus quasi zum schluss betrachtet (wenn sie vorher nicht zur kreisbildung benützt werden könnte).
Und wenn das so ist dann wurden alle anderen Kanten von C (da sie geringer gewichtet sind) schon betrachtet. Sollten diese alle schon markiert worden sein, wird e auf keinen Fall mehr markiert, da sich ja sonst der Kreis C im Spannbaum bilden würde.
Also kann e nicht zum spannbaum gehören.

Ist das nicht auch ein beweis?
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von sam007
Und wenn das so ist dann wurden alle anderen Kanten von C (da sie geringer gewichtet sind) schon betrachtet. Sollten diese alle schon markiert worden sein, wird e auf keinen Fall mehr markiert, da sich ja sonst der Kreis C im Spannbaum bilden würde.
Also kann e nicht zum spannbaum gehören.


Das funktioniert nur, wenn alle anderen Kanten des Kreises für das Gerüst ausgewählt wurden. Das dürfte i.A. jedoch nicht der Fall sein (denn diese könnten einerseits noch andere Kreise bilden und andererseits müssen ja nicht alle Kreiskanten außer der schwersten zu jedem beliebigen Minimalgerüst gehören).

Grüße Abakus smile
 
 
sam007 Auf diesen Beitrag antworten »

ok,
also ich hab das ganze mal an nem beispiel gemacht (reicht nicht aus für ein Beweis, weil ja nicht allgemein oder?).

Ich hab wie du gesagt hast einen Graph genommen, und einen minimalen spannbaum erzeugt, nach Kruskal, allerdings nich ganz exakt nach diesem algorithmus, da ja sonst die schwerste kannte nicht dabei wäre..
Jeden falls hab ich das gleiche noch einmal streng nach dem algo von Kruskal gemacht und gemerkt es gibt einen kleineren Spannbaum, was ja dann die annahme widerlegt, das e im spannbaum enthalten ist..
So das ist aber nur für ein Beispiel, ich weiss aber nicht wie man das allgemein aufschreiben soll.
Tobias Auf diesen Beitrag antworten »

Mein Ansatz wäre Folgender:

Sei k die Kante mit dem höchsten Gewicht im Kreis.

Entferne diese Kante aus dem Graphen G. Da k auf einem Kreis liegt, bleibt der Graph G-k zusammenhängend, d.h. er hat auch einen minimalen Spannbaum.

Jeder Spannbaum von G hat nun aber genau n-1 Kanten, der Spannbaum von G-x hat ebenfalls n-1 Kanten. Damit sollte das Argument deutlich werden.
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von Tobias
Sei k die Kante mit dem höchsten Gewicht im Kreis.

Entferne diese Kante aus dem Graphen G. Da k auf einem Kreis liegt, bleibt der Graph G-k zusammenhängend, d.h. er hat auch einen minimalen Spannbaum.

Jeder Spannbaum von G hat nun aber genau n-1 Kanten, der Spannbaum von G-x hat ebenfalls n-1 Kanten. Damit sollte das Argument deutlich werden.


Das Argument bzw. den gesuchten Widerspruch sehe ich da noch nicht (der Spannbaum von G-k kann ja völlig andere Kanten haben). Die Idee, aus dem gegebenen minimalen Spannbaum die schwerste Kante k des Kreises zu entfernen, ist aber gut.

Du musst jetzt nur noch eine Kante finden, die du wieder zu den "Spannbaum-Resten" hinzufügen und mit der du die Spannbaum-Eigenschaft wieder herstellen kannst. Diese muss auf dem Kreis liegen (denn alle Kanten des Kreises können nicht zum Spannbaum gehört haben). Dass du so einen Spannbaum kriegst, wäre natürlich zu begründen.

Der neue Spannbaum hat dann ein echt kleineres Gewicht als der angeblich minimale (denn die neue Kante ist leichter als die herausgenommene). Da wäre der Widerspruch.

Grüße Abakus smile
Tobias Auf diesen Beitrag antworten »

Ok, tatsächlich, der Schnellschuss ging in die Hose. Aber ich wage einen zweiten Versuch:

Sei der Kreis der Länge t ( ) und die Kante mit dem größten Gewicht auf diesem Kreis.

Angenommen es gäbe einen minimalen Spannbaum T mit der Kante k. Dann zerfällt T-k in zwei eckendisjunkte Teilbäume mit den Eckenmengen V_1 und V_2.

Sei o.B.d.A. .

Gäbe es eine Kante mit , dann vereinigt diese Kante die beiden Teilbäume wieder zu einem Spannbaum, der dann aber geringer ist (Widerspruch).

Das führt zu der Argumentationskette .
Widerspruch, denn .
Abakus Auf diesen Beitrag antworten »

Ist folgerichtig, denke ich Freude

Grüße Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »