Esercizio 5.2.10
0 passi visti su 2
Consegna
Prendete i grafi orientati degli esercizi finora dati, interpretate i costi come capacità e calcolate il massimo flusso dal nodo 1 al nodo . (Se il nodo 1 ha archi entranti , invertitene l'orientamento in , lasciandone inalterata la capacità.)
0Grafo della Figura 5.2apri
Gli archi (6,1) e (7,1) diventano (1,6) e (1,7). Il primo percorso è 1 → 7, con ; il secondo 1 → 4 → 5 → 7, con . Poi il pozzo non si etichetta: il flusso massimo vale 2. Nel taglio finale 7 è l'unico nodo non etichettato, e gli archi che vi entrano, (1,7) e (5,7), sono saturi: .
1Grafo dell'Esercizio 5.2.8apri
L'unico arco che entra nel nodo 7 è (4,7), con capacità 1: il primo percorso, 1 → 4 → 7, lo satura e il flusso massimo vale 1, con il taglio attorno al nodo 7.