Fluxos de rede
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:
Exceto em caso de indicação contrária, o conteúdo desta página é licenciado de acordo com a Licença de atribuição 4.0 do Creative Commons, e as amostras de código são licenciadas de acordo com a Licença Apache 2.0. Para mais detalhes, consulte as políticas do site do Google Developers. Java é uma marca registrada da Oracle e/ou afiliadas.
Última atualização 2024-08-09 UTC.
[null,null,["Última atualização 2024-08-09 UTC."],[[["Network flow problems, like transporting goods across a railway system, can be represented by graphs with nodes and links, where links have capacity limits."],["The maximum flow problem aims to find the maximum transportable amount across a network, respecting capacity constraints."],["OR-Tools offers various solvers in its graph libraries to address network flow problems like maximum flows and minimum cost flows."],["Example applications of network flows include assignments with individual workers or teams, solvable using OR-Tools."]]],["Computer science utilizes graphs to model problems like network flow, where goods are transported across a network (e.g., railway). Each link (arc) in the network has a capacity, limiting transport volume. The maximum flow problem determines the highest total transport volume across all arcs, respecting these capacity constraints. This problem, first studied by A.N. Tolstoi, can be solved using solvers from the OR-Tools graph libraries, which are useful for problems such as maximum flows, minimum cost flows, and assignment problems.\n"]]
