Wird ein minimaler Spannbaum und ein Baum mit dem kürzesten Pfad immer mindestens eine Kante teilen?

Ich studiere Graphtheorie und ich habe eine Frage über die Verbindung zwischen minimalen aufspannenden Bäumen und kürzesten Pfadbäumen.Wird ein minimaler Spannbaum und ein Baum mit dem kürzesten Pfad immer mindestens eine Kante teilen?

Lassen G ein ungerichteter, zusammenhängender Graph sein, wo alle Kanten mit unterschiedlich Kosten gewichtet werden. Lassen Sie T ein MST von G sein und lassen T_s für einige Knoten einen kürzesten Weg-Baum sein s. Sind T und T_s garantiert, um mindestens eine Kante zu teilen?

Ich glaube, das ist nicht immer wahr, aber ich kann kein Gegenbeispiel finden. Hat jemand einen Vorschlag, wie man ein Gegenbeispiel findet?

Quelle

2013-06-13 Spartacus

Sind die Kantengewichte notwendig nicht negativ? – templatetypedef

Ja, das ist immer wahr wegen der Kanten, die mit ** s ** verbunden sind, die kürzeste Kante unter ihnen, die mit dem Spannbaum verbunden ist, ist auch ein Mitglied des kürzesten Pfadbaums. –

@TylerDurden Woher wissen Sie, dass eine der Kanten, die mit s im SPT kollidieren, auch eine der Kanten ist, die in der MST mit s auftreten? –

Ich denke, dass diese Aussage tatsächlich wahr ist, so bezweifle ich, dass Sie ein Gegenbeispiel finden können.

Hier ist ein Hinweis - nehmen Sie einen beliebigen Knoten in der Grafik und finden Sie einen kürzesten Pfad Baum für diesen Knoten. Nun überlegen Sie, was passieren würde, wenn Sie Prim's algorithm von diesem Knoten ausgehend ausführen würden - können Sie garantieren, dass mindestens eine Kante von der MST ihren Weg in die kürzeste Pfadstruktur findet?

Hoffe, das hilft!

Quelle

2013-06-13 17:55:10 templatetypedef

Danke für Ihre Antwort. Ich habe versucht, Ihre Methode Kruskal Algorithmus und Prim-Algorithmus zu verwenden, aber die beiden Bäume teilen immer mindestens eine Kante – Spartacus

@ Julius- Könnten Sie beweisen, dass nach Prim-Algorithmus beginnend von s, Sie sind garantiert * * mindestens eine Kante mit dem kürzesten Pfad zu haben? – templatetypedef

Ich glaube nicht, dass der Hinweis hilft, die Aussage zu beweisen oder zu widerlegen. Wenn ich Sie richtig verstehe, deutet dies darauf hin, dass eine bestimmte Menge von MSTs und eine bestimmte Menge von kürzesten Pfadbäumen immer eine Kante teilen, nicht dass sie für alle MSTs und kürzesten Pfadbäume eines allgemeinen Graphen gilt. –

Proof Um s und seiner kürzesten Pfadbaum T_s, der Keil in MST T ist w (s, v) Vertex-, und nehme an, es nicht der Fall ist existieren in T_s. dann muss es zu s, und es gibt einen Scheitelpunkt in dem Pfad (da w (s, v) nicht der kürzeste Pfad), ein kürzerer Weg von VBE der p sein nähme s, und macht -> p -> v, w (s , v)> = path (s -> p -> v). Entfernen w (s, v) und füge w (s, p) in T, wenn alle Kanten positiv sind und unterschiedliche, w (s, p) < w (s, v). Wir erhalten einen weniger Spannbaum T '.

Aber T ist ein MST.Hier ist der Widerspruch. Annahme nicht gilt, das beweist, dass T und T_s mindestens eine Kante zu teilen, und es ist w (s, v) in MST T.

Wenn es ein Gewicht mit 0 kostet, ist die Situation ähnlich. Sie können annehmen, dass die beiden Ecken, bei denen w (a, b) = 0 ist, die gleiche Ecke sind, und entfernen Sie eine von ihnen. Der Beweis funktioniert, wenn die Gewichte nicht negativ sind.

wenn einige Gewichte sind negativ und w (s, p)> w (s, v), das heißt, w (p, v) < 0, w (s, v)> = path (s ->p ->v) nicht w (s machen , p) < w (s, v) .Aber in MST T, w (s, v) sollte auch nicht existieren, weil Pfad (s ->p ->v) macht s zu v mit weniger Kosten, ersetzen w (s, v) in T mit w (s, p) und W (p, v) falls erforderlich macht einen weniger minimalen Spanning-Tree T‘. Noch Widerspruch.

Quelle

2013-06-14 01:53:30 vvy

Wird ein minimaler Spannbaum und ein Baum mit dem kürzesten Pfad immer mindestens eine Kante teilen?

Antwort

Verwandte Themen