Molti problemi dell'informatica possono essere rappresentati da un grafico composto da nodi e link tra loro. Alcuni esempi sono i problemi di flusso della rete, che riguardano il trasporto di beni o materiali attraverso una rete, ad esempio un sistema ferroviario.
Puoi rappresentare un flusso di rete da un grafico i cui nodi sono città e i cui archi sono linee ferroviarie tra loro. Sono chiamati flussi perché le loro proprietà sono simili a quelle dell'acqua che scorre attraverso una rete di tubi.
Un vincolo chiave nei flussi di rete è che ogni arco ha una capacità: la quantità massima che può essere trasferita attraverso l'arco in un periodo di tempo prestabilito.
Il problema massimo di flusso è determinare la quantità totale massima che può essere trasportata su tutti gli archi della rete, in base ai vincoli di capacità.
La prima persona a studiare questo problema è stata la matematica russa A.N. Tolstoj, negli anni '30. La mappa seguente mostra la rete ferroviaria effettiva di cui desidera trovare un flusso massimo.
OR-Tools fornisce diversi risolutori per i problemi dei flussi di rete nelle sue librerie graph.
Le seguenti sezioni presentano alcuni esempi di problemi di flusso di rete e mostrano come risolverli: