G=(V,E) zsm.hgd. Graph mit inj. Kostenfunktion cost:E->N. Zeige: G bes. genau einen MST |
| 08.06.2020, 18:45 | Ergydion | Auf diesen Beitrag antworten » |
| G=(V,E) zsm.hgd. Graph mit inj. Kostenfunktion cost:E->N. Zeige: G bes. genau einen MST Grüßt euch, ich sitze an folgendem Problem: Gegeben ist ein zusammenhängender Graph G=(V,E) mit einer injektiven Kostenfunktion cost: E -> N. Nun gilt es zu zeigen, dass G genau einen minimal aufspannenden Baum hat. Meine Ideen: Also wir wollen ja zeigen, dass G nur genau einen minimal aufspannenden Baum hat. Sei B unser minimal aufspannender Baum, dann gibt es kein B' /= B mit cost(B) = cost(B'). Mein Ansatz wäre vielleicht mit Widerspruch zu zeigen, dass es eben doch nur diesen einen Baum B geben kann. Also würde ich erstmal annehmen, dass es doch einen minimal aufspannenden Baum B' gibt, der allerdings ungleich B ist. Hier weiß ich allerdings nicht weiter und wäre über Hilfe sehr dankbar. Intuitiv habe ich denke ich verstanden, dass es nur einen Baum B geben kann, aber wie genau ich das beweise weiß ich leider nicht. Vielen Dank schon mal für eure Hilfe |
||
| 08.06.2020, 19:05 | Ergydion | Auf diesen Beitrag antworten » |
Ich habe eine passende Lösung zu der Frage gefunden: https://math.stackexchange.com/questions...e-different-cos |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
