Esercizio 5.2.8
Si usa l'etichettatura dello pseudocodice della dispensa. Gli appunti della lezione 12 elaborano i nodi in un altro ordine: i percorsi cambiano, il flusso massimo e il taglio no.
0 passi visti su 2
Consegna
Con riferimento al grafo orientato con capacità (1,2) 1, (1,4) 5, (1,6) 3, (2,3) 5, (2,4) 1, (2,5) 6, (2,6) 4, (4,5) 3, (4,7) 1, (5,3) 9, (6,3) 2, (7,5) 1, si determini il flusso massimo dalla sorgente al pozzo .
0Ford-Fulkersonapri
Si parte dal flusso nullo. I nodi etichettati si elaborano dall'ultimo (pila); dentro un nodo prima gli archi uscenti, poi gli entranti.
| It. | Nodi elaborati ed etichette date | Percorso aumentante | dopo | |
|---|---|---|---|---|
| 1 | da 1: 2 [+1, 1], 4 [+1, 5], 6 [+1, 3]; da 6: 3 [+6, 2] | 1 → 6 → 3 | 2 | 2 |
| 2 | da 1: 2 [+1, 1], 4 [+1, 5], 6 [+1, 1]; da 6: nessuna; da 4: 5 [+4, 3], 7 [+4, 1]; da 7: nessuna; da 5: 3 [+5, 3] | 1 → 4 → 5 → 3 | 3 | 5 |
| 3 | da 1: 2 [+1, 1], 4 [+1, 2], 6 [+1, 1]; da 6: nessuna; da 4: 7 [+4, 1]; da 7: 5 [+7, 1]; da 5: 3 [+5, 1] | 1 → 4 → 7 → 5 → 3 | 1 | 6 |
| 4 | da 1: 2 [+1, 1], 4 [+1, 1], 6 [+1, 1]; da 6 e da 4: nessuna; da 2: 3 [+2, 1], 5 [+2, 1] | 1 → 2 → 3 | 1 | 7 |
| 5 | da 1: 4 [+1, 1], 6 [+1, 1]; da 6 e da 4: nessuna | nessuno | 7 |
1Flusso massimo e taglioapri
Il flusso massimo vale 7. Certificato: , gli archi uscenti (1,2), (4,5), (4,7) e (6,3) sono saturi, e .