Wenn wir einen Graphen G = (V, E) und eine Teilmenge F mit nur V darin haben, fügen Sie für jede verbundene Komponente S von F die Mindestgewichtskante im Schnitt hinzu (S, V \ S) bis F.Azyklisch über Schnitte in einem Diagramm
Warum wird jedes Mal, wenn die Mindestgewichtskante zu F addiert wird, F weiterhin azyklisch?
Um einen Zyklus zu erstellen, müssen Sie eine Kante erstellen, die Scheitelpunkte verbindet, die bereits verbunden sind.
Wenn Sie eine Kante zwischen Scheitelpunkten hinzufügen, die nicht verbunden sind, erstellen Sie keinen neuen Zyklus. Sie verbinden zwei nicht verbundene Komponenten. Die Grafik bleibt jedoch azyklisch.
Um besser zu verstehen, wie es funktioniert, könnten Sie die verbundene Komponente des Graphen als einzelnen Vertex darstellen. Und wenn Sie die Kante zwischen nicht verbundenen Komponenten hinzufügen, werden Ihre Scheitelpunkte einfach zusammengeführt.
Diese Frage bezieht sich übrigens nicht auf Gewichte (und MST-Algorithmus). Es ist immer noch gültig ohne Gewichte.