Aplicações de Fluxo e Cortes

1. O Teorema Max-Flow Min-Cut

Imagine que você quer interromper o tráfego entre duas cidades \(S\) e \(T\) explodindo pontes. Cada ponte tem um “custo de destruição” (que é igual à sua capacidade). O Teorema Max-Flow Min-Cut diz algo surpreendente: > “A soma mínima dos custos das pontes que precisam ser destruídas para separar \(S\) de \(T\) é exatamente igual ao fluxo máximo que consegue passar de \(S\) a \(T\).”

Isso transforma problemas de “separação” em problemas de “fluxo”.

2. Aplicação: Segmentação de Imagem (Photoshop)

Como o computador sabe separar o “Gato” (Frente) do “Fundo” automaticamente?

Modele a imagem como um grafo onde cada Pixel é um vértice.
Crie uma Fonte \(S\) (representando o Objeto) e um Sorvedouro \(T\) (representando o Fundo).
Conecte \(S\) aos pixels que paraceem gato (alta probabilidade).
Conecte \(T\) aos pixels que parecem fundo.
Conecte pixels vizinhos entre si com arestas de alta capacidade (pois vizinhos tendem a ser do mesmo objeto).
Rode o Max-Flow.
O Min-Cut dessas arestas vai cortar exatamente onde a diferença de cor é maior (bordas), separando o objeto do fundo com custo mínimo.

3. Aplicação: Problema da Seleção de Projetos

Você tem uma lista de Projetos possíveis e Requisitos. - Cada Projeto dá um Lucro. - Cada Projeto depende de Ferramentas (ou steps) que têm Custo para comprar. - Se fizer o projeto A, precisa comprar a ferramenta X. - Objetivo: Escolher projetos/ferramentas para maximizar o Lucro Líquido (Lucro - Custo).

Modelagem como Grafo (Min-Cut): 1. Crie Fonte \(S\) e Sorvedouro \(T\). 2. Uma aresta de \(S\) para cada Projeto com capacidade = Lucro. 3. Uma aresta de cada Ferramenta para \(T\) com capacidade = Custo. 4. Arestas de Projeto \(\to\) Ferramenta Necessária com capacidade \(\infty\). 5. Calcule o Min-Cut \((S, T)\). 6. O Corte Mínimo representa o menor prejuízo possível (projetos não realizados + ferramentas pagas). 7. Lucro Máximo = (Soma de todos os lucros possíveis) - (Min-Cut).