Essa é uma revisão anterior do documento!
Max flux min cut
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.
Para tornar o que dissemos acima preciso, precisamos fixar algumas definições, e o domínio de discurso.
- Vamos tratar de digrafos não necessariamente simples, ou seja:
- As arestas $e \in E(G)$ entre vértices $x$ e $y$ nascem com uma orientação, $[x,y]$ ou $[y,x]$.
- Entre dois vértices, podemos ter mais de uma aresta orientada.
- Para cada aresta $e$, está bem definido $-e$ a mesma aresta, considerada agora com a orientação inversa.
- Considere $E \doteq \{e,-e \, : \, e \in E(G)\}$.
Definição: Uma circulação 1) de $G$ sobre $(H,+)$ um grupo abeliano, é uma função $f:E \to H$ tal que
- Orientação: $f(-e) = -f(e)$.
- Seja $x$ um vértice. Defina \[\nabla \cdot f(x) \doteq \sum_{e \text{ incidente em $x$ orientado como $[x,*]$}}f(e).\]
- Conservação em toda aresta: Pedimos que $\nabla \cdot f = 0$ em $V(G)$.
- 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.
Max flow min cut
No que segue, assumiremos $H = \mathbb{N}$ e vamos definir uma rede e seus fluxo associados.
Definição: Uma rede $N \doteq (H,s,t,c)$ consiste nas seguintes informações:
- Um digrafo $G$.
- Uma fonte $s$.
- 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).
Uma fluxo nessa rede é uma circulação $f:E \to \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}$.
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, $\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.
- 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$.
- 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.
A
- grafos/maxfluxmincut.1654279736.txt.gz
- Última modificação: 2022/06/03 15:08
- por 127.0.0.1