Beweis, dass kein minimum spanning tree enthält die maximal gewichtete Kante
Sagen wir mal es gibt Graphen G, so dass es alle seine Kanten haben GEWICHTE, entsprechen verschiedene zahlen. Also keine zwei edge hat das gleiche Gewicht.
Lassen Sie E werden alle Kanten von G. Lassen emax eine Kante E mit maximalem Gewicht.
Eine weitere Eigenschaft des Graphen G ist, dass jede Kante e gehört zu einigen Zyklus in G.
Ich muss beweisen, dass kein minimaler Spannbaum von G enthält die Kante emax.
Ich kann sehen, warum dies so ist, da alle Kanten sind Verschieden und jede Kante gehört zu einem Zyklus, die minimum-spanning-tree-Algorithmus-wählen Sie einfach die Kante mit geringerem Gewicht in den Kreislauf, enthält emax.
Aber ich bin mir nicht sicher, wie Sie Sie konkret zu beweisen.
- en.wikipedia.org/wiki/Minimum_spanning_tree#Cycle_property
- Diese Art der Argumentation ist ziemlich nützlich für den Beweis der Optimalität Eigenschaften Allgemeine Strukturen genannt, die cut und paste-argument. Lesen Sie mehr in CLRS darüber.
- Danke an alle, es ist einfach jetzt, dass ich dies wissen
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dies ist im Zusammenhang mit die Cycle-Eigenschaft des Minimum Spanning Tree, die im Grunde sagen, dass Sie in einem gegebenen Zyklus in einem graph die Kante mit dem größten Gewicht gehört nicht in die MST (leicht bewiesen durch Widerspruch in dem link oben). So da die Kante
emaxgehört zu einem Zyklus es muss nicht werden in der MST.Beweis durch Widerspruch funktioniert hier. Angenommen, Sie haben eine minimum-spanning-tree-einschließlich der maximal edge. Wenn Sie entfernen, die Kante, die Sie haben zwei Komponenten, die nicht mehr mit einander. Jeder Knoten ist in einer Komponente oder die anderen. Es ist ein Kreislauf, einschließlich der maximal edge. Starten Sie auf einen Eckpunkt an der einen Seite der maximale Rand und bewegen sich entlang des Zyklus. Weil Sie schließlich cycle-Runde auf die andere Seite der maximale Rand in die andere Komponente, die Sie finden - bevor dann - eine Kante hat eine Ecke in einer der getrennten Komponenten und eine Ecke in eine weitere der getrennten Komponenten. Da die Komponenten getrennt sind, die Kante ist nicht in der minimum-spanning-tree. Indem es der Baum Sie schließen Sie die Komponenten und erstellen Sie einen minimalen Spannbaum mit geringerem Gewicht als Sie begann mit -, so dass Sie original-minimum spanning tree war nicht minimal.
Manchmal, Ja.
Es hängt von der Art des Graphen. Wenn die Kante mit dem maximalen Gewicht ist die einzige Brücke, die verbindet die Komponenten eines Graphen, dann ist dieser Rand muss auch vorhanden sein in der MST.