Angesichts eines Netzwerkflusses finden Sie, wenn ein Minute ein Minute enthält, dass nur einer der angegebenen Kanten darauf lag

Question

Angesichts eines Netzwerkflusses $ g= (V, E) $ mit Kapazitätsfunktion $ C $ Quelle $ s $ und loch $ T $ , und gegebenenfalls 2 Kanten $ E_1, E_2 $ .

Finden Sie, ob ein Min-Cut vorhanden ist, so dass nur einer der Kanten zum Min-Cut gehört.

hoffe, Hilfe zu bekommen.

Answer 1

Erster, berechnen Sie den minimalen Schnittwert $ C $ des Netzwerks.

zweiter, entfernen Sie die Kante $ E_1 $ und erhöhen Sie die Kapazität von $ E_2 $ bis unendlich, dannBerechnen Sie den minimalen Schnittwert $ C_1 $ des neuen Netzwerks.

Drittel, Rand Rand $ E_2 $ und erhöhen Sie die Kapazität von $ E_1 $ bis unendlich, dannBerechnen Sie den minimalen Schnittwert $ C_2 $ des neuen Netzwerks.

Jetzt können Sie überprüfen, ob $ C-C_1 \ GE C (E_1) $ oder $ C-C_2 \ gec (e_2) $ Um zu sehen, ob in dem anfänglichen Netzwerk ein Min-Cut vorhanden ist, der genau einen von $ E_1 enthält, E_2 $ .

.