Flusso massimo

DELTA

PERCORSO

III- Da parte, scriviamo su una riga tutti i nodi

1 2 3 4 5 6 7

-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 NUMERI TROVATI

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

/ 1 1 1 2 3 4

Abbiamo completato la riga. Adesso dobbiamo trovare il percorso: si parte dall'ultimo nodo

− ( in questo caso il 7) e facciamo il percorso a ritroso: a 7 come ci siamo arrivati? É

sufficiente guardare il numero che si trova al di sotto del 7: il 4. E al 4 come ci siamo

arrivati? Guardiamo la prima riga e vediamo che sotto il 4 c'è l'1.

1 2 3 4 5 6 7

/ 1 1 1 2 3 4

In ordine, abbiamo trovato i seguenti numeri 741, che riporteremo scritti al contrario (147)

− nella II colonna della tabella alla voce “percorso”. Il numero 147 ci da le coppie di nodi 1,4

e 4,7. Andiamo alla I colonna della tabella e sottolineiamo i valori corrispondenti delle

coppie di nodi 1,4 e 4,7, che sono rispettivamente 0,12 e 0,19. Di questi due valori,

prendiamo il valore minore (0,12) e lo riportiamo alla voce delta della II colonna, senza però

lo 0 che lo precede.

I COLONNA II COLONNA

1,2 0,12

1,3 0,12

1,4 0,12

2,4 0,11

2,5 0,3 0

3,4 0,12

3,6 0,21

4,5 0,1 0

4,6 0,14

4,7 0,19

5,7 0,12

6,7 0,9

DELTA 12

PERCO 147

RSO

-Prendiamo i valori delle coppie di nodi che abbiamo sottolineato (0,12 e 0,19) e prima della virgola

sommiamo 12 ( il valore che abbiamo trovato nel passaggio precedente) e dopo la virgola

sottraiamo 12. Quindi avremo 12,0 e 12,7..

-Dunque, il nuovo valore per la coppia di nodi 1,4 è 12,0 e per la coppia 4,7 è 12,7. Riportiamo

questi valori nella II colonna, mentre i valori degli altri nodi li trascriviamo uguali.

I COLONNA II COLONNA

1,2 0,12 0,12

1,3 0,12 0,12

1,4 0,12 12,O

2,4 0,11 0,11

2,5 0,3 0 0,3O

3,4 0,12 0,12

3,6 0,21 0,21

4,5 0,1 0 0,1O

4,6 0,14 0,14

4,7 0,19 12,7

5,7 0,12 0,12

6,7 0,9 0,9

DELTA 12

PERCO 147

RSO

IV- Adesso ricominciamo come al passo III. Continuiamo sotto l'elenco di nodi che avevamo fatto

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

/ 1 1 1 2 3 4

Ci chiediamo: l'1 arriva al 2? Guardiamo i “nuovi valori”della II colonna e vediamo che l'1

− arriva al 2, quindi solito procedimento:

1 2 3 4 5 6 7 1 2

/ 1 1 1 2 3 4

/ 1

-L'1 arriva al 3? Sì. Solito procedimento...

1 2 3 4 5 6 7 1 2 3

/ 1 1 1 2 3 4

/ 1 1

-L'1 arriva al 4? No, perchè il numero dopo la virgola è 0. Quindi andiamo al numero successivo

all'1 dei numeri trovati: il 2.

- Continuiamo fino a completare la riga e avremo

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

/ 1 1 1 2 3 4

/ 1 1 2 2 3 4

Dobbiamo adesso trovare il percorso. Guardiamo sempre al 7 sulla prima riga. Come ci

− siamo arrivati al 7? Guardiamo all'ultima riga e vediamo che c'è il 4. E al 4 come ci siamo

arrivati? Andiamo al 4 della prima riga e vediamo che all'ultima riga c'è il 2. E al 2 come ci

siamo arrivati? Andiamo al 2 della prima riga e vediamo che nell'ultima riga c'è l'1. Quindi

avremo 7421, che scritto al contrario è 1247. Facciamo lo stesso procedimento di prima.

1,2 0,12 0,12 7,5

1,3 0,12 0,12 0,12

1,4 0,12 12,O 12,O

7,4

2,4 0,11 0,11

2,5 0,3 0 0,3O 0,3O

3,4 0,12 0,12 0,12

3,6 0,21 0,21 0,21

4,5 0,1 0 0,1O 0,1O

4,6 0,14 0,14 0,14

4,7 0,19 12,7 5,O

5,7 0,12 0,12 0,12

6,7 0,9 0,9 0,9

DEL 12 7

TA

PER 147 1247

COR

SO Continuiamo ancora...

−

1 2 3 4 5 6 7

/ 1 1 1 2 3 4

/ 1 1 2 2 3 4

/ 1 1 2 2 3 5

Questa volta il percorso è 1257, lo riportiamo nella tabella e continuiamo come prima.

−

1,2 0,12 0,12 7,5 2,O

1,3 0,12 0,12 0,12 0,12

1,4 0,12 12,O 12,O 12,O

2,4 0,11 0,11 7,4 7,4

5,25

2,5 0,3 0 0,3O 0,3O

3,4 0,12 0,12 0,12 0,12

3,6 0,21 0,21 0,21 0,21

4,5 0,1 0 0,1O 0,1O 0,1O

4,6 0,14 0,14 0,14 0,14

4,7 0,19 12,7 5,O 5,O

5,7 0,12 0,12 0,12 5,7

6,7 0,9 0,9 0,9 0,9

DEL 12 7 5

TA

PER 147 1247 1257

COR

SO Continuiamo. L'1 arriva al 2? No. Quindi sotto il 2 non scriviamo nulla e andiamo avanti.

− L'1 arriva al al 3? Sì, quindi sotto al 3 mettiamo l'1. L'1 arriva al 4? No. Quindi andiamo al

numero successivo all'1 dei numeri trovati:3. Il 3 arriva al 2? No. Il 3 arriva al 4?Sì, quindi

sotto il 4 mettiamo il 3. Il 3 arriva al 5? No. Il 3 arriva al 6? Sì, quindi sotto al 6 mettiamo il

3. Il 3 arriva al 7? No, quindi passiamo al 4. Il 4 arriva al 2? No, però c'è il “reciproco” e

cioè 2,4. Quindi sotto al 2 mettiamo il 4. Il 4 arriva al 5? Sì ecc...ecc...fino a completare la

riga.

1 2 3 4 5 6 7

/ 1 1 1 2 3 4

/ 1 1 2 2 3 4

/ 1 1 2 2 3 5

/ 4 1 3 4 3 6

Il percorso trovato è 1367, lo riportiamo nella tabella e continuiamo come prima.