Kruskal < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:06 So 12.01.2014 | | Autor: | rsprsp |
| Aufgabe | | Beweisen Sie, dass der Algorithmus von Kruskal immer einen spannenden Baum mit minimaler Gewicht erzeugt. Zeigen Sie hierzu, dass der Algorithmus von Kruskal nur ein Spezialfall des allgemeinen Greedy-Algorithmus ueber Matroiden ist. |
Der Algorithmus von Kruskal sammelt zuerst die billigsten Kanten und versucht den Graph kreisfrei zu halten. Dadurch wird ein Baum mit minimalen Gewicht erzeugt.
Reicht das als Beweis ?
Auf das andere komm ich nicht...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:43 So 12.01.2014 | | Autor: | felixf |
Moin!
> Beweisen Sie, dass der Algorithmus von Kruskal immer einen
> spannenden Baum mit minimaler Gewicht erzeugt. Zeigen Sie
> hierzu, dass der Algorithmus von Kruskal nur ein
> Spezialfall des allgemeinen Greedy-Algorithmus ueber
> Matroiden ist.
>
> Der Algorithmus von Kruskal sammelt zuerst die billigsten
> Kanten und versucht den Graph kreisfrei zu halten.
Und, schafft er es auch?
> Dadurch wird ein Baum mit minimalen Gewicht erzeugt.
Wieso ist das Gewicht minimal?
> Reicht das als Beweis ?
Nein, offenbar nicht. Du hast ja nichts bewiesen, sondern nur Zusammenhaenge behauptet, die nicht so einfach sind dass man sie sofort glaubt.
> Auf das andere komm ich nicht...
Weisst du denn, worum es ueberhaupt geht? Also, weisst du was ein Matroid ist, was der allgemeine Greedy-Algorithmus ueber Matroiden ist, und was das ganze mit minimalen Spannbaeumen zu tun haben koennte?
(Tipp: schau dir die Menge aller Untergraphen des Graphen an, die Baeume sind.)
LG Felix
|
|
|
|
