Muitos problemas da ciência da computação podem ser representados por um gráfico que consiste em nós e links entre eles. Exemplos são problemas de fluxo de rede, que envolvem o transporte de bens ou material em uma rede, como um sistema ferroviário.
É possível representar um fluxo de rede por um gráfico com nós que são cidades e cujos arcos são linhas ferroviárias entre eles. Elas são chamadas de fluxos porque as propriedades delas são semelhantes às da água que flui por uma rede de tubulações.
Uma restrição importante nos fluxos de rede é que cada arco tem uma capacidade, o valor máximo que pode ser transportado pelo arco em um período fixo.
O problema de fluxo máximo é determinar a quantidade total máxima que pode ser transportada em todos os arcos na rede, sujeita às restrições de capacidade.
A primeira pessoa a estudar esse problema foi o matemático russo Tolstoi, na década de 1930. O mapa abaixo mostra a rede ferroviária real em que ele quer encontrar o fluxo máximo.
A OR-Tools oferece vários solucionadores de problemas de fluxo de rede nas bibliotecas graph.
As seções a seguir apresentam exemplos de problemas de fluxo de rede e mostram como resolvê-los: