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)

Altri strumenti correlati:

Operazioni matematiche avanzate:

• Calcolatore di Antilogaritmo
• Calcolatore di funzione Beta
• Calcolatore del Coefficiente Binomiale
• Calcolatrice di distribuzione binomiale
• Calcolatore Bitwise
• Calcolatore del Teorema Centrale del Limite
• Calcolatore di combinazione
• Calcolatore di Funzione di Errore Complementare
• Calcolatrice di Numeri Complessi
• Calcolatore di Entropia
• Calcolatore della funzione di errore
• Calcolatore di decadimento esponenziale
• Calcolatore della crescita esponenziale
• Calcolatore dell'Integrale Esponenziale
• calcolatore-di-esponenti-alta-precisione
• Calcolatrice del Fattoriale
• Calcolatore della Funzione Gamma
• Calcolatore del Rapporto Aureo
• Calcolatore del tempo di dimezzamento
• Calcolatore del Tasso di Crescita Percentuale
• Calcolatore di Permutazione
• Calcolatrice della Distribuzione di Poisson
• Calcolatrice delle Radici dei Polinomi con Passaggi Dettagliati
• Calcolatrice delle probabilità
• Calcolatrice di Distribuzione di Probabilità
• Calcolatore di Proporzioni
• Calcolatore di formula quadratica
• Calcolatrice Scientifica
• Calcolatore di notazioni scientifiche
• Calcolatore di Cifre Significative Nuovo
• Calcolatore di Somme di Cubi
• Calcolatore di somme di numeri interi positivi
• Calcolatore di Somme di Quadrati
• Generatore di Tabella di Verità
• Calcolatore di Teoria degli Insiemi
• Generatore di Diagramma di Venn (3 Insiemi)
• Calcolatore del Teorema Cinese del Resto
• Calcolatore della Funzione Toziente di Eulero
• Calcolatore dell'Algoritmo Euclideo Esteso
• Calcolatore dell'Inverso Moltiplicativo Modulare
• Calcolatore di Frazioni Continue
• Calcolatore del Percorso più Breve di Dijkstra
• Calcolatore dell'Albero Ricoprente Minimo
• Validatore di Sequenza di Gradi di Grafo
• Calcolatore di Derangement (Sottofattoriale)
• Calcolatore di Numeri di Stirling
• Calcolatore del Principio dei Cassetti
• Calcolatore Distribuzione Stazionaria Catena di Markov
• Calcolatore di Arrotondamento Nuovo
• Calcolatore Distribuzione Binomiale Negativa Nuovo
• Calcolatore Permutazioni con Ripetizione Nuovo
• Calcolatore Esponenziazione Modulare Nuovo
• Calcolatore Radice Primitiva
• Semplificatore di Algebra Booleana Nuovo
• Risolutore di Mappa di Karnaugh (K-Map) Nuovo
• Calcolatore di Colorazione di Grafi Nuovo
• Calcolatore di Ordinamento Topologico Nuovo
• Calcolatore di Matrice di Adiacenza Nuovo
• Calcolatore Inclusione-Esclusione Nuovo
• Risolutore di Programmazione Lineare Nuovo
• Risolutore del Commesso Viaggiatore (TSP) Nuovo
• Verificatore di Cammino Hamiltoniano Nuovo
• Verificatore di Grafo Planare Nuovo
• Calcolatore di Flusso in Rete (Flusso Massimo) Nuovo
• Risolutore del Problema del Matrimonio Stabile Nuovo
• Calcolatore Ordine Teoria dei Gruppi Nuovo
• Calcolatore di Anelli e Campi Nuovo