Breitester Pfadalgorithmus Korrektheitsbeweis

Question

Wie beweisen Sie, dass der maximale Spannbaum eines ungerichteten Graphen den Pfad enthält, der der breiteste Pfad zwischen zwei beliebigen Scheitelpunkten A und B in der Grafik ist?

Ich habe versucht, über den Beweis für Kruskal-Algorithmus mit einer Bearbeitung nachzudenken, so dass es den maximalen Spannbaum erzeugt, aber ich sehe nicht, warum der maximale Spannbaum die Kanten im breitesten Pfad enthalten muss, besonders wenn es mehrere breiteste Pfade gibt.

Answer 1

Beweise für Optimalität sind oft widersprüchlich. Hier werden Sie selbst einrichten, einen zu finden, indem er sagte

dort Angenommen, sind die Eckpunkte A und B mit einem breiten Weg zwischen ihnen zumindest eine Kante nicht in jeder MST-Heuristik des Graphen enthält.

Nun müssen Sie zeigen, dass die Existenz einer solchen Kante zum gewünschten Widerspruch führt. Ein klarer Pfad wäre, zu zeigen, dass diese Kante verwendet werden kann, um einen neuen aufspannenden Baum von Gewicht zu konstruieren, der größer ist als irgendeines der maximalen Spannbäume des Graphen. Daher waren sie doch nicht maximal.

Die Existenz eines Widerspruchs zeigt, dass der hypothetisch breiteste Weg von A nach B nicht existiert. Daher liegt der Beweis vor.