Calcolatore di Flusso in Rete (Flusso Massimo)

Calcolatore di Flusso in Rete (Flusso Massimo)

Il Calcolatore di Flusso in Rete e Flusso Massimo calcola il flusso massimo da una sorgente scelta s a un pozzo scelto t in qualsiasi rete orientata con capacità. Sotto il cofano esegue il metodo Ford-Fulkerson con percorsi aumentanti basati sulla ricerca in ampiezza (l'algoritmo di Edmonds-Karp), quindi registra ogni percorso trovato in modo da poter rivedere l'intero processo decisionale un'iterazione alla volta. La pagina dei risultati evidenzia anche il taglio minimo (min-cut) — la partizione collo di bottiglia che dimostra che il valore del flusso è veramente ottimale.

Cos'è il problema del flusso massimo?

Una rete di flusso è un grafico orientato G = (V, E) insieme a una funzione di capacità c: E → ℝ_≥0. Due vertici sono distinti: la sorgente s (da dove ha origine il flusso) e il pozzo t (dove viene consumato). Un flusso f è qualsiasi assegnazione f(u, v) ≥ 0 sugli archi che rispetti:

Il problema del flusso massimo cerca il flusso f che massimizza |f|. Intuitivamente: se gli archi fossero tubi d'acqua con le capacità date, quanti litri al secondo puoi inviare da s a t?

Come funziona l'algoritmo — Ford-Fulkerson con BFS

L'algoritmo mantiene un grafico residuo insieme al flusso corrente. Per ogni arco (u, v) con capacità c e flusso corrente f, il grafico residuo contiene:

• un arco residuo in avanti (u, v) con capacità c − f (quanto può ancora essere spinto), e
• un arco residuo inverso (v, u) con capacità f (quanto del flusso impegnato può ancora essere annullato).

Ad ogni iterazione esegue una ricerca in ampiezza (BFS) da s a t sul grafico residuo. Se viene trovato un percorso, la capacità minima dell'arco sul percorso — il collo di bottiglia — viene aggiunta al flusso su ogni arco in avanti e sottratta su ogni arco inverso lungo il percorso. Questo è chiamato percorso aumentante. Quando la BFS non può più raggiungere t, il flusso corrente è ottimale.

L'uso della BFS (piuttosto che una ricerca del percorso arbitraria) trasforma Ford-Fulkerson in Edmonds-Karp, con un tempo di esecuzione garantito di O(V · E²). Garantisce inoltre la terminazione su capacità irrazionali, cosa che Ford-Fulkerson semplice non fa.

Il teorema del flusso massimo e taglio minimo

Un taglio è una partizione dei vertici in due insiemi (S, T) con s ∈ S e t ∈ T. La sua capacità è la somma delle capacità degli archi che vanno da S a T:

Il teorema del flusso massimo e taglio minimo (Ford & Fulkerson, 1956) afferma:

Questo strumento trova automaticamente il taglio minimo. Al termine di Edmonds-Karp, esegue un'ultima BFS da s sul grafico residuo; i vertici raggiunti formano S, gli altri formano T, e ogni arco che attraversa S → T nel grafico originale è saturo. Le loro capacità sommano esattamente al valore del flusso massimo — visibile nel risultato principale come "Capacità taglio minimo ✓ conferma l'ottimalità".

Funzionalità create per l'apprendimento

• Animazione passo-passo. Rivedi ogni percorso aumentante con i controlli di riproduzione, pausa e passo. Guarda quale percorso ha scelto la BFS, quale arco era il collo di bottiglia e come è cresciuto il totale corrente.
• Tre matrici sincronizzate. Passa dalla matrice delle capacità C, alla matrice del flusso finale f, alla matrice residua C − f — le tre immagini che insieme caratterizzano ogni flusso.
• Vista partizione taglio minimo. I vertici del lato S e del lato T sono elencati come chip con gli archi saturi che li attraversano evidenziati in rosso.
• Tabella arco per arco. Per ogni arco: capacità, flusso, residuo, barra di utilizzo e un indicatore di saturazione.
• Layout a strati da sinistra a destra. Il disegno del grafico è calcolato in base alle distanze BFS dalla sorgente, in modo che l'acqua "scorra" visibilmente da sinistra a destra — esattamente come viene disegnata nei libri di testo.

Formati di input

1. Elenco archi con capacità

Un arco per riga. La forma con la freccia è la più leggibile, ma funzionano diverse alternative:

Accettati anche: A, B, 10 · A B 10 · A -> B , 10. Gli archi multipli tra la stessa coppia vengono sommati.

2. Matrice di capacità

Una riga per linea, valori separati da spazi o virgole. La voce C[i][j] è la capacità dell'arco dal vertice i al vertice j. Usa 0 per "nessun arco". La matrice deve essere quadrata e la diagonale deve essere 0 (nessun auto-loop).

Inserisci le etichette dei vertici corrispondenti nel campo Etichette matrice (separate da virgola o spazio). Se omesso, le etichette predefinite sono S, A, B, …, T.

Applicazioni del flusso massimo

Esempio svolto

L'esempio rapido "Libro di testo" codifica una rete a 6 nodi con sorgente S e pozzo T. L'esecuzione di Edmonds-Karp produce quattro percorsi aumentanti:

1. S → A → B → T con collo di bottiglia 4 (l'arco A-B è il limitatore). Totale corrente: 4.
2. S → A → D → T con collo di bottiglia 6. Totale corrente: 10.
3. S → C → D → T con collo di bottiglia 4 (l'arco D-T è ora il limitatore, ne rimangono solo 4). Totale corrente: 14.
4. S → C → D → B → T con collo di bottiglia 5. Totale corrente: 19.

L'algoritmo si ferma: non esistono più percorsi aumentanti. Il taglio minimo è (S = {S, C}, T = {A, B, D, T}) con gli archi che attraversano S → A (capacità 10) e C → D (capacità 9), per un totale di 19 — esattamente il valore del flusso massimo.

Come usare questo calcolatore

1. Scegli il formato di input usando le schede — elenco archi (consigliato) o matrice di capacità.
2. Inserisci la tua rete. Puoi iniziare da un esempio rapido e modificarlo. Per l'input della matrice, fornisci anche le etichette se desideri nomi diversi da S, A, B, …, T.
3. Specifica sorgente e pozzo (o lascia vuoto per rilevare automaticamente S e T).
4. Fai clic su Calcola Flusso Massimo. La pagina dei risultati mostra il valore del flusso massimo, la partizione del taglio minimo, una visualizzazione grafica a strati, ogni percorso aumentante, una tabella di utilizzo degli archi e tre matrici (capacità, flusso, residuo).
5. Riproduci l'animazione sotto il grafico per rivedere le decisioni dell'algoritmo. Fai clic su qualsiasi passaggio del percorso aumentante per saltarvi direttamente.

Limiti

• Vertici: fino a 30 — mantiene leggibili la visualizzazione e le matrici.
• Archi: fino a 200.
• Capacità: non negative, fino a 10⁹. Sono consentite capacità frazionarie.
• Nessun auto-loop. Gli auto-loop non portano flusso in una formulazione standard di flusso massimo e vengono rifiutati.

Domande frequenti (FAQ)

Cos'è il problema del flusso massimo?

Data una rete orientata in cui ogni arco ha una capacità non negativa, il problema del flusso massimo chiede: quanto flusso può essere inviato da un vertice sorgente designato s a un vertice pozzo designato t, a condizione che il flusso su ogni arco non superi la sua capacità e che il flusso che entra in ogni vertice (diverso da sorgente e pozzo) debba essere uguale al flusso che ne esce? La risposta è chiamata valore del flusso massimo.

Cos'è il metodo Ford-Fulkerson?

Ford-Fulkerson è una tecnica generale per calcolare il flusso massimo. Trova ripetutamente un percorso aumentante dalla sorgente al pozzo nel grafico residuo e spinge quanto più flusso possibile lungo quel percorso (la capacità del collo di bottiglia), quindi aggiorna il grafico residuo. La procedura termina quando non esiste alcun percorso aumentante. Quando implementata con la ricerca in ampiezza (BFS) per la selezione del percorso, viene chiamata Edmonds-Karp e viene eseguita in tempo O(V · E²).

Cos'è il taglio minimo (min-cut) di una rete di flusso?

Un taglio è una partizione dei vertici in due insiemi S e T tali che la sorgente sia in S e il pozzo sia in T. La capacità del taglio è la somma delle capacità degli archi da S a T. Un taglio minimo è un taglio di capacità minima. Il famoso teorema del flusso massimo e taglio minimo dimostra che il valore del flusso massimo è sempre uguale alla capacità del taglio minimo.

Cos'è il grafico residuo?

Il grafico residuo tiene traccia di quanto flusso può ancora essere spinto su ogni arco. Per ogni arco originale (u, v) con capacità c e flusso corrente f, il grafico residuo contiene un arco in avanti (u, v) con capacità c meno f (capacità rimanente) e un arco inverso (v, u) con capacità f (flusso annullabile). Un percorso aumentante utilizza archi del grafico residuo, consentendo all'algoritmo di annullare decisioni precedenti.

Perché lo strumento usa la BFS per i percorsi aumentanti?

Scegliere i percorsi aumentanti con la ricerca in ampiezza (Edmonds-Karp) garantisce la terminazione in tempo polinomiale indipendentemente dalle capacità degli archi. Ford-Fulkerson semplice con una strategia di ricerca del percorso arbitraria può entrare in loop per un numero esponenziale di iterazioni su input patologici e, su capacità irrazionali, potrebbe non terminare affatto. La BFS produce anche i percorsi aumentanti più brevi, che sono più facili da leggere.

Cosa significa arco saturo?

Un arco è saturo quando il suo flusso è uguale alla sua capacità, quindi non è possibile inviare ulteriore flusso su di esso. Gli archi saturi sono i colli di bottiglia della rete e ogni taglio minimo consiste interamente di archi saturi dal lato S al lato T del taglio. Lo strumento evidenzia gli archi saturi in arancione in modo da poter vedere a colpo d'occhio la struttura del collo di bottiglia.

Ulteriori letture

• Maximum flow problem — Wikipedia (EN)
• Algoritmo di Ford–Fulkerson — Wikipedia (IT)
• Algoritmo di Edmonds–Karp — Wikipedia (IT)
• Max-flow min-cut theorem — Wikipedia (EN)