Redes de Fluxo Flashcards
O que é uma rede de fluxo?
É um grafo direcionado com origem s, alvo t em que cada aresta possui uma capacidade c >= 0.
O que é um corte em uma rede de fluxo? Como se mede sua capacidade?
É uma partição (A, B) dos nós com s ∈ A e t ∈ B. Sua capacidade é a soma das capacidades das arestas de A para B.
Em uma rede de fluxo, o que é um fluxo? Qual é seu valor?
Um fluxo é uma função f que satisfaz:
- Para cada e ∈ F, 0 <= f(e) <= c(e) (ou seja, a cada aresta é designada um valor menor igual à sua capacidade).
- Com exceção do vértice inicial e o final, para todos os outros vértices, a soma dos fluxos que entram é igual à soma dos fluxos que saem (lei da conservação de fluxo).
O valor de um fluxo é dado pela diferença do fluxo que sai no vértice inicial e o fluxo que entra do vértice inicial.
Descreva um algoritmo ganancioso simples capaz de encontrar um fluxo máximo de A até B. Por que ele não encontra o melhor resultado?
- Comece com f(e) = 0 para todas as arestas.
- Encontre um caminho p entre s e t de modo que todas as arestas tenham f(e) < c(e) (ou seja, o fluxo seja menor que a capacidade).
- Aumente o fluxo de todas as arestas em p.
- Repita até parar.
O maior problema desse algoritmo é o fato que uma vez que uma aresta tenha chegado à sua capacidade máxima, ela nunca será esvaziada. Isso quer dizer que uma escolha ruim de arestas pode impedir que o algoritmo encontre o resultado ideal.
O que é uma rede residual de fluxo? O que ela representa? Para que ela serve?
É uma rede de fluxo que serve como contraponto a um fluxo em uma rede. A rede residual possui as arestas da rede original com capacidade c(e) - f(e) (ou seja, a capacidade do fluxo em uma direção é a capacidade restante da rede) junto com arestas reversas com capacidade f(e) (ou seja, a capacidade da aresta reversa é o próprio fluxo).
A principal utilidade da rede residual de fluxo é a identificação dos caminhos da rede original que podem ser desfeitos.
No contexto de redes de fluxo, o que é um caminho aumentante?
É um caminho simples s -> t na rede residual Gf.
O que é o gargalo da capacidade de um caminho aumentante P?
É a capacidade residual mínima de qualquer aresta em P.
O que diz o lema do valor de fluxo?
Seja f um fluxo qualquer em um corte (A, B) qualquer. O fluxo de f é o fluxo líquido que passa pelo corte (A, B).
val(f) = soma do fluxo que sai de A - soma do fluxo que entra em A.
O que diz a lei da dualidade fraca no contexto de redes de fluxo?
Seja f um fluxo qualquer e (A, B) um corte qualquer. Então val(f) <= cap(A,B).
O que é um problema de fluxo máximo? O que é um problema de corte mínimo? Qual a relação entre eles? Como essa relação é conhecida ?
O problema do fluxo máximo envolve encontrar o maior fluxo possível em uma rede. O problema do corte mínimo é encontrar o corte em uma rede que possui o menor fluxo possível. A relação entre eles é que o fluxo máximo é o fluxo que passa por um corte mínimo. Essa relação é conhecida como dualidade forte.
O que diz o teorema do caminho aumentante no contexto de redes de fluxo?
Ele diz que um fluxo f é máximo se e somente se não possui caminhos aumentantes.
Em um grafo direcionado com início em s e fim em v, o que é o grafo de nível? Como podemos encontrá-lo?
É um subgrafo que contém apenas arestas envolvidas no caminho mais curto entre s e v (se mais de um caminho com o mesmo número existe, ambos são mantidos).
O que é uma rede de capacidade unitária simples? Qual algoritmo de redes de fluxo possui um desempenho superior nessas redes? Qual a sua complexidade?
É uma rede de fluxo em que cada aresta possui capacidade 1 e cada nó possui ou apenas uma aresta entrando ou apenas uma aresta saindo (ou ambos). Se a rede possui capacidade unitária simples, seu grafo residual também possuirá.
O algoritmo de Dinitz (normalmente O (m n²)) possui complexidade O (m n^1/2) em redes de capacidade unitária simples.
