Bestimmen Sie die Eindeutigkeit des min-cut

Disclaimer: diese war ein Hausaufgaben problem. Die Frist ist nun vergangen, so dass die Diskussionen fortsetzen können, ohne zu befürchten, dass.

Das problem das ich mit zu kämpfen ist, um zu bestimmen, ob ein bestimmtes minimum s-t Schnitt in einem Graphen G = (V, E) ist einzigartig. Es ist einfach genug zu finden einige min-Schnitt mittels eines max-flow-Algorithmus als pro dieses Beispiel, aber wie würden Sie es die min-cut?

InformationsquelleAutor Daniel Buckmaster | 2011-10-06
  1. 13

    Ok, da Sie nicht wollen, dass die ganze Antwort sofort, ich werde Ihnen ein paar Tipps. Lesen Sie so viele wie Sie fühlen, sind für Sie notwendig, und geben, wenn Sie sich - gehen Sie vor und Lesen Sie Sie alle.

    1:

    Der Schnitt ist einzigartig iff-es gibt keine anderen min-cut.

    2:

    Wenn Sie erfolgreich bei der Suche nach einer anderen min-cut, dann die erste min-cut ist nicht einzigartig.

    3:

    Dein link gab uns ein min-cut", die alle erreichbar Eckpunkte von s in der residual-graph. Können Sie denken Sie an einen Weg, um einen anderen Schnitt, nicht unbedingt die gleichen?

    4:

    Warum haben wir diese Eckpunkte erreichbar von s insbesondere?

    5:

    Vielleicht können wir etwas tun, Analog von t?

    6:

    Blick auf die gleiche residual-Graphen, beginnend bei t. Blick auf die Gruppe von vertices erreichbar von t in der reverse Richtung der Pfeile (also alle vertices die Reichweite t).

    7:

    Diese Gruppe ist auch ein min-cut (oder eigentlich S \, die Gruppe, um genau zu sein).

    8 (Letzte Antwort):

    Wenn das der Schnitt ist identisch zu Ihren original-Schnitt, dann gibt es nur einen. Andernfalls werden Sie nur gefunden, 2 Schnitte, so dass das original kann möglicherweise nicht eindeutig sein.

    • Tatsächlich, auch dies macht Sinn, auf die Beispiele, die ich gezogen habe aus... (ich habe gelesen, dass die ganze Sache... aber danke, es brechen!) Obwohl es scheint, dass er weit einfacher als die oben. Das macht auch Sinn für mich. Was ist Ihr nehmen auf die Antwort @davin gab?
    • seine Antwort, die so gut funktioniert, aber die Komplexität ist noch schlimmer: Ihr |E|*(|V|+|E|) statt nur (|V|+|E|) in meinem Fall, wenn ich mich nicht Irre.
    • Vorausgesetzt, die max-flow ist bereits berechnet. Alle max-flow algorithmen, die ich kenne sind rund um O(|V|^3) oder gleichwertig. Wenn es eine schnelle (O(|V|)) - Methode der Neuberechnung der max-Fluss, nachdem eine inkrementelle änderung (was ich vermute, es ist... musst Fragen, mein tutor) und dann die andere Methode würde zu reduzieren, um die gleiche Zeit-Komplexität (wenn auch vielleicht langsamer, wenn man Konstanten in die Rechnung).
    InformationsquelleAutor Eran Zimmerman
  2. 22

    Gliederung:

    Gegeben ein minimum S-T cut, (U,V) mit Schnitt-Kanten E', machen wir eine einfache Beobachtung: Wenn dieses minimum cut ist nicht eindeutig, dann gibt es einige andere minimale Schnitt mit einem Satz von Schnitt-Kanten E", so dass E" != E'.

    Wenn dem so ist, können wir die Iteration über jede Kante in E', hinzu, um dessen Kapazität, eine Neuberechnung der max flow, und prüfen Sie, ob es erhöht.

    Als Ergebnis der Beobachtung über, es existiert eine Kante E', die, wenn erhöht, der maximale Durchfluss nicht erhöhen iff der original-Schnitt ist nicht eindeutig.

    Ich lasse Sie in den details füllen und zu beweisen, dass dies ein poly-time-Aufgabe.

    • Arg. Es ist wirklich ganz einfach... ich habe Fragen zum ändern der Förderleistung früher, aber verworfen, dass die Linie des Denkens, da es sich um Lösung des max-flow auf einem verschiedenen graph.
    • dies sollte die akzeptierte Antwort
    • in diesem Zusammenhang gab er ein Beispiel für mehr als ein min-cut? stackoverflow.com/questions/34820333/...
    InformationsquelleAutor davin
  3. 2

    Gegeben, das max flow/min cut-problem ist wirklich eine Lineare Programmierung problem(primal/dual bzw. ist), denke ich, dass jede Methode zu überprüfen Einzigartigkeit der LP-Lösung und der Suche nach alternativen die optimale Lösung, wenn Ihr nicht eindeutig verwendet werden können, in diesem Zusammenhang.
    Habe ich gegoogelt, um zu finden, die dieses Papier :Auf die Einzigartigkeit der Lösungen von Linearen Programmen
    EDIT 1: Basierend auf Vorschlag von dzhuang, für diejenigen, die nicht bewusst, dass das maxflow-mincut-theorem ist ein Sonderfall der starken Dualität theorem in linearer Programmierung, hier ist der link zur Erklärung dieser nuance: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Linear_program_formulation

    • "Das max-flow problem ist ein lineares problem, aber die min-cut nicht."en.wikipedia.org/wiki/...
    • In welchem Sinne Sie behaupten, dass min-cut ist nicht ein lineares problem?
    • Sorry mein Fehler, ich habe nicht bemerkt, Sie beziehen sich auf den prime/dual-Beziehung. Ich ziehe meinen Kritiker, und wenn Sie Bearbeiten können (zum Beispiel, fügen Sie die obige wikipedia-Verweis) Ihre ursprüngliche Antwort, dann kann ich den Vorgang rückgängig machen downvote, und fügen Sie ein upvote.
    InformationsquelleAutor Jayant Apte
Schreibe einen Kommentar