Teoria do Fluxo

Definições

Digrafo

Grafo dirigido, todas as arestas têm orientação.

Exemplo

Digrafo

Grau de Entrada/Saída

Seja vv um vértice de um digrafo dd:

  • Grau de Entrada: Quantas arestas estão direcionadas para vv
  • Grau de Saída: Quantas arestas partem de vv para outro vértice
Exemplo

Digrafo

Neste exemplo, o vértice v tem

  • Grau de entrada 11
  • Grau de saída 33

O vértice S tem

  • Grau de entrada 00
  • Grau de saída 33

Fonte e Sumidouro

Fonte é o vértice de um digrafo conexo com grau de entrada nulo.
Sumidouro é o vértice de um digrafo conexo com grau de saída nulo.

Notação

Um digrafo-ss-tt é um digrafo com fonte ss e sumidouro tt

Rede Capacitada

Uma rede capacitada N=(V,E,s,t,cap)N=(V,E,s,t,\operatorname{cap}) é um digrafo-ss-tt (V,E,s,t)(V,E,s,t), com uma função capacidade cap:V×VN\operatorname{cap}: V \times V \rightarrow \N, tal que, para vértices vi,vkVv_i, v_k \in V:

  • cap(xy)=0\operatorname{cap}(xy)=0 se xyExy \notin E (não é aresta do digrafo)
  • cap(xy)0\operatorname{cap}(xy)\geq0 se xyExy \in E

Fluxo

Um Fluxo numa Rede Capacitada N=(V,E,s,t,cap)N=(V,E,s,t,\operatorname{cap}) é uma atribuição de valores f:V×VN\operatorname{f}: V \times V \rightarrow \N às arestas do digrafo-ss-tt (V,E,s,t)(V,E,s,t), onde:

  • f(xy)=0\operatorname{f}(xy)=0 se xyExy \notin E
  • f(xy)0\operatorname{f}(xy)\geq0 se xyExy \in E
  • f(xy)cap(xy)\operatorname{f}(xy) \leq \operatorname{cap}(xy) (Fluxo não pode exceder capacidade)
  • Fluxo que entra num vértice vv é igual ao fluxo que sai de vv

Valor do Fluxo

O Valor de um Fluxo numa Rede Capacitada será igual ao somatório do fluxo que sai da Fonte, ou Fontes se houver mais do que uma.

Dica

Podemos ver uma Rede Capacitada, como uma rede de canalização da água, onde há uma fonte, destino(sumidouro) e as arestas são canos de água. Tal como na Rede Capacitada, um cano não tem água a circular nos dois sentidos, apenas num.
Seguindo esta ideia,

  • Capacidade (cap)(\operatorname{cap}) indica a quantidade máxima de água que cada cano aguenta.
  • Fluxo (f)(\operatorname{f}) indica a quantidade de água que está a passar em cada um dos canos
  • O Valor do Fluxo é quantidade de água que emitimos na fonte.

Fluxo Máximo

Fluxo máximo é um fluxo f\operatorname{f}, tal que o seu valor é maior ou igual ao valor de qualquer outro fluxo possível na mesma Rede capacitada.

Corte

Numa Rede N=(V,E,s,t,cap)N=(V,E,s,t,\operatorname{cap}), sejam VsV_s e VtV_t uma partição de VV (VsVt=VsVt=V)(V_s\cap V_t = \emptyset \quad \wedge \quad V_s\cup V_t =V), tal que sVss \in V_s e tVtt \in V_t.
Ao conjunto de arestas orientadas de vértices em VsV_s para vértices em VtV_t, ou dá-se o nome de Corte na rede NN e denota-se por (Vs,Vt)(V_s,V_t)

Capacidade do Corte

cap(Vs,Vt)=xVsyVtcap(xy)\operatorname{cap}(V_s,V_t) = \sum_{x \in V_s} \sum_{y \in V_t}\operatorname{cap}(xy)

