Dato un flusso di rete trovare se c'è un taglio minimo che solo uno dei bordi indicati giaceva su di esso

Question

Dato un flusso di rete $ g= (v, e) $ con funzione capacità $ c $ Source $ s $ e foro $ T $ , e dato 2 bordi $ E_1, e_2 $ .

Trova se esiste un taglio min-tali che solo uno dei bordi appartiene al minimo.

Spero di ottenere aiuto.

Answer 1

In primo luogo, calcola il valore di taglio minimo $ c $ della rete.

Secondo, rimuovere il bordo $ E_1 $ e aumentare la capacità di $ E_2 $ all'infinito, quindiComputa il valore minimo di taglio $ c_1 $ della nuova rete.

terzo, rimuovere il bordo $ E_2 $ e aumentare la capacità di $ E_1 $ all'infinito, quindiComputa il valore minimo di taglio $ c_2 $ della nuova rete.

Ora puoi controllare se $ c-c_1 \ ge c (e_1) $ o $ c-c_2 \ gec (E_2) $ per vedere se esiste un min-tagliato nella rete iniziale che contiene esattamente una delle $ E_1, E_2 $ .