Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:maxfluxmincut [2022/06/03 15:07] – edição externa 127.0.0.1
+++ grafos:maxfluxmincut [2022/06/03 17:37] (atual) – edição externa 127.0.0.1
@@ Linha 3: / Linha 3: @@
 <WRAP group>
 <WRAP half column>
-** Resumo: ** Suponha que tenhamos, entre um reservatório de água e um grande consumidor de água, um sistema de encanamentos. Os canos (arestas) tem uma certa capacidade (em L/s) de fluxo suportada. No que segue, vamos argumentar que o maior fluxo possível, da fonte para o consumidor, corresponde a menor capacidade conjunta de um conjunto de canos que corresponde a um corte do grafo, com a fonte em uma partição e o consumidor em outra. A notação será inspirada por mecânica dos fluidos, //just for fun//.
+** Resumo: ** Suponha que tenhamos, entre um reservatório de água e um grande consumidor de água, um sistema de encanamentos. Os canos (arestas) tem uma certa capacidade (em L/s) de fluxo suportada. No que segue, vamos argumentar que o maior fluxo possível, da fonte para o consumidor, corresponde a menor capacidade conjunta de um conjunto de canos que corresponde a um corte do grafo, com a fonte em uma partição e o consumidor em outra. A notação será motivada pelo [[http://en.wikipedia.org/wiki/Divergence_theorem|Teorema da divergência]].
 Para tornar o que dissemos acima preciso, precisamos fixar algumas definições, e o domínio de discurso.
@@ Linha 21: / Linha 21: @@
 <WRAP center round tip 90%>
-  * Interpretando $f$ como "kg de fluido por segundo atravessando uma seção transversal do cano", podemos interpretar o segundo axioma como a lei de preservação de massa, pois \nabla \cdot f(x)$ seria menos a taxa de acúmulo de massa em um vértice.
+  * Interpretando $f$ como "kg de fluido por segundo atravessando uma seção transversal do cano", podemos interpretar o segundo axioma como a lei de preservação de massa, pois $\nabla \cdot f(x)$ seria menos a taxa de acúmulo de massa em um vértice.
   * Interpretando como "litros por segundo", o segundo axioma é análogo a supor incompressibilidade do fluido.
   * Interpretando como corrente de cargas num circuito elétrico, é supor o não acúmulo de cargas (Coulomb) e nenhum ponto.
@@ Linha 27: / Linha 27: @@
 </WRAP>
-==== Max flow min cut ====
+===== Fluxo =====
 No que segue, assumiremos $H = \mathbb{N}$ e vamos definir uma rede e seus fluxo associados.
+<WRAP group>
+<WRAP half column>
 **Definição: ** Uma **rede** $N \doteq (H,s,t,c)$ consiste nas seguintes informações:
@@ Linha 36: / Linha 38: @@
   * Um sorvedouro/consumidor $t$.
   * Uma função de capacidade $c:E \to \mathbb{N}$, $c(e) = c(-e)$ (a capacidade é a mesma em ambas as direções).
+</WRAP>
-Uma **fluxo** nessa rede é uma circulação $f:E \to \R$ tal que:
+<WRAP half column>
+Uma **fluxo** nessa rede é uma circulação $f:E \to \mathbb{R}$ tal que:
   * (i) Pode violar a conservação de massa na fonte e no sorvedouro.
   * (ii) Deve respeitar a "capacidade dos canos": $f(e) \leq c(e)$.
   * (iii) Dizemos que $f$ é fluxo inteiro se $f(e) \in \mathbb{Z}$.
+</WRAP>
+</WRAP>
 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$.
@@ Linha 46: / Linha 51: @@
   * 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, $\nabla \cdot f(S)$ é 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.
+    * 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 **fluxo associado ao corte $C$**.
+    * 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: ** Todo corte tem o mesmo fluxo.
+        * 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 (($f \leq g$ quando $f(e) \leq g(e)$ pra todo $e$.)) 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 ((delete ciclos.)) assumir que o $(s,v)$-passeio $(e_1,...,e_p)$ é um caminho.
+              * Suponha que $v = t$.
+              * Considere $\epsilon>0$ a menor capacidade ociosa ((A capacidade ociosa de $e$ na direção de $x$ para $y$ é $c(e) - f(e)$ se $e$ está orientado corretamente, ou $c(e) + f(e)$ se estiver orientado reversamente.)) 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.
-A