Os problemas de fluxo maximo associão-se a que?

Uma grafo capacitado é um grafo com números positivos associados aos arcos.  O número associado a um arco é conhecido como capacidade do arco.  A capacidade de um arco v-w será denotada por c_vw.  Suporemos sempre que todas as capacidades são inteiras.

(Um grafo capacitado é, portanto, o caso especial de grafo com custos nos arcos em que os custos são todos positivos e a palavra capacidade é usada no lugar de custo.)  Um grafo capacitado com vértice inicial e vértice final é às vezes chamado rede (= network).

Suponha que f é um fluxo num grafo capacitado com vértice inicial e vértice final.  Dizemos que f respeita as capacidades se   f_vw  ≤  c_vw  para cada arco v-w, sendo f_vw o fluxo no arco v-w e c_vw a capacidade do arco.

Na teoria da otimização, os problemas de fluxo máximo envolvem encontrar um fluxo viável por meio de uma rede de fluxo de fonte única e dissipador único que seja máxima. O problema do fluxo máximo pode ser visto como um caso especial de problemas de fluxo de rede mais complexos, como o problema de circulação. O valor máximo de um escoamento de st (isto é, fluxo da fonte s para afundar t) é igual à capacidade mínima de um corte em st (isto é, corte de corte s de t) na rede, como declarado no minuto de fluxo máximo. Teorema de corte.

Enquanto houver um caminho aberto através do gráfico residual, envie o mínimo das capacidades residuais no caminho. O algoritmo só é garantido para terminar se todos os pesos são racionais. Caso contrário, é possível que o algoritmo não converge para o valor máximo. No entanto, se o algoritmo terminar, é garantido que encontre o valor máximo.

O algoritmo de reclassificação de push mantém um pré-fluxo, ou seja, uma função de fluxo com a possibilidade de excesso nos vértices. O algoritmo é executado enquanto há um vértice com excesso positivo, ou seja, um vértice ativo no gráfico. A operação de empurrar aumenta o fluxo em uma borda residual, e uma função de altura nos vértices controla quais arestas residuais podem ser empurradas. A função de altura é alterada com uma operação de reclassificação. As definições adequadas dessas operações garantem que a função de fluxo resultante seja um fluxo máximo.

Na teoria da otimização, os problemas de fluxo máximo envolvem encontrar um fluxo viável por meio de uma rede de fluxo de fonte única e dissipador único que seja máxima. O problema do fluxo máximo pode ser visto como um caso especial de problemas de fluxo de rede mais complexos, como o problema de circulação. O valor máximo de um escoamento de st (isto é, fluxo da fonte s para afundar t) é igual à capacidade mínima de um corte em st (isto é, corte de corte s de t) na rede, como declarado no minuto de fluxo máximo. Teorema de corte.

Enquanto houver um caminho aberto através do gráfico residual, envie o mínimo das capacidades residuais no caminho. O algoritmo só é garantido para terminar se todos os pesos são racionais. Caso contrário, é possível que o algoritmo não converge para o valor máximo. No entanto, se o algoritmo terminar, é garantido que encontre o valor máximo.

O algoritmo de reclassificação de push mantém um pré-fluxo, ou seja, uma função de fluxo com a possibilidade de excesso nos vértices. O algoritmo é executado enquanto há um vértice com excesso positivo, ou seja, um vértice ativo no gráfico. A operação de empurrar aumenta o fluxo em uma borda residual, e uma função de altura nos vértices controla quais arestas residuais podem ser empurradas. A função de altura é alterada com uma operação de reclassificação. As definições adequadas dessas operações garantem que a função de fluxo resultante seja um fluxo máximo.