Diferenças
Aqui você vê as diferenças entre duas revisões dessa página.
| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
| grafos:maxfluxmincut [2022/06/03 15:18] – gustavo | grafos: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, | + | ** 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, | Para tornar o que dissemos acima preciso, precisamos fixar algumas definições, | ||
| 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 " | * Interpretando como " | ||
| * 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 51: | 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 " | * 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 " | ||
| * Note que no cálculo $\int_S\nabla \cdot f$, incrementos de arestas $e$ cujas extremidades estão em $S$ se cancelam. | * 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 |
| * 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).\] | * 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$**. | * Chamamos esse valor de **$|f|_C$ associado ao corte $C$**. | ||
| 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|$. Queremos mostrar | + | 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 | ||
| + | * ** 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' | ||
| + | * **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, | ||
| + | * Suponha que $v = t$. | ||
| + | * Considere $\epsilon> | ||
| + | * 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. | ** 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. | ||