Caio

Teorema Fluxo-Máximo Corte-Mínimo
Descrição do Problema
O Teorema de Fluxo-Máximo Corte-Mínimo de Ford-Fulkerson surgiu no início da década de 50, durante a guerra fria, com base na seguinte formulação de T. E Harris: “Considere uma rede ferroviária conectando duas cidades através de um número de cidades intermediárias, onde cada ligação entre cada cidade tenha associado um valor de capacidade de transporte. Encontre um fluxo máximo de uma dada cidade até outra”. E, assim, através dessa formulação, Ford-Fulkerson descobriu o corte-mínimo da malha ferroviária poderia minimizar os esforços da força armada dos Estados Unidos para desabastecer à região, no caso de um possível embate com o exército vermelho.
Para entendermos o teorema fluxo-máximo corte-mínimo, é preciso entender o que é um fluxo em rede, que por sua vez, é definido como o envio de um nó (origem) até outro nó (destino), percorrendo alguns arcos da rede onde aqueles nós fazem parte.
As redes de fluxo apresentam grafos direcionados, e arestas que possuem “capacidade” (quantidade de fluxo máximo que pode passar pela aresta). Além disso, possuem 3 tipos de vértices, o de origem (onde fluxo entra), o interno (onde fluxo passa) e o de destino (onde fluxo sai). Um fluxo em rede G=(V,E) é um grafo orientado em que cada aresta (u,v)∈ E e tem uma capacidade não negativa c(u,v) ≥ 0. Onde u equivale à origem e v o destino. Em uma rede G=(V,E), cada vértice reside em algum caminho de u até v.
O fluxo em rede deve respeitar as três propriedades seguintes:
Restrição de Capacidade: o fluxo em cada aresta não deve ultrapassar sua capacidade.
F(u,v) ≤ c(u,v) para todo par de vértices (u,v).
Anti-simetria oblíquoa: o fluxo em uma direção deve ser igual ao seu fluxo na direção oposta. Essa propriedade é válida para grafos não orientados. f(u,v)=-f(u,v) Conservação do fluxo: O fluxo que entra deve ser igual ao que sai, exceto na origem e no sorvedouro. E o fluxo que sai da origem deve ser igual ao que