Gibt es einen minimum-spanning-tree -, die nicht enthalten die min/max-gewichtete Kante?
Wenn wir einen (beliebigen) verbunden ungerichtete graph G, dessen Kanten haben verschiedene GEWICHTE,
- hat jeder MST von G enthält die minimal gewichtete Kante?
- ist es ein MST von G, die nicht enthalten die maximal gewichtete Kante?
Auch, ich bin eher dankbar, wenn jemand kann einen Tipp geben für die wichtigsten Dinge muss man im Hinterkopf behalten, beim Umgang mit solchen MST Fragen.
Dies ist ein Hausaufgaben problem. Danke.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Kann es sein, aber es muss nicht sein. Betrachten Sie ein 4-vertex-Diagramm wie folgt:
Der minimale Spannbaum besteht aus der edge set {CA, AB, BD}. Die maximale edge-Gewicht ist 50, sowie {- CD}, aber es ist nicht Teil des MST. Aber wenn G wurden schon gleich seine eigene MST, dann ist es offensichtlich würde enthalten, die seine eigene maximal edge.
Ja. MSTs haben eine cut-Eigenschaft. Ein Schnitt ist einfach eine partition der Knoten des Graphen in zwei disjunkte setzt. Für jeden Schnitt kann man machen, wenn das Gewicht einer Kante in diesem Schnitt ist kleiner als die GEWICHTE der anderen Kanten im Schnitt, dann ist diese Kante gehört zu allen MSTs in das Diagramm. Weil Sie garantiert, dass die kantengewichte sind Verschieden, Sie haben auch garantiert, dass es eine Kante, die kleiner ist als alle anderen Kanten.
Ihre beste Wette ist, um den Grund über Dinge, über die Eigenschaften der MSTs im Allgemeinen, und zu versuchen, zu konstruieren bestimmte Gegenbeispiele, die Sie denken, wird Ihren Fall beweisen. Ich gab eine Instanz von jeder Argumentation oben. Wegen der Schnitt-und Zyklus-Eigenschaften " können Sie immer genau bestimmen, welche Kanten in einem MST, so kann man systematisch testen Sie jede Kante, um zu bestimmen, ob oder nicht, es ist in der MST.
Ja. Nehmen wir an, wir haben eine
MST
die nicht enthalten min Gewicht Rand. Nun die Aufnahme dieser Kante auf dieMST
wird in einemcycle
. Nun es wird immer wieder eine Kante in dercycle
die entfernt werden können, zu entfernen, den Kreislauf und immer noch behaupten die Grafik(MST
) verbunden.Hängt von der graph. Wenn die
graph
selbst ist ein Baum, dann müssen wir, um alle seinen-1
Kanten in derMST
, so das max Gewicht Kante nicht ausgeschlossen werden kann. Auch wenn das maximale Gewicht der Kante ist einecut-edge
so, dass seine Ausgrenzung wird niemals das Resultat Konnektivität, dann das max Gewicht Kante nicht ausgeschlossen werden kann. Aber wenn die max Gewicht-Rand ist ein Teil einercycle
dann ist es möglich, ausschließen aus derMST
.Für Ihre erste Frage-die Antwort ist Nein, und kruskal ' s Algorithmus beweist es. Es werden immer wählen die minimalen Kosten Rand.
Für die zweite Frage, die Antwort ist ja, und es ist trivial zu finden, ein Beispiel-Diagramm:
Die Dritte Kante wird nie gewählt werden, es führt einen Zyklus. Also im Grunde, wenn die Kante mit maximalen Kosten würde, erstellen Sie einen Zyklus, wenn eingefügt in die MST, es wird nicht eingefügt werden.
Ich sehe, Sie zu studieren CSC263 durch die 2009 test? (Auch hier!)
Anderen Weg, um zu sehen, dass das minimum immer in der MST ist es zu betrachten, einfach auf das minimum edge (nennen wir ihn e):
(Vorausgesetzt, dieser hat verbindungen zu anderen verticies). Nun, für e NICHT aufgenommen werden in die endgültigen MST bedeutet, an einem Punkt haben wir, ohne Verlust der Allgemeingültigkeit, v1 in der MST, aber nicht v2. Jedoch, der einzige Weg, um hinzuzufügen v2 ohne hinzufügen von e wäre zu sagen, dass die Zugabe von v1 nicht fügen Sie e an die Warteschlange (weil per definition, e wäre an der Spitze der Warteschlange, weil es hat die niedrigste Priorität) dies widerspricht aber der MST-Bau-Satz.
Also im Grunde genommen, ist es nicht möglich, eine Kante mit minimalem Gewicht, nicht zu die Warteschlange die bedeutet, dass jeder MST gebaut würde.