Dal 2010 · Oltre 2 milioni di utilizzi degli strumenti ogni mese
Dal 2010
Aggiungi a Chrome

La Mia Cassetta Degli Attrezzi

Modalità Automatica

Nessuno strumento salvato.

Aggiorna alla Versione Premium
Strumenti correlati
Calcolatore di Ordinamento TopologicoEstrattore di numeri
Pagina Iniziale > Matematica > Operazioni matematiche avanzate
 

Calcolatore di Flusso in Rete (Flusso Massimo)

Calcola il flusso massimo da sorgente a pozzo in una rete diretta con capacità usando Ford-Fulkerson con Edmonds-Karp. Anima ogni cammino di aumento e mostra capacità residue, archi saturi e il taglio minimo dimostrante.

Utilizzo gratuitoSenza registrazioneRisultati istantanei
Calcolatore di Flusso in Rete (Flusso Massimo)Provalo ora — gratis ▼
Esempi rapidi:
Libro di testo (6 nodi) Rete piccola Classico CLRS Bipartito Input matrice
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 separate da virgola o spazio, una per riga della matrice. Predefinito: S, A, B, …, T.

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:

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

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

DominioCome viene utilizzato il flusso massimo
Trasporti e logisticaQuanto carico può spostare una rete ferroviaria/stradale/oleodotto al giorno dall'origine a destinazione?
Matching bipartitoAssegnazione di lavori ai lavoratori, studenti ai progetti. Il flusso massimo con capacità unitaria fornisce il matching massimo.
Segmentazione delle immaginiIl min-cut di Boykov-Kolmogorov nella computer vision separa i pixel del primo piano dallo sfondo.
Affidabilità della reteIl taglio minimo identifica gli anelli più deboli il cui guasto disconnette la rete.
Programmazione dei progettiProblemi di chiusura e di selezione si riducono al taglio minimo.
Eliminazione nel baseballDetermina 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:

  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

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.

Operazioni matematiche avanzate:

Strumenti popolari e aggiornati:

Calcolatore della frequenza cardiaca massimaCalcolatore di Una Ripetizione Massima (1RM)Calcolatore del margine del flusso di cassaVedi tutti →
Pagina Iniziale > Matematica > Operazioni matematiche avanzate > Calcolatore di Flusso in Rete (Flusso Massimo)