Calcolatore di Flusso in Rete (Flusso Massimo)

Calcola il flusso massimo da una sorgente a un pozzo in una rete orientata capacitata utilizzando il metodo Ford-Fulkerson (Edmonds-Karp). Anima ogni percorso aumentante, mostra le capacità residue, gli archi saturi e la partizione del taglio minimo (min-cut) che ne dimostra l'ottimalità.

Esempi rapidi:

Libro di testo (6 nodi) Rete piccola Classico CLRS Bipartito Input matrice

↦ Elenco archi con capacità ▦ Matrice di capacità

Dati della rete

Formato archi: A -> B : 10 (freccia più capacità), o A, B, 10. Formato matrice: una riga per linea, C[i][j] è la capacità dell'arco i → j (usa 0 per nessun arco). La diagonale deve essere 0.

Etichette matrice (opzionale)

Etichette separate da virgola o spazio, una per riga della matrice. Predefinito: S, A, B, …, T.

Vertice sorgente (source) ⭘

Vertice pozzo (sink) ⬤

Embed Calcolatore di Flusso in Rete (Flusso Massimo) Widget

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:

Capacità: 0 ≤ f(u, v) ≤ c(u, v) per ogni arco (u, v) Conservazione: Σ f(w, v) = Σ f(v, w) per ogni v ∈ V \ {s, t} Valore flusso: |f| = Σ f(s, w) − Σ f(w, s) (flusso netto in uscita da s)

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.

finché esiste un percorso aumentante P da s a t nel grafico residuo: b ← min c_residuo(u, v) per gli archi (u, v) in P spingi b unità di flusso lungo P // aggiorna residuo + flusso restituisci flusso totale |f|

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:

cap(S, T) = Σ c(u, v) per u ∈ S, v ∈ T

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

valore del flusso massimo = capacità del taglio minimo

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:

S -> A : 10 S -> B : 13 A -> B : 10 B -> A : 4 B -> T : 14

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).

S A B C D T S [ 0 10 0 10 0 0 ] A [ 0 0 4 2 8 0 ] B [ 0 0 0 0 0 10 ] C [ 0 0 0 0 9 0 ] D [ 0 0 6 0 0 10 ] T [ 0 0 0 0 0 0 ]

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

Dominio	Come viene utilizzato il flusso massimo
Trasporti e logistica	Quanto carico può spostare una rete ferroviaria/stradale/oleodotto al giorno dall'origine a destinazione?
Matching bipartito	Assegnazione di lavori ai lavoratori, studenti ai progetti. Il flusso massimo con capacità unitaria fornisce il matching massimo.
Segmentazione delle immagini	Il min-cut di Boykov-Kolmogorov nella computer vision separa i pixel del primo piano dallo sfondo.
Affidabilità della rete	Il taglio minimo identifica gli anelli più deboli il cui guasto disconnette la rete.
Programmazione dei progetti	Problemi di chiusura e di selezione si riducono al taglio minimo.
Eliminazione nel baseball	Determina se una squadra è matematicamente eliminata dal titolo di un campionato.

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:

S → A → B → T con collo di bottiglia 4 (l'arco A-B è il limitatore). Totale corrente: 4.
S → A → D → T con collo di bottiglia 6. Totale corrente: 10.
S → C → D → T con collo di bottiglia 4 (l'arco D-T è ora il limitatore, ne rimangono solo 4). Totale corrente: 14.
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

Scegli il formato di input usando le schede — elenco archi (consigliato) o matrice di capacità.
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.
Specifica sorgente e pozzo (o lascia vuoto per rilevare automaticamente S e T).
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).
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

Cita questo contenuto, pagina o strumento come:

"Calcolatore di Flusso in Rete (Flusso Massimo)" su https://MiniWebtool.com/it/calcolatore-di-flusso-in-rete-flusso-massimo/ di MiniWebtool, https://MiniWebtool.com/

dal team di miniwebtool. Aggiornato: 22 apr 2026

Puoi anche provare il nostro Risolutore di Matematica AI GPT per risolvere i tuoi problemi matematici attraverso domande e risposte in linguaggio naturale.

Calcolatore di Flusso in Rete (Flusso Massimo)

Calcolatore di Flusso in Rete (Flusso Massimo)

Cos'è il problema del flusso massimo?

Come funziona l'algoritmo — Ford-Fulkerson con BFS

Il teorema del flusso massimo e taglio minimo

Funzionalità create per l'apprendimento

Formati di input

1. Elenco archi con capacità

2. Matrice di capacità

Applicazioni del flusso massimo

Esempio svolto

Come usare questo calcolatore

Limiti

Domande frequenti (FAQ)

Cos'è il problema del flusso massimo?

Cos'è il metodo Ford-Fulkerson?

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

Cos'è il grafico residuo?

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

Cosa significa arco saturo?

Ulteriori letture

Operazioni matematiche avanzate:

Strumenti in primo piano: