Minimaler Spannbaum: Was genau ist die Cut-Eigenschaft?

Question

Ich habe viel Zeit damit verbracht, Online-Präsentationen und Lehrbücher über die Cut-Eigenschaft eines minimalen Spannbaums zu lesen. Ich verstehe nicht wirklich, was es zu illustrieren oder sogar warum es praktisch ist. Angeblich hilft es zu bestimmen, welche Kanten zu einer MST hinzuzufügen, aber ich sehe nicht, wie es das erreicht. Mein Verständnis der Cut-Eigenschaft ist, dass Sie eine MST in zwei beliebige Teilmengen aufteilen. Irgendwelche Hilfe hier? Vielen Dank!

Answer 1

Ein Schnitt eines verbundenen Graphen ist ein minimaler Satz von Kanten, deren Entfernung den Graphen in zwei Komponenten (Teile) trennt. Die minimale Schnitteigenschaft besagt, dass, wenn eine der Kanten des Schnitts ein Gewicht aufweist, das kleiner ist als jede andere Kante im Schnitt, es sich in der MST befindet. Nehmen wir an, dass es eine MST gibt, die die Kante nicht enthält. Wenn wir die Kante der MST hinzufügen, erhalten wir einen Zyklus, der den Schnitt mindestens zweimal kreuzt, so dass wir den Zyklus unterbrechen können, indem wir die andere Kante aus der MST entfernen, wodurch ein neuer Baum mit geringerem Gewicht entsteht, was der Minimalität der MST.