Soma das capacidades de todas as arestas do corte.

Exemplo

Corte

Neste Corte a vermelho a capacidade do Corte será:

6+3+10+9=286+3+10+9 = 28

Nota

A aresta com capacidade 33 mais abaixo não é incluída, porque vai de VtV_t para VsV_s

Balanço de Fluxo

Balanço de fluxo, através de um corte C=(Vs,Vt)C = (V_s,V_t), que também pode ser identificado por Fluxo do Corte CC, é a soma dos fluxo das arestas orientadas de VsV_s para VtV_t (fluxo positivo) menos a soma dos fluxos das arestas orientadas de um vértice de VtV_t para VsV_s (fluxo negativo).
Qualquer Corte numa Rede Capacitada tem sempre o mesmo Balanço de Fluxo.

Exemplos

Corte

O Balanço do Fluxo deste corte será:

6+3+10+93=256+3+10+9 - 3=25

Corte mínimo

Corte, cuja capacidade é menor ou igual à capacidade de qualquer outro corte da mesma Rede.

Trajetória num Digrafo

Uma trajetória numa rede capacitada N=(V,E,s,t,cap)N=(V,E,s,t,\operatorname{cap}) é uma trajetória aberta de ss a tt.

Relembrar dos Grafos: Trajetória aberta é um caminho que não repete vértices nem arestas, e que não é fechada (não acaba no mesmo vértice)

Quasi-trajetória

Trajetória, mas que pode ter arestas negativas. Seja

Q=s,a1,v1,a2,,vk1,ak,tQ = s,a_1,v_1,a_2,\dots,v_{k-1},a_k,t

uma Quasi-trajetória, pode existir uma aresta aia_i (*com 1<i<k1<i<k) que está dirigida de viv_i para vi1v_{i-1}. Este tipo de arestas é designado por arestas negativas

NOTAS

  • *Não pode ser 1ik1\leq i \leq k, porque uma aresta da fonte sai sempre da fonte e uma do sumidouro está sempre dirigida para este.
  • É normal incluir-se uma trajetória no grupo das Quasi-trajetórias
Exemplos

Quase

Ambas representam Quasi-Trajetórias, mesmo que a vermelha não tenho arestas negativas

Frouxidão

Seja QQ uma Quasi-Trajetória e aa uma aresta que faz parte de QQ, a Frouxidão de aa é dada por:

