Max flux min cut

Fluxo

No que segue, assumiremos $H = \mathbb{N}$ e vamos definir uma rede e seus fluxo associados.

No que segue, vamos considerar apenas cortes $C$, conjuntos de arestas que separam a partição de vértices $(S,V(G) \backslash S \doteq T)$ com $s \in S$ e $t \in T$.

• Podemos estender $\nabla \cdot f$ para subconjuntos de vértices $S \subset V$, e essa quantidade ($\int_S \nabla \cdot f \doteq \sum_{s \in S}\nabla \cdot f $) deve ser interpretada como “quantidade de fluido sendo introduzido via $S$ para o sistema”.
• Note que no cálculo $\int_S\nabla \cdot f$, incrementos de arestas $e$ cujas extremidades estão em $S$ se cancelam.
  • Ou seja, $\int_S \nabla \cdot f$ é a soma de $f(e)$, tal que $e$ é aresta entre $x \in S$ e $y \in V(G) \backslash S$, com $e$ orientado como $[x,y]$, ou seja, é a quatidade de fluido que $S$ fornece para o resto do sistema.
  • Esse valor é na verdade associado ao corte $C \doteq \partial S$ e seu complementar : \[\int_{\partial S}f \cdot \hat{n} \doteq \sum_{ e \in C, \, e \text{ orientado de } S \text{ para fora de } S}f(e).\]
  • Chamamos esse valor de $|f|_C$ associado ao corte $C$.
    • Se $f$ é conservativa em todo vértice de $S$, $\int_S \nabla \cdot f \doteq \sum_{s \in S}\nabla \cdot f(s) = 0 $.
    • Nesse caso, o fluxo de $C$ é \[\nabla \cdot f (s) + \underbrace{\int_{S \backslash \{s\}} \nabla \cdot f}_{0, \text{ pois $f$ é conservativo nesse subconjunto.} }\]
    • Mostramos a Proposição: Seja $f$ fluxo qualquer, então $|f|_C = \nabla\cdot f(s) \doteq |f|$ para qualquer corte $C$.

Max flux min flow

Fixada uma rede então, é natural perguntarmos qual é a maior quantidade $|f|$ que uma rede $N$ consegue transportar de sua fonte para seu sorvedouro. Seja $C$ um corte, e $|C|$ a soma das capacidades de sua aresta. Está claro que $|f| \leq |C|$. Nesse caso, $\max_{f \text{ fluxo}} |f| \leq \min_{C, \, C \text{ corte}} |C|$.

• Considere a ordem $\leq$ natural ²⁾ sobre os fluxos integrais.
• Uma sequência est. ascendente $f_n$ de fluxos corresponde a uma sequência est. ascendente de valores $|f_n|$.
  • Estas são superiormente limitadas pelas capacidades dos cortes, logo a sequência estaciona.
  • Suponha que ela estaciona em $f$ que não pode ser incrementada de $1$ em nenhuma aresta.
  • Afirmação $[\flat]$: Se encontrarmos $C$ corte com $|f| = |C|$ acabamos
    • De fato, não pode haver $f'$ fluxo com $|f'| > |f|$, pois $|f'| \leq |C| = |f|$, absurdo.
    • Houvesse $C'$ com $|C'|<|C|$, teríamos $|C| = |f| \leq |C'|$, absurdo.
  • Construção da sequência: Começamos com $ f_0 \equiv 0 $.
    • Definido $f_k$, considere \[S_k \doteq \{v \in V(G) \, : \, \text{existe um caminho de arestas com capacidade ociosa positiva na direção de } s \text{ a } v\}.\]
    • Para cada $v \in S_k$, podemos ³⁾ assumir que o $(s,v)$-passeio $(e_1,\ldots,e_p)$ é um caminho.
      • Suponha que $v = t$.
      • Considere $\epsilon>0$ a menor capacidade ociosa ⁴⁾ de todas as arestas deste caminho, no sentido $s$ para $t$.
      • Este é um número inteiro, pois $c$ é inteiro e $f_k$ é assumido inteiro por hipótese de indução.
      • Para cada $e_i$ nesse caminho, faça $f_{k+1}(e_i) = f_k(e_i) + \epsilon$, e mantenha o valor da $f$ em outras arestas.
      • Este ainda é um fluxo inteiro.
      • Note que, como assumimos que este é um caminho, $|f_{k+1}| = \nabla \cdot f_{k+1}(s) = \nabla \cdot f_{k}(s) + \epsilon = |f_k|+\epsilon$.
      • Como queríamos, essa é uma sequência de fluxos inteiros ascendentes.
      • Essa sequência estaciona em $f_n \doteq f$, com componente $S_n \doteq S$ associada.
  • Se $t$ estivesse em $S$, poderíamos incrementar $f$, contrariando estacionamento da sequencia em $f$.
  • Nesse caso, $t \notin S$.
  • Note que $(S,V(G) \backslash S)$ estabelece um corte $C$.
    • Se houvesse capacidade ociosa alguma aresta em $C$, contradizemos a definição de $S$.
    • Nesse caso, $f(e) = c(e)$ para $e \in C$.
    • Note então que $|f| = |C|$, e acabamos por $[\flat]$.

Mostramos então o

Teorema (max flux min cut) : Seja $N = (G,s,t,c)$ uma rede.

• $\max_{f \text{ fluxo}} |f| = \min_{C, \, C \text{ corte}} |C|$.
• O fluxo maximizador é inteiro.