Il flusso massimo con bordi reciprocamente esclusivi può essere ridotto al problema standard di flusso massimo?
-
04-11-2019 - |
Domanda
Sto lavorando con una rete di flusso come la seguente:
La fonte S ha quattro bordi, ciascuno con capacità 1, fuori dai nodi A, B, C e D. Tutti di A, B, C e D hanno bordi su altri due nodi, X e Y, anche con capacità 1 . X e Y hanno entrambi bordi con capacità 4 del lavandino t.
In genere questo avrebbe molte soluzioni: tutti i modi in cui potresti dividere A, B, C e D tra X e Y. Nella versione modificata, devo scegliere X o Y. Se il flusso acceso (x, t )> 0, il flusso su (y, t) deve essere 0 e viceversa. Quindi ci sono solo due soluzioni, che inviano tutte e 4 le unità di flusso tramite X o attraverso Y.
Mi chiedo se c'è un modo per ridurre questo vincolo al flusso massimo standard in modo da poter semplicemente eseguire Ford-Fulkerson su un grafico modificato. Questo, o se questo è fondamentalmente più difficile ed è un isomorfismo di un problema diverso.
In versioni più semplici come quella che ho disposto sopra potresti semplicemente ridurre la decisione a un problema in cui hai solo S, T e i nodi X e Y e devi inviare 1 unità di flusso attraverso la rete, ma io sono Lottando con il caso generale in cui abbiamo due bordi X e Y, solo uno dei quali è permesso avere un flusso diverso da zero attraverso di esso nella soluzione.
Nessuna soluzione corretta