Rete di flusso

Nella teoria dei grafi, una rete di flusso è un grafo orientato in cui ogni arco ha una capacità non negativa ed è attraversato da un flusso, ovvero un numero compreso fra 0 e la capacità dell'arco.

Le reti di flusso sono un'importante sezione della teoria dei grafi perché possono essere usate per modellare molte situazioni reali: si pensi ad esempio ad una rete stradale ed il relativo flusso di veicoli, o una rete idrica. Più in generale, ogni sistema che comprende il passaggio di qualcosa attraverso canali di capacità limitata e interconnessi fra loro, può essere rappresentato utilizzando una rete di flusso.

Definizione formale

Si dice rete un grafo $G=(V,E)$ a cui è associata una funzione $c:V^{2}\to \mathbb {R} _{\infty }$ , detta funzione capacità. Senza perdita di generalità, assumiamo che se $(u,v)\in E$ , allora anche $(v,u)\in E$ , dal momento che se $(v,u)\not \in E$ allora $(v,u)$ può essere aggiunto ad E e poi imporre $c(v,u)=0$ .

Dati due nodi s e t di G distinti, detti rispettivamente sorgente e pozzo, allora $(G,c,s,t)$ è detta rete di flusso.^[1]

Ad ogni nodo $v\in V$ viene associato un coefficiente $b_{v}$ , che indica se $v$ genera o assorbe del flusso.^[2] Nel primo caso il coefficiente sarà positivo e verrà chiamato domanda del nodo; nel secondo caso il coefficiente sarà negativo e verrà chiamato offerta del nodo. Se $b_{v}$ è nullo, $v$ è detto nodo di trasferimento.^[2] Nel caso si dovesse modellare una rete di flusso con più sorgenti, è prassi comune creare una supersorgente, ovvero una nuova sorgente con archi di capacità infinita che la collegano a tutte le altre sorgenti. Così facendo le precedenti sorgenti diventano nodi "comuni", e ci si ritrova al caso con un'unica sorgente, senza variare il sistema poiché un flusso nella nuova rete corrisponde ad uno nell'originale. Un costrutto simile è utilizzato nel caso di più pozzi, con l'introduzione di un superpozzo.

Flussi

Esistono vari tipi di funzione di flusso definibili in una rete di flusso. Le funzioni di flusso associano un numero a ciascuna coppia di nodi.

L'esempio basilare di una funzione di flusso è noto come pseudoflusso. Uno pseudoflusso è una funzione $f:V^{2}\to \mathbb {R}$ che soddisfa i due seguenti vincoli:^[2]

Vincolo sulla capacità.

f(u,v)\leq c(u,v)\forall u,v\in V

. Il flusso lungo un arco non può eccedere la capacità dello stesso.

Emisimmetria. Il flusso lungo un arco

k=(u,v)

deve essere di segno opposto se k viene attraversato da v a u.

f(u,v)=-f(v,u)\forall u,v\in V

.

Partendo dalla definizione di pseudoflusso, si possono aggiungere ulteriori vincoli per ottenere tipi di flusso più specifici. Un flusso ammissibile^[2] (denotabile semplicemente come "flusso") deve soddisfare la seguente regola:

Conservazione del flusso.

\sum _{v\in V}f(v,u)=\sum _{v\in V}f(u,v),\quad \forall u\in V\setminus \{s,t\}

. Per ogni nodo il flusso entrante deve eguagliare quello uscente.^[2]

Concetti utili per i problemi di flusso

Grafo residuo

Dato un flusso $x$ ammissibile, il grafo residuo (relativo a $x$ ) è un grafo $G(x)=(V,E(x))$ con gli stessi nodi del grafo $G,$ mentre gli archi e le loro capacità $r_{ij},$ dette residue, sono così definiti:

{\begin{aligned}(i,j)&\in E,\quad x_{ij}<u_{ij}\;\Longrightarrow (i,j)\in E(x),\quad r_{ij}=u_{ij}-x_{ij}\\(i,j)&\in E,\quad x_{ij}>0\quad \Longrightarrow (j,i)\in E(x),\quad r_{ji}=x_{ij}\end{aligned}}

Cammino aumentante

Dato un flusso $x$ ammissibile, un cammino aumentante (rispetto a $x$ ) è un cammino orientato da $s$ a $t$ nel grafo residuo $G(x)$ , dove $s$ è il nodo origine (o sorgente) e $t$ è il nodo destinazione (o pozzo).

Applicazioni

Le reti di flusso hanno svariate applicazioni pratiche, poiché consentono di rappresentare con un modello matematico relativamente semplice situazioni reali. Il problema più frequentemente associato alle reti di flusso è quello del flusso massimo, ovvero trovare il valore massimo di flusso che può essere "generato" dalla sorgente ed arrivare al pozzo senza che si superino le capacità dei singoli archi. Il problema può essere risolto in maniera efficiente con l'algoritmo di Ford-Fulkerson. Un altro problema tipico di questo argomento è quello del flusso di costo minimo.

Note

^ (EN) A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989
^ ^a ^b ^c ^d ^e Domenico Cantone, Grafi e reti di flusso (PDF), su dmi.unict.it, Università di Catania, Dipartimento di Matematica e Informatica. URL consultato il 30 agosto 2016 (archiviato il 30 agosto 2016).

Bibliografia

Passacantando M. ; Pappalardo M. (2013). "Ricerca Operativa" Pisa University Press ISBN 9788867410736

Altri progetti

Wikimedia Commons contiene immagini o altri file su rete di flusso

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] (EN) A.V. Goldberg, É. Tardos and R.E. Tarjan, Network flow algorithms, Tech. Report STAN-CS-89-1252, Stanford University CS Dept., 1989

[cantone-2] Domenico Cantone, Grafi e reti di flusso (PDF), su dmi.unict.it, Università di Catania, Dipartimento di Matematica e Informatica. URL consultato il 30 agosto 2016 (archiviato il 30 agosto 2016).

[1]

[2]