Algorithmus von Kruskal erzeugt immer einen spannenden Baum |
| 30.01.2016, 16:46 | binabum | Auf diesen Beitrag antworten » |
| Algorithmus von Kruskal erzeugt immer einen spannenden Baum Hi, ich habe eine Frage zu der Aufgabe: Beweisen Sie, dass der Algorithmus von Kruskal immer einen spannenden Baum mit minimalem Gewicht erzeugt. Zeigen Sie hierzu, dass der Algorithmus von Kruskal nur ein Spezialfall des allgemeinen Greedy- Algorithmus über Matroide ist. ich bin mir nicht sicher,ob es richtog ist oder ob ich die frage falsch verstanden habe Meine Ideen: gzz. Wälder und Matroide leerer graph ist kreisfrei teilgraph von kleinsten graph ist wieder kreisfrei --> teilgraph element von U seien G1,G2 kreisfreie graphen und G2 hat eine kante mehr als G1 Behauptung: G1 vereinigt {e} kreisfrei, wobei e Element von E (G2) Zwischenbehauptung: n-m zusammenhängende komponente im graph n=# Knoten,m=#Kanen =>da G2 einer kante ,ehr,muss nach zwischenbehauptung eine zusammenhängende komponente weniger haben auswahl eines repräsentanten(knoten) aus jedeer zusammenhangs komponente von dem größten graphen G1 betrachte repräsentanten in graph G2 )beide graphen gleiche Knoten) => schubfachprinzip: k representanten, da k zusammenhängender komponent in graph G1 und graph G2 hat nun k-1 zusammenhangs komponenten daraus folgt : (umgedreht E) zwei knoten die in in einem zusammenhangs komponent in graph G2 => (gedachter) {x,y} -Pfad in G1 --> gehe entlang Pfaden {x,y} in G1 von x aus sonlange bis man zusammenhängenden komponent (um x) verlässt |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
