Brauche einen Hinweis! Kargers Algorithmus gegen Kruskal, Spanning Tree Distribution

Sei G = (V, E) ein Einheitskapazitätsgraph mit n Eckpunkten und m Kanten.

T bezeichne alle überspannenden Bäume in G.

Wenn wir den Karger-Algorithmus ausführen, erhalten wir einen zufälligen Spannbaum in T, der durch die kontrahierten Kanten gebildet wird. Wir bezeichnen diese Verteilung der Spannbäume mit D1.

Wenn wir andererseits jeder Kante ein zufälliges Gewicht in (0,1) zuweisen und einen minimalen Spannbaum unter Verwendung des Kruskal-Algorithmus berechnen, wird eine andere Verteilung D2 über T erhalten.

Zeigen Sie, dass die Verteilungen D1 und D2 identisch sind.

Ich habe keine Ahnung, wo ich anfangen soll. Jeder Hinweis ist hilfreich!

Sie sollten zeigen, dass beide Algorithmen bei jedem Schritt eine Kante mit derselben Wahrscheinlichkeitsverteilung auswählen. Zum Beispiel ist die erste Kante, die durch Kargers Algorithmus kontrahiert wird, eine gleichmäßig zufällige Kante. Wenn Sie die Gewichte zufällig auswählen, ist die erste Kante, die im Kruskal-Algorithmus ausgewählt wird, eine gleichmäßig zufällige Kante.

Was ist mit der nächsten Kante? Kargers Algorithmus wählt eine andere gleichmäßig zufällige Kante aus. Nach dem Entfernen der ersten Kante werden die verbleibenden Kanten vollständig zufällig angeordnet. Daher ist auch die nächste vom Kruskal-Algorithmus gewählte Kante gleichmäßig zufällig.

Ab der dritten Kante wären daher einige Kantenauswahlmöglichkeiten schlecht - schließen einen Zyklus. Konstruktionsbedingt geschieht dies jedoch nicht in beiden Algorithmen, und ansonsten ist die gewählte Kante gleichmäßig zufällig.

Dies ist die Idee des Beweises, und es bleibt, ihn formal zu machen. Das ist deine Aufgabe.