Spannbaum |
| 31.05.2016, 23:52 | Auf diesen Beitrag antworten » | ||
| Shizmo | Spannbaum Hallo 
Ich nehme gerne Vorschläge entgegen 
LG |
||
|
|
|||
| 01.06.2016, 08:28 | Auf diesen Beitrag antworten » | ||
| 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. |
||
| 01.06.2016, 09:18 | Auf diesen Beitrag antworten » | ||
| 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:
Wenn ich das (vermutlich |V|-1 mal) gemacht habe bin ich auch schon fertig oder? |
||
| 01.06.2016, 09:31 | Auf diesen Beitrag antworten » | ||
| 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.
ja. |
||
| Anzeige | |||
|
|
|||
| 01.06.2016, 09:39 | Auf diesen Beitrag antworten » | ||
| 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. 
|
||
| 01.06.2016, 09:42 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | Kannst du mir das mal aufmalen (einschließlich dem Schnitt, durch den Kante 4 leichteste Kante wird)? |
||
| 01.06.2016, 09:54 | Auf diesen Beitrag antworten » | ||
| Shizmo |
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).? |
||
| 01.06.2016, 09:57 | Auf diesen Beitrag antworten » | ||
| 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. |
||
| 01.06.2016, 16:50 | Auf diesen Beitrag antworten » | ||
| Shizmo |
Hier komm ich leider nicht ganz mit, warum? |
||
| 01.06.2016, 16:57 | Auf diesen Beitrag antworten » | ||
| 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. |
||
| 01.06.2016, 18:27 | Auf diesen Beitrag antworten » | ||
| Shizmo | Okay, vielen Dank 
|
||
|
|