BigIssue
Utente Attivo
- Messaggi
- 226
- Reazioni
- 18
- Punteggio
- 45
Buongiorno
chi di voi è studente di Milano unimi? Sto affrontando l'esame di algoritmi e strutture dati. Cerco ripetizioni su alcuni argomenti che non ho capito. Per chi fosse disponibile mi contatti presto.
Alcune definizioni
Sia G = (V,E) una rete di flusso con una funzione capacità c.
Sia s la sorgente della rete e sia t il pozzo.
Un cammino aumentante è semplicemente un cammino p da s a t nella rete residua
La capacità di un cammino aumentante p è la minima capacità degli archi di p nella rete residua:0
cf ( p) min{cf (u,v): uv arco di p}
cf = capacità
f = flusso
Metodo del cammino aumentante: Aumenta ripetutamente il flusso lungo dei cammini aumentanti finché non si arrivi ad un flusso di valore massimo Dimostreremo ora che il flusso è massimo se e solo se non ci sono cammini aumentanti da s a t nella rete residua Per farlo abbiamo bisogno di definire il concetto di taglio in una rete di flusso
Ora metto nel testo lo pseudocodice del metodo di ford fulkerson
Ora metto nel testo questa figura che rappresenta una rete rappresentata da un grafo orientato pesato. In cui ce un flusso e la capacità. Viene fatta un operazione di inizializzazione che considera 4, la capacità di fluso come valore piu piccolo tra tutto il grafo.
Quindi ogni arco ha due valori (tranne se è duplicato in quel caso 4 4 viene omesso)
Un esempio è il flusso: 4 e la capacità 16: cioè il peso dell'arco.
1) Data la definizione di cammino aumentante perchè quello in verde è un cammino aumentante? come lo deduco?
Ora metto nel testo questa figura indicante la rete residua.Ogni arco lo sdoppia in entrante e uscente. In quello Entrante (per intenderci quello con direzione inversa) mette 4 cioè il flusso corrente sull'arco,invece quelle rimanente uscente (per intenderci quelo di partenza) mette 12 ( 16 - 4). E cosi lo fa per tutti gli archi del cammino aumentante.
2 ) Poi seleziona un altro cammino aumentante dalla rete residua. Guarda gli archi uscenti o entranti? stesso dubbio come individua dagli archi il cammino aumentante?
chi di voi è studente di Milano unimi? Sto affrontando l'esame di algoritmi e strutture dati. Cerco ripetizioni su alcuni argomenti che non ho capito. Per chi fosse disponibile mi contatti presto.
Alcune definizioni
Sia G = (V,E) una rete di flusso con una funzione capacità c.
Sia s la sorgente della rete e sia t il pozzo.
Un cammino aumentante è semplicemente un cammino p da s a t nella rete residua
La capacità di un cammino aumentante p è la minima capacità degli archi di p nella rete residua:0
cf ( p) min{cf (u,v): uv arco di p}
cf = capacità
f = flusso
Metodo del cammino aumentante: Aumenta ripetutamente il flusso lungo dei cammini aumentanti finché non si arrivi ad un flusso di valore massimo Dimostreremo ora che il flusso è massimo se e solo se non ci sono cammini aumentanti da s a t nella rete residua Per farlo abbiamo bisogno di definire il concetto di taglio in una rete di flusso
Ora metto nel testo lo pseudocodice del metodo di ford fulkerson
Ora metto nel testo questa figura che rappresenta una rete rappresentata da un grafo orientato pesato. In cui ce un flusso e la capacità. Viene fatta un operazione di inizializzazione che considera 4, la capacità di fluso come valore piu piccolo tra tutto il grafo.
Quindi ogni arco ha due valori (tranne se è duplicato in quel caso 4 4 viene omesso)
Un esempio è il flusso: 4 e la capacità 16: cioè il peso dell'arco.
1) Data la definizione di cammino aumentante perchè quello in verde è un cammino aumentante? come lo deduco?
Ora metto nel testo questa figura indicante la rete residua.Ogni arco lo sdoppia in entrante e uscente. In quello Entrante (per intenderci quello con direzione inversa) mette 4 cioè il flusso corrente sull'arco,invece quelle rimanente uscente (per intenderci quelo di partenza) mette 12 ( 16 - 4). E cosi lo fa per tutti gli archi del cammino aumentante.
2 ) Poi seleziona un altro cammino aumentante dalla rete residua. Guarda gli archi uscenti o entranti? stesso dubbio come individua dagli archi il cammino aumentante?
Ultima modifica: