| Die letzten 10 Beiträge |
| Shizmo |
Okay, vielen Dank 
|
| eulerscheZahl |
Also nochmal:
Wir versuchen, bei einem Kreis die Kante mit dem größten Gewicht in den Spannbaum zu bekommen.
Dazu muss es einen Schnitt geben, der diese eine Kante enthält, aber keine andere Kante des Kreises (die ja ein kleineres Gewicht hat).
Um keine Kante mit kleinerem Gewicht zu erwischen, müssen alle Knoten des Kreises in C (oder dessen Komplement) sein.
Daraus folgt dann aber auch, dass die Kante, die wir eigentlich hinzufügen wollen um den Kreis zu schließen, nicht über den Schnitt geht. Man kann also keinen Kreis bilden. |
| Shizmo |
| Zitat: |
Original von eulerscheZahl
[...]
Das heißt aber, dass alle Knoten im Kreis in C liegen (oder in dessen Komplement).[...] |
Hier komm ich leider nicht ganz mit, warum? |
| eulerscheZahl |
Es gibt noch die Möglichkeit, nur den neuen Knoten in C zu nehmen, wodurch Kante 5 Teil des Spannbaums wird. Kante 4 wirst du da nicht mehr reinbekommen. |
| Shizmo |
| Zitat: |
Original von eulerscheZahl
[...] Die größte Kante des Kreises würde dann aber nicht über den Schnitt gehen. |
Ah ich glaub ich versteh schon, ich habe es so gemeint (Bild 1), aber das kann ja nicht sein oder? Weil der nördlichste und südlichste Knoten bereits eine Zusammenhangskomponente sind, richtig?? Also gibt es nur noch dieses Szenario (Bild 2).?
Shizmo hat diese Bilder (verkleinerte Versionen) angehängt:
 
|
| eulerscheZahl |
Kannst du mir das mal aufmalen (einschließlich dem Schnitt, durch den Kante 4 leichteste Kante wird)? |
| Shizmo |
Aber angenommen es gibt bei deinem Beispielgraphen noch einen Knoten 5 der rechts in der Mitte ist und eine (gestrichelte) Kante nach 1 hat mit Gewicht 5. Dann wäre beim Schnitt ja 4 die leichteste Kante und es bildet sich ein Kreis. 
|
| eulerscheZahl |
Hm, da habe ich was übersehen.
Angenommen, wir haben eine Kante, die den Kreis schließen würde (vgl. Bild). Die Kanten innerhalb des Kreises müssten alle unterschiedliches Gewicht haben (eindeutige leichteste Kante). Die Kante mit dem größten Gewicht kann nur dann Teil des minimalen Spannbaums sein, wenn alle anderen für den entsprechenden Schnitt nicht die leichteste Kante sein. Das heißt aber, dass alle Knoten im Kreis in C liegen (oder in dessen Komplement). Die größte Kante des Kreises würde dann aber nicht über den Schnitt gehen. Es gibt also keinen Schnitt, der die Kante wählt.
| Zitat: |
| Wenn ich das (vermutlich |V|-1 mal) gemacht habe bin ich auch schon fertig oder? |
ja.
eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:
|
| Shizmo |
Danke für deine Antwort!!
Ich versteh nicht ganz wie du Kreise ausschließt, es gibt zwar immer nur eine eindeutige leichte Kante, aber die könnte beim Schnitt ja auch so liegen, dass sich ein Kreis bildet.?
Wenn das jetzt geklärt wäre, dann:
| Zitat: |
| [...] nimm zwei nicht verbundene Teile und finde die leichteste Kante. |
Wenn ich das (vermutlich |V|-1 mal) gemacht habe bin ich auch schon fertig oder? |
| eulerscheZahl |
Nehmen wir an, dass alle diese leichten Kanten im minimalen Spannbaum enthalten sind.
Wir müssen zeigen: der Graph ist zusammenhängend und es gibt keine Kreise.
Kreise können wir ausschließen: ein Schnitt kann immer so durch den Kreis gelegt werden, dass er zwei Kanten schneidet. Es kann aber nur eine leichteste Kante geben.
Aber weil es für jeden Schnitt nicht nur maximal, sondern auch minimal eine Kante gibt, muss der Graph zusammenhängend sein: stelle dir einfach vor, du hättest zwei nicht verbundene Teile. Mache einen Schnitt zwischen diesen, dann musst du eine Kante wählen und schon sind die Teile verbunden.
Damit hätten wir dann auch schon eine Konstruktionsvorschrift: nimm zwei nicht verbundene Teile und finde die leichteste Kante. |
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
