 Spannbaum |
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
 |
|
Hallo 
| Zitat: |
| Gegeben ist ein ungerichteter gewichteter Graph G=(V,E). Zeigen Sie, dass G einen eindeutigen minimalen Spannbaum besitzt, wenn für jeden Schnitt (C,V-C) von G eine eindeutige leichte Kante existiert die (C,V-C) kreuzt. |
Ich nehme gerne Vorschläge entgegen 
LG
|
|
31.05.2016 23:52 |
|
|
|
|
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.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
01.06.2016 08:28 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
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?
|
|
|
01.06.2016 09:18 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
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:39 |
|
|
|
|
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.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
01.06.2016 09:57 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
| 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?
|
|
|
01.06.2016 16:50 |
|
|
|
|
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.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
01.06.2016 16:57 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
Okay, vielen Dank 
|
|
|
01.06.2016 18:27 |
|
|
|
