Flusso massimo

Flusso massimo

Ordinamento delle coppie di nodi

Mettiamo in ordine tutte le coppie di nodi (quelli evidenziati).

Flussi e collegamenti

Nella prima colonna scriviamo i rispettivi flussi che legano i nodi, preceduti dallo 0.

Delta percorso

Da parte, scriviamo su una riga tutti i nodi:

1 2 3 4 5 6 7

Verifica dei collegamenti

Partiamo dal numero 1 e chiediamoci: l'1 arriva al 2? Per rispondere a questa domanda, guardiamo i collegamenti tra i nodi (1,2/1,3/1,4 ecc...). Se il collegamento tra i nodi c'è (e in questo caso c'è), per sapere se l'1 arriva al 2 dobbiamo guardare i valori che abbiamo riportato nella I colonna: se dopo la virgola c'è un numero maggiore di 0, allora la risposta è positiva e cioè l'1 arriva al 2. Quindi sotto al 2 (dell'elenco dei nodi scritti da parte nel passaggio III) mettiamo l'1. Da un lato scriviamo i numeri che “troviamo”. Quindi, tra i numeri trovati, avremo:

• 1 è il numero con il quale siamo partiti;
• 2 è il numero che abbiamo appena trovato.

Elenco nodi Numeri trovati

1 2 3 4 5 6 7 1 2/ 1

Continuiamo. L'1 arriva al 3? Sì. Quindi: scriviamo 1 sotto al 3 dell'elenco dei nodi e aggiungiamo 3 ai numeri trovati.

Elenco nodi Numeri trovati

1 2 3 4 5 6 7 1 2 3/ 1 1

L'1 arriva al 4? Sì. Quindi scriviamo 1 sotto al 4 e aggiungiamo il 4 ai numeri trovati.

Elenco nodi Numeri trovati

1 2 3 4 5 6 7 1 2 3 4/ 1 1 1

L'1 arriva al 5? No, come possiamo vedere dall'elenco fatto nella tabella e nella figura, non c'è nessun collegamento tra 1 e 5. Quindi andiamo ai numeri trovati e passiamo al numero successivo al primo, in questo caso 2.

Adesso ricominciamo con il 2 dal punto in cui eravamo rimasti e ci chiediamo: il 2 arriva al 5? Sì, quindi mettiamo il 2 sotto al 5 e aggiungiamo il 5 ai numeri trovati.

Elenco nodi Numeri trovati

1 2 3 4 5 6 7 1 2 3 4 5/ 1 1 1 2

Il 2 arriva al 6? No. Quindi andiamo ai numeri trovati e passiamo al numero successivo al 2: il 3. Proseguiamo: il 3 arriva al 6? Sì. Quindi scriviamo 3 sotto al 6 e aggiungiamo il 6 ai numeri trovati.

Elenco nodi Numeri trovati

1 2 3 4 5 6 7 1 2 3 4 5 6/ 1 1 1 2 3

Il 3 arriva al 7? No. Quindi andiamo ai numeri trovati e passiamo al numero successivo: il 4. Il 4 arriva al 7? Sì. Quindi scriviamo 4 sotto a 7 e aggiungiamo 7 ai numeri trovati.

Elenco nodi