Wird der minimale Spannbaum nicht nur die von der Zykluseigenschaft angegebenen Kanten haben?[Duplikat]

Question

Diese Frage hat bereits eine Antwort hier

Welche Kanten sind nicht in einem MST? (1 Antwort)

geschlossene vor 4 Monaten .

Ich habe gerade angefangen, die "minimalen Spannbäume" (MSTS) zu verstehen und auf die Zykluseigenschaft gestoßen zu sein. Ich beziehe mich auf das Buch-Algorithmus-Design von Jon Kleinberg und Eva Tardos. Die Erklärung der Immobilie, wie sie im Buch verfasst ist, ist:

Nehmen Sie an, dass alle Randkosten unterschiedlich sind. Sei c beliebige Zyklus in G sein, und sei Rand e= (v, w) die teuerste Kante, die zu C gehört, dann gehört E nicht zu keinem minimalen Spannbaum.

Jetzt ist mein Zweifel: Sind die Kanten eines Diagramms (ungerichtetes Graph mit unterschiedlichen positiven Gewichten), die die Zykluseigenschaft nicht erfüllen, die nur die einzigen, die nicht in der MST vorhanden sind oder andere Kanten geben Gehören Sie nicht zur MST und sind nicht von dieser Immobilie abgedeckt?

Ich kann nicht mit einem Beweis kommen, um darüber zu streiten, ob solche Kanten existieren oder nicht. Können einige bitte einen Beweis dafür geben?

Answer 1

Lassen Sie uns sagen, dass ein Rand $ E $ in $ g $ ist schlecht < / stark> Wenn ein Zyklus in $ G $ existiert, in dem $ E $ maximales Gewicht hat.

Definieren Sie $ {\ CAL B}={E ~ | ~ E $ ist schlecht in $ g \} $ Um die Sammlung aller schlechten Kanten zu sein.

Ihre Frage ist, ob die Grafik $ (g - {\ cal B}) $ der MST der $ g $ (Angenommen, alle Kantengewichte sind unterschiedlich). Die Antwort ist ja!

Um dies zu beweisen, genügt es zu zeigen, dass $ (g - {\ cal b}) $ azyklisch ist.

Nehmen Sie daran teil, dass $ (g - {\ \ cal b}) $ einen Zyklus enthält, sagen Sie $ C $ . Beobachten Sie, dass $ C $ ein Zyklus in $ G $ ist. Lassen Sie $ E ^ * $ Seien Sie der Rand des maximalen Gewichts im Zyklus $ C $ . Jetzt $ E ^ * $ ist ein schlechter $ (G - {\ cal b}) $ an erster Stelle. Dies zeigt, dass $ (g - {\ cal b}) $ azyklische ist.

Answer 2

Es tut mir leid, wenn ich Ihre Frage nicht verstanden habe, aber was ich denke, dass Sie fragen wollten, ist, ob es möglich ist, dass eine Kante nicht in einem MST ist, wenn diese Kante nicht in einem Zyklus ist.

Hier ist meine Antwort.

lassen Sie uns annehmen, dass wir eine Kante (u, v) in einem Graphen G haben, das ist nicht Teil eines Zyklus.Dies würde bedeuten, dass es keinen Pfad von u bis v gibt, der nicht der Rand (u, v) ist. Wenn der Rand (u, v) nicht in der MST war, würde dies bedeuten, dass es in diesem MST keinen Weg von u bis v gibt, was bedeutet, dass der MST getrennt werden würde, und somit kein MST überhaupt nicht. Wenn daher eine Kante nicht Teil eines Zyklus ist, muss er sich in der MST des Graphen befinden.