Disclaimer: Dieses war ein Hausaufgabenproblem. Die Frist ist jetzt verstrichen, damit die Diskussionen fortgesetzt werden können, ohne sich darum kümmern zu müssen.
Das Problem, mit dem ich zu kämpfen habe, ist festzustellen, ob ein bestimmtes Minimum s-t in einem Graphen geschnitten ist G = (V, E) ist einzigartig. Es ist einfach genug, einige min-cut mit einem Max-Flow-Algorithmus nach Dieses Beispiel , aber wie würden Sie zeigen, dass es der Min-Cut ist?
Ok, da du die ganze Antwort nicht sofort haben willst, werde ich dir ein paar Hinweise geben. Lesen Sie so viele, wie Sie für notwendig halten, und wenn Sie aufgeben - gehen Sie voran und lesen Sie alle.
1:
Der Schnitt ist einzigartig, wenn kein anderer Min-Cut vorhanden ist.
2:
Wenn Sie einen anderen Min-Cut finden, ist der erste Min-Cut nicht eindeutig.
3:
Ihr Link gab uns einen Min-Cut, bei dem es sich um alle erreichbaren Vertices von s im Restgraphen handelt. Können Sie sich einen Weg vorstellen, um einen anderen Schnitt zu erhalten, nicht unbedingt den gleichen?
4:
Warum haben wir diese Scheitelpunkte insbesondere von s erreicht?
5:
Vielleicht können wir etwas analoges von t machen?
6:
Betrachten Sie denselben Restgraphen, beginnend bei t. Sehen Sie sich die Gruppe der Vertices an, die von t in der umgekehrten Richtung der Pfeile erreichbar sind (dh alle Vertices, die t erreichen können).
7:
Diese Gruppe ist auch ein Min-Cut (oder eigentlich S \ that Gruppe, um genau zu sein).
8 (endgültige Antwort):
Wenn dieser Schnitt mit Ihrem ursprünglichen Schnitt identisch ist, dann gibt es nur einen. Ansonsten hast du nur 2 Schnitte gefunden, also kann das Original nicht eindeutig sein.
Gliederung:
Bei einem minimalen ST-Schnitt (U, V) mit Schnittkanten E 'machen wir eine einfache Beobachtung: Wenn dieser minimale Schnitt nicht eindeutig ist, dann existiert ein anderer minimaler Schnitt mit einer Menge von Schnittkanten E '', so dass E ''! = E '.
Wenn ja, können wir über jede Kante in E 'iterieren, zu ihrer Kapazität hinzufügen, den maximalen Fluss neu berechnen und prüfen, ob sie erhöht wurde.
Als Ergebnis der obigen Beobachtung gibt es eine Kante in E ', die, wenn sie vergrößert wird, den maximalen Fluss nicht erhöht, wenn der ursprüngliche Schnitt nicht eindeutig ist.
Ich werde Sie verlassen, um die Details auszufüllen und zu beweisen, dass dies eine Poly-Zeit-Aufgabe ist.
Da das Max-Flow / Min-Cut-Problem wirklich ein lineares Programmierproblem (primal / dual) ist, rechne ich jede Methode zur Überprüfung der Eindeutigkeit der LP-Lösung und Suche nach einer alternativen optimalen Lösung, wenn sie nicht eindeutig ist. Ich googelte, um dieses Papier zu finden: Über die Einzigartigkeit von Lösungen für lineare Programme BEARBEITEN 1: Basierend auf der Anregung von dzhuang, ist für diejenigen, die nicht wissen, dass das Maxflow-Mincut-Theorem ein Sonderfall des starken Dualitätssatzes in der linearen Programmierung ist, der Link zur Erklärung dieser Nuance: Ссылка