grafos:maxfluxmincut

Diferenças

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

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
Próxima revisão		 Revisão anterior
grafos:maxfluxmincut [2022/06/03 16:47] – gustavografos:maxfluxmincut [2022/06/03 17:37] (atual) – edição externa 127.0.0.1
Linha 3: Linha 3:
 <WRAP group> <WRAP group>
 <WRAP half column> <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. 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%> <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 "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.    * Interpretando como corrente de cargas num circuito elétrico, é supor o não acúmulo de cargas (Coulomb) e nenhum ponto. 
Linha 60: Linha 60:
 ===== Max flux min flow ===== ===== 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 \text{ corte} |C|$.+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.   * 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|$.    * Uma sequência est. ascendente $f_n$ de fluxos corresponde a uma sequência est. ascendente de valores $|f_n|$. 
Linha 69: Linha 69:
           * Houvesse $C'$ com $|C'|<|C|$, teríamos $|C| = |f| \leq |C'|$, 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 $.       * **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 cujas capacidades não foram usadas de } s \text{a } v\}$.+          * 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.           * 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$.               * Suponha que $v = t$.
Linha 79: Linha 79:
               * Como queríamos, essa é uma sequência de fluxos inteiros ascendentes.               * 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.               * 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$. +      * Se $t$ estivesse em $S$, poderíamos incrementar $f$, contrariando estacionamento da sequencia em $f$. 
-          * Nesse caso, $t \notin S$. +      * Nesse caso, $t \notin S$. 
-          * Note que $(S,V(G) \backslash S)$ estabelece um corte $C$. +      * 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$. +         * Se houvesse capacidade ociosa alguma aresta em $C$, contradizemos a definição de $S$. 
-              * Nesse caso, $f(e) = c(e)$ para $e \in C$. +         * Nesse caso, $f(e) = c(e)$ para $e \in C$. 
-              * Note então que $|f| = |C|$, e acabamos por $[\flat]$.+         * 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. ** Teorema (max flux min cut) : ** Seja $N = (G,s,t,c)$ uma rede.
-  * $\max_{f \text{ fluxo}} |f| = \min_{C \text{ corte} |C|$.+  * $\max_{f \text{ fluxo}} |f| = \min_{C, \, C \text{ corte}} |C|$.
   * O fluxo maximizador é inteiro.   * O fluxo maximizador é inteiro.
  
  
  • grafos/maxfluxmincut.1654285637.txt.gz
  • Última modificação: 2022/06/03 16:47
  • por gustavo