Kruskal Beweis Minimalität < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | In einem zusammenhängenden gewichteten Graphen G konstruiert der Kruskal-Algorithmus einen minimalen spannenden Baum (MST). |
Hallo,
das ist zwar keine Aufgabe aber der Satz um den es geht. Ich habe den Beweis dazu vollständig vor mir aber der ergibt für mich schon relativ am Anfang keinen Sinn. Vielleicht kann mir jemand helfen...
Teil 1: Z.z. MST ist ein Baum. <- Wie man das beweist ist mir klar.
Teil 2. Z.z. ist die Minimalität dieses Baums.
Und hier ist mein Problem. der Beweis beginnt da wie folgt:
Sei T Ergebnis des Algorithmus und T* minimal spannender Baum. Gilt T = T* -> fertig. Gilt T [mm] \not= [/mm] T*, dann sei e die erste (kleinste) Kante mit e [mm] \in [/mm] T und e [mm] \not\in [/mm] T*. T* [mm] \cup [/mm] {e} -> Kreis C.
-> Bitte was? Wie soll ich denn einfache die kleinste Kante aus T in irgendeinen beliebigen mini. sp. Baum T* eintragen? Man kann doch da nicht einfach nach belieben irgendwo eine Kante hinzufügen!? Oder doch? Und wenn ja wo? Da fehlt mir die Phanatsie muss ich ehrlich sagen....
Mag mich jemand erleuchten?^^
lg
Kalia
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:03 Mo 16.06.2014 | | Autor: | wauwau |
ein minimal spannender Baum ist eine Baum (enthält also keine Kreise) der aber alle Knoten des Graphen enthält und je zwei dieser sind mit einem Weg verbunden!
Fügst du also irgendeine noch nicht im Baum enthaltene Kante diesem Baum hinzu, dann verbindest Du also zwei Knoten, die aber schon über einen anderen Weg des Baumes miteinander verbunden sind. Daher entsteht damit ein Kreis!
|
|
|
| |
|
Ja, dass ist mir klar aber meine Frage ist eher, ob ich als T* jetzt irgendeinen beliebigen minimal spannenden Baum nehmen kann?
Danke aber trotzdem schonmal. :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:02 Di 17.06.2014 | | Autor: | wauwau |
Ja kannst du, denn die Idee des Beweises ist ja, dass du Kanten aus T zu [mm] $T^{*}$ [/mm] hinzufügen kannst und aus diesem dann eine Kante mit [mm] $\le$ [/mm] Gewicht entfernen kannst ohne die Minimalität zu verändern.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:23 Di 17.06.2014 | | Autor: | WhiteKalia |
Ah ok, danke dir!! :D
|
|
|
|
