Gimmy

.consigliere.

User info:

Registered: Jun 2008
Posts: 117 (0.02 al dì)
Location: Palazzolo Milanese
Corso: Informatica Magistrale
Anno: 1°
Time Online: 22:56:53 [...]
Status: Offline

Post actions:

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

spenk.85

.illuminato.

User info:

Registered: Nov 2005
Posts: 196 (0.03 al dì)
Location: Muggiò
Corso: Comunicazione Digitale
Anno: x
Time Online: 1 Day, 12:55:02: [...]
Status: Offline

Post actions:

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

Gimmy

.consigliere.

User info:

Registered: Jun 2008
Posts: 117 (0.02 al dì)
Location: Palazzolo Milanese
Corso: Informatica Magistrale
Anno: 1°
Time Online: 22:56:53 [...]
Status: Offline

Post actions:

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.

carla86

User info:

Registered: Dec 2006
Posts: 219 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 6 Days, 21:40:54 [...]
Status: Offline

Post actions:

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.

Gimmy

.consigliere.

User info:

Registered: Jun 2008
Posts: 117 (0.02 al dì)
Location: Palazzolo Milanese
Corso: Informatica Magistrale
Anno: 1°
Time Online: 22:56:53 [...]
Status: Offline

Post actions:

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?

carla86

User info:

Registered: Dec 2006
Posts: 219 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: Terzo
Time Online: 6 Days, 21:40:54 [...]
Status: Offline

Post actions:

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...

Gimmy

.consigliere.

User info:

Registered: Jun 2008
Posts: 117 (0.02 al dì)
Location: Palazzolo Milanese
Corso: Informatica Magistrale
Anno: 1°
Time Online: 22:56:53 [...]
Status: Offline

Post actions:

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

Attachment: es_6_24-07-08.jpg
This has been downloaded 26 time(s).

spenk.85

.illuminato.

User info:

Registered: Nov 2005
Posts: 196 (0.03 al dì)
Location: Muggiò
Corso: Comunicazione Digitale
Anno: x
Time Online: 1 Day, 12:55:02: [...]
Status: Offline

Post actions:

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...

Gimmy

.consigliere.

User info:

Registered: Jun 2008
Posts: 117 (0.02 al dì)
Location: Palazzolo Milanese
Corso: Informatica Magistrale
Anno: 1°
Time Online: 22:56:53 [...]
Status: Offline

Post actions:

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?

Last edited by Gimmy on 16-01-2010 at 16:44

spenk.85

.illuminato.

User info:

Registered: Nov 2005
Posts: 196 (0.03 al dì)
Location: Muggiò
Corso: Comunicazione Digitale
Anno: x
Time Online: 1 Day, 12:55:02: [...]
Status: Offline

Post actions:

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.

Gimmy

.consigliere.

User info:

Registered: Jun 2008
Posts: 117 (0.02 al dì)
Location: Palazzolo Milanese
Corso: Informatica Magistrale
Anno: 1°
Time Online: 22:56:53 [...]
Status: Offline

Post actions:

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...

spenk.85

.illuminato.

User info:

Registered: Nov 2005
Posts: 196 (0.03 al dì)
Location: Muggiò
Corso: Comunicazione Digitale
Anno: x
Time Online: 1 Day, 12:55:02: [...]
Status: Offline

Post actions:

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