Determina se un flusso può soddisfare le richieste del nodo in un grafico acyclico diretto

Question

Ho il seguente problema che sto cercando di risolvere senza successo:

Ho un grafico diretto con richieste del nodo. A differenza della circolazione con le richieste, questi nodi richiedono non "sottrarre" dal flusso - i nodi richiedono semplicemente che ci sarebbe un flusso di forza k che scorre attraverso di loro. Il grafico è acyclic, tuttavia, non è un albero - i percorsi multipli esistono dal più alto ai nodi inferiori.

La domanda è, se un flusso di forza r può soddisfare tutte le richieste dei nodi. Naturalmente, un flusso con forza più di k può fluire attraverso un nodo con domanda k . Inoltre, non ci sono limiti di capacità nel grafico di input.

Ho bisogno di ridurre questo problema al problema del flusso massimo. Ho cercato di ridurlo alla circolazione con limiti inferiori e la circolazione con le richieste, ma senza successo, poiché non riesco a scoprire un buon modo su come in qualche modo limitare il flusso nei nodi di essere minimo mentre si soddisfano le richieste e la misurazione allo stesso tempo.

Answer 1

Aggiungi una nuova fonte $ s '$ e il bordo $ (s', s) $ Con la capacità massima e minima della classe $ r $ .

Per ogni vertice $ V $ con richiesta $ d $ Fai quanto segue:

.
• Sostituire $ V $ con due vertici $ v_1 $ e $ v_2 $ .
• Sostituisci tutti gli ex bordi $ (u, v) $ con $ (u, v_1) $
• Sostituisci tutti gli ex bordi $ (v, u) $ con $ (v_2, u) $ .
• Aggiungi il bordo $ (v_1, v_2) $ con capacità minima $ d $ . .

Il problema è ora equivalente a verificare se esiste un flusso fattibile in una rete con capacità minime e massime del bordo.

Questo problema è noto e può essere ridotto al flusso massimo (vedi, ad esempio, "saldi e pseudoflows" nel libro Algoritmi di Jeff Erickson).

Essenzialmente, se $ d $ è la somma di tutte le capacità minime dei bordi:

.
• Aggiungi una nuova sorgente vertice $ s ^ * $ e un nuovo target vertice $ t ^ * $ .
• Aggiungi il bordo $ (s ^ *, s ') $ con capacità massima $ + \ INFTY $ .

• per ogni bordo $ (u, v) $ con capacità minima $ c \ neq 0 $ < / Spaccatura> e capacità massima $ c $ , aggiungere il bordo $ (u, t ^ *) $ con capacità $ c $ , il bordo $ (s ^ *, v) $ con capacità $ c $ , rimuovere la capacità minima da $ (u, v) $ e modificare la capacità massima di $ (u, v) $ a $ cc $ (se $ C $ era $ + \ Infty $ Quindi la nuova capacità è anche $ + \ INFTY $ ).

• Controllare se il flusso massimo di $ s ^ * $ a $ t ^ * $ è uguale a $ d $ .