.dsy:it. (http://www.dsy.it/forum/)
- Ricerca operativa (http://www.dsy.it/forum/forumdisplay.php?forumid=228)
-- Es Flusso Max (http://www.dsy.it/forum/showthread.php?threadid=39750)

Es Flusso Max

Ecco il domandone... Dato un grafo come costruisco il relativo grafo incrementale a seconda se i valori sugli archi sono capacità superiore-costo unitario oppure capacità superiore-flusso inviato?

Grazie

il grafo incrementale è sempre capacità residua nel verso di percorrenza del arco orginale, capacità deflusso (flusso mandato) nell'arco di ritorno.

esempio: arco originale s->b (7 capacità sup, 2 flusso inviato). L'arco sul grafo incrementale sarà: s->b (5) b->a (2).

Scambio di dritte: sai come aggiornare poi il grafo incrementale quando ho trovato un cammino aumentante oppure quando devo cercare il flusso di costo minimo? Mi incarto in quel punto

ok, pero quello che non capivo è che in alcuni esercizi c'è scritto che i valori sugli archi sono capacità superiore, flusso inviato(e si fa come dici tu), ma ci sono altri es dove i valori sugli archi indicano capacità superiore,costo unitario e qui non so come fare...

Per aggiornare il grafo incrementale quando cerchi i cammini per il flusso massimo devi sommare agli archi uscenti del cammino scelto il valore minimo degli archi(ossia il collo di bottiglia) e sottrarlo invece agli archi in uscita. Per esempio se scegli s-a-b-t e il collo di bottiglia è 2, devi sottrarre a tutti gli archi uscenti che collegano i 4 nodi il valore 2 e sommarlo ai relativi archi in entrata.
Cmq guarda la lezione 16-01-2006 presente nell'area filez, che lì è spiegato bene.

semplicemente quando nn ce il flusso inviato.. parti con le frecce d ritorno a zero.
i costi unitari ti serve per la seconda parte, ossia quando l'esercizio ti chiede se il flusso inviato l'hai inviato a costo min.

mmm... quindi prima applico l'algoritmo di ford fulkerson per determinare il flusso massimo (ossia cerco i vari cammini da s a t finchè on ottengo un taglio di capacità minima, e fin qui non uso i costi unitari giusto?) poi invece per la seconda parte devo usare i costi unitari, metterli sul grafo appena ottenuto e vedere se ci sono cicli a costo negativo?

si esatto.
attenzione ke quando hai il flusso iniziale, non devi partire cn i percorsi da zero ma le capacità sn gia state un po usate...

ok, ora provo a fare qualche esercizio con il flusso...
intanto ho fatto questo con i costi unitari, dovrebbe essere giusto...

Originally posted by Gimmy
ok, ora provo a fare qualche esercizio con il flusso...
intanto ho fatto questo con i costi unitari, dovrebbe essere giusto...

bella
menter per gli es con il flusso inviato per passare alla rete incrementale devo fare capacità supeiore - flusso inviato (uscente) e flusso inviato (entrante) giusto?

Se invece nella rete incrementale (ottenuta da capacità superiore,flusso inviato) ho già dei possibili tagli non faccio nessun cammino e taglio direttamente?

se hai già del flusso inviato devi mettere l'arco di ritorno con il valore del flusso, mentre nella direzione dell'arco originale la capacità rimanente (cap tot - flusso inviato).

il taglio da che ne so io è uno soltanto. sostanzialmente dovresti fare così:
-rete incrementale
-controlli la presenza dei cammini aumentanti, se ci sono modifichi la rete incrementale
-quando non hai più cammini allora hai un taglio. per trovare questo taglio parti da nodo di partenza e guardi i nodi che puoi raggiungere, gli altri sono al di la del taglio. Nel esempio dell'esercizio sopra: parti da 1; da 1 non posso andare da nessuna parte, quindi il taglio è tra 1 e tutti gli altri nodi.

si per il procedimento ok, pero in un es mi è capitato che passando alla rete incrementale avevo già il taglio sul nodo 1 dell'es che abbiamo fatto, cioè praticamente ho già gli archi uscenti dal nodo 1 a 0, e quindi teoricamente potrei già tagliare...

si, significa in pratica che non hai nessuno cammino aumentante e il flusso è già instradato in maniera ottimale