Δ(a)={cap(a)f(a),se a aresta eˊ positivaf(a),se a aresta eˊ negativacap(a)capacidade da aresta af(a)fluxo da aresta a\Delta(a) = \begin{cases} \operatorname{cap}(a)-\operatorname{f}(a), \quad &\text{se a aresta é positiva} \\ \operatorname{f}(a), \quad &\text{se a aresta é negativa} \end{cases}\\ \operatorname{cap}(a) \rightarrow \text{capacidade da aresta a}\\ \operatorname{f}(a) \rightarrow \text{fluxo da aresta a}

(Obrigado ao Rafael Oliveira)

A Frouxidão mínima de uma Quasi-trajetória (ΔQ)(\Delta_Q) será a mínima frouxidão de entre todas as arestas de QQ.

Incremento do Fluxo

Seja QQ uma Quasi-Trajetória, é possível incrementar o seu fluxo, se a Frouxidão mínima for maior que 00.

Nesse caso, seja (ΔQ)(\Delta_Q) a frouxidão mínima de QQ, adicionamos (ΔQ)(\Delta_Q) ao fluxo das arestas positivas, e retiramos (ΔQ)(\Delta_Q) do fluxo das arestas negativas

Teoremas

Teorema 1

O valor de um fluxo é menor ou igual à capacidade de um corte mínimo numa rede capacitada.
Se o valor do fluxo f\operatorname{f} é igual à capacidade de um corte (Vs,Vt)(V_s,V_t), então o fluxo f\operatorname{f} é máximo e o corte (Vs,Vt)(V_s,V_t) é um corte mínimo.

Demonstração

Seja fc\operatorname{f_c} o fluxo de um corte C=(Vs,Vt)C = (V_s,V_t).
Se fc\operatorname{f_c} é igual à capacidade do corte, então, pela fórmula do fluxo de um corte, a soma dos fluxos das arestas orientadas de um vértice de VtV_t para VsV_s (fluxo negativo) será 00.

Deste modo, o fluxo será máximo, porque é igual à capacidade, e por isso, o corte também será mínimo

QED

Teorema 2

Um fluxo f\operatorname{f} numa Rede Capacitada NN é um fluxo máximo se e só se não existir uma Quasi-trajetória de incremento do fluxo.

Demonstração

Condição Necessária - Se não existe Quasi-Trajetória de aumento, o fluxo é máximo.

Vamos definir um corte (Vs,Vt)(V_s,V_t) mínimo:

  1. sVss \in V_s (relembrar que ss é a fonte)
  2. Se uVsu \in V_s e f(uv)<cap(uv)\operatorname{f}(uv)<\operatorname{cap}(uv), então vVsv \in V_s
  3. Se uVsu \in V_s e f(vu)>0\operatorname{f}(vu)>0, então vVsv \in V_s
  4. Vt=VVsV_t = V - V_s

Face a estas restrições, tt (o sumidouro) terá de pertencer a VtV_t, pois, se não pertencesse haveria uma Quasi-Trajetória de aumento, que não existe como assumido no início da Condição Necessária.
Logo, (Vs,Vt)(V_s,V_t) é um corte.

O fluxo será máximo se for igual à capacidade do corte.
Seja a1a_1 uma aresta do corte (Vs,Vt)(V_s,V_t), esta aresta tem de estar saturada, caso contrário ambos os vértices das arestas pertenceriam a VsV_s (ponto 22)
Seja a2a_2 uma aresta que vai de VtV_t para VsV_s, terá fluxo 00 (ponto 33).

Aplicando o Teorema 1, o Teorema 2 fica demonstrado

QED

Aviso do Professor

Isto só se verifica numa Rede Capacitada com números Racionais. Há situações com números Reais onde não podemos concluir nada.
Contudo, esta exceção não deve ser avaliada.

Algoritmo de Ford-Fulkerson

Numa Rede capacitada N=(V,E,s,t,cap)N=(V,E,s,t,\operatorname{cap}), permite-nos encontrar o Fluxo máximo e, consequentemente, o Corte mínimo.

Pseudo-Código

Pseudo Ford

Descrição Informal

Sempre que houver uma Quasi-Trajetória QQ com Frouxidão mínima positiva, aumentamos o fluxo de QQ.
Quando já não houver termina o algoritmo (pelo Teorema 2), e teremos uma Rede Capacitada com Fluxo máximo.

Corte mínimo pelo Ford-Fulkerson

Seja VsV_s o conjunto dos vértices alcançáveis no final do Algoritmo de Ford-Fulkerson e VtV_t tal que VsVt=VsVt={conjunto de todos os veˊrtices}V_s\cap V_t = \emptyset \quad \wedge \quad V_s\cup V_t =\{\text{conjunto de todos os vértices}\}, (Vs,Vt)(V_s,V_t) é um Corte Mínimo, porque respeita as condições do Teorema 1.

NOTA

Podemos usar o Teorema 1 para verificar que o corte que escolhemos no final do Algoritmo de Ford-Fulkerson é mínimo. Só se for mínimo é que a resposta está correta.

Vértice alcançável

Um vértice vv é alcançável se é possível aumentar o fluxo de uma "pseudo" Quasi-trajetória que começa na fonte e vai até ao vértice vv.

Atenção

Pode acontecer que uma aresta já tenha fluxo = capacidade, mas o vértice a que se dirige seja alcançável. Esses casos devem-se à existência de arestas negativas.

Exemplo do Ford-Fulkerson + Corte

Link