Problemas de fluxo numa rede
Modelar fluxos conservativos entre dois pontos através de canais com capacidade limitada
1
2
s
Fluxo num arco não pode
ultrapassar a capacidade
Soma das entradas num nó
igual à soma das saídas
Exemplos
• abastecimento de líquido
ponto a ponto
• tráfego entre dois pontos
- s: fonte; t: poço
- distribuição de fluxo pelos
arcos arbitrária, desde que
respeite as setas
s
3
2
1
a
3
b
4
3
c
d
2
3
t
0
a
2
2
b
1
2
2
c
d
2
3
t
Grafos - 1
Fluxo máximo: 1ª abordagem
 algoritmo simples de aproximações sucessivas baseado em
• G  grafo base de capacidades
• Gf  grafo auxiliar de fluxos
- inicialmente fluxos iguais a 0
- no fim, fluxo máximo
• Gr  grafo residual (auxiliar)
- capacidade disponível em cada arco (= capacidade - fluxo)
- capacidade disponível = 0 — eliminar arco saturado
 método de calcular o fluxo máximo entre s e t
• em cada iteração, selecciona-se um caminho em Gr entre s e t (de acréscimo) —
algoritmo não determinístico
• valor mínimo nos arcos desse caminho = quantidade a aumentar a cada um dos
arcos respectivos em Gf
• recalcular Gr
• termina quando não houver caminho de s para t
Grafos - 2
Exemplo: estado inicial
s
s
3
2
1
a
0
b
4
3
d
2
3
t
G
0
0
a
2
c
s
3
b
0
0
c
d
0
0
1
a
0
2
b
4
3
2
c
d
2
3
t
t
Gf
Gr
Grafos - 3
Exemplo: 1ª iteração
s
s
3
2
1
a
0
b
4
3
d
2
3
t
G
2
0
a
2
c
s
3
b
0
0
2
c
d
0
2
1
a
b
4
3
c
d
2
1
t
t
Gf
Gr
Grafos - 4
Exemplo: 2ª iteração
s
s
3
2
1
a
2
b
4
3
d
2
3
t
G
2
0
a
2
c
s
1
b
0
2
2
c
d
2
a
1
b
4
1
c
d
2
1
t
t
Gf
Gr
Grafos - 5
Exemplo: 3ª iteração
s
s
3
2
1
a
3
b
4
3
d
2
3
t
G
2
0
a
2
c
s
b
1
2
2
c
d
2
a
1
b
3
1
c
d
3
t
t
Gf
Gr
Grafos - 6
Algoritmo não garante fluxo óptimo
 critério ganancioso de selecção do caminho: escolher o que dê maior fluxo
- caminho s, a, d, t (3 unidades de fluxo)  algoritmo termina sem obter o máximo
- exemplo de algoritmo ganancioso que falha
s
s
3
2
1
a
3
b
4
3
d
2
3
t
0
0
a
2
c
s
2
b
3
0
d
0
3
t
a
0
c
1
b
1
3
c
2
d
2
t
Grafos - 7
Algoritmo determinístico
permitir que o algoritmo mude de ideias
•
•
•
•
para cada arco (v,w) com fluxo f(v,w) no grafo de fluxos acrescenta-se um arco (w,v) no
grafo residual com capacidade f(v,w)
- corresponde a deixar devolver fluxo para trás (nunca fica globalmente negativo, contra o
arco)
- podem existir arcos em sentidos opostos; podem existir ciclos
se as capacidades forem números racionais, o algoritmo termina com máximo
se as capacidades forem inteiros e o fluxo máximo f
- bastam f estádios (fluxo aumenta pelo menos 1 por estádio)
- tempo de execução ( caminho mais curto não pesado ) é O(f. |E| )  mau
evitar o problema
- escolher caminho que dá maior aumento de fluxo
- semelhante ao problema do caminho pesado mais curto (pequena alteração a Dijkstra)
- fluxo máximo em O(|E| log capMax)
(capMax = capacidade máxima de um arco)
- cada cálculo de um aumento em O(|E| log |V|) (Dijkstra)
- global: O(|E|^2 log |V| log capMax)
Grafos - 8
Solução óptima - 1ª iteração
s
s
3
2
1
a
3
b
4
3
s
0
a
2
0
3
b
3
0
2
1
a
0
b
1
3
2
3
c
d
2
3
t
G
c
d
0
3
c
d
2
3
t
t
Gf
Gr
3 unidades de fluxo no caminho sadt
Grafos - 9
Solução óptima - 2ª iteração
s
s
3
2
1
a
3
b
4
3
s
0
a
2
2
3
b
1
2
2
1
a
2
2
b
3
1
2
1
c
d
2
3
t
G
c
d
2
c
3
d
2
3
t
t
Gf
Gr
2 unidades de fluxo no caminho s,b,d,a,c, t
Grafos - 10
Caso difícil
1 000 000
a
1 000 000
s
1
t
- se se escolher passar sempre por a e por b…
1 000 000
b
1 000 000
s
1
999 999
1
a
b
1
1
t
999 999
1
0
a
… temos 2 000 000 de iterações,
em vez de 2!
s
b
1
1 000 000
1 1
1
a
1 000 000
1
t
s
a
999 999
b
999 999
t
s
1 1
1
1 1
t
999 999
b
999 999
Grafos - 11
Árvores de expansão mínimas
Árvore que liga todos os vértices do grafo usando arestas com um custo total mínimo
•
caso do grafo não dirigido
•
grafo tem que ser conexo
•
árvore  acíclico
•
número de arestas = |V| - 1
 exemplo de aplicação: cablamento de uma casa
- vértices são as tomadas
- arestas são os comprimentos dos troços
Grafos - 12
Algoritmo de Prim
 expandir a árvore por adição sucessiva de arestas e respectivos vértices
•
critério de selecção: escolher a aresta (u,v) de menor custo tal que u já pertence à
árvore e v não (ganancioso)
•
início: um vértice qualquer
 idêntico ao algoritmo de Dijkstra para o caminho mais curto
•
informação para cada vértice
- dist(v) é o custo mínimo das arestas que ligam a um vértice já na árvore
- path(v) é o último vértice a alterar dist(v)
- known(v) indica se o vértice jé foi processado (isto é, se já pertence à árvore)
•
diferença na regra de actualização: após a selecção do vértice v, para cada w não
processado, adjacente a v, dist(w) = min{ dist(w), cost(w,v) }
•
tempo de execução
- O( |V|2 ) sem fila de prioridade
- O( |E| log |V| ) com fila de prioridade
Grafos - 13
Evolução do algoritmo de Prim
4
2
1
5
7
4
8
5
4
1
6

10
3
2
3
2
1
última
tabela
6
7


1
1
2
1

3
1
2
2
2
1
4

3
4
1
2
known
1
1
1
1
1
1
1

2
1
4
v
1
2
3
4
5
6
7
2
1
4
4

3
2
4
2
7
1
2
1
5
4
4
6
2
1
2
1
path
0
1
4
1
7
7
4
2
1
3
2
dist
0
2
2
1
6
1
4
4
7
6
1
7
6
Grafos - 14
Algoritmo de Kruskal
 analisar as arestas por ordem crescente de peso e aceitar as que não provocarem
ciclos (ganancioso)
 método
•
manter uma floresta, inicialmente com um vértice em cada árvore (há |V|)
•
adicionar uma aresta é fundir duas árvores
•
quando o algoritmo termina há só uma árvore (de expansão mínima)
 aceitação de arestas — algoritmo de Busca/União em conjuntos
•
representados como árvores
•
se dois vértices pertencem à mesma árvore/conjunto, mais uma aresta entre eles
provoca um ciclo (2 Buscas)
•
se são de conjuntos disjuntos, aceitar a aresta é aplicar-lhes uma União
 selecção de arestas: ordenar por peso ou, melhor, construir fila de prioridade em tempo
linear e usar Apaga_Min
•
tempo no pior caso O( |E| log |E| ), dominado pelas operações na fila
Grafos - 15
Pseudocódigo (Kruskal)
void kruskal()
{
DisjSet s;
PriorityQueue h;
Vertex u, v;
SetType uset, vset;
Edge e,
int edgesAccepted = 0;
h = readGraphIntoHeapArray();
h.buildHeap();
s = new DisjSet(NUM_VERTICES);
}}
while(edgesAccepted < NUM_VERTICES -1 )
{
e = h.deleteMin();
// e = (u,v)
uset = s.find(u);
vset = s.find(v);
if (uset != vset)
{
edgesAccepted++;
S.union(uset, vset);
}
Grafos - 16
Evolução do algoritmo de Kruskal
4
1
1
5
2
7
4
8
4
1
6
1
2
10
3
2
3

2
3
5
6
6
7
5
4

7

1
1
2
1
1
3
5
4
6
7
2
3
5
4
6
1
7
Grafos - 17
Evolução do algoritmo de Kruskal
4
2
1
2
3
5
2
1
7
4
8
4
1
6

10
3
7
2
1
5
3
6
2
5
4

2
1
7
2
1
1
3
2
1
6

2
1
2
1
5
4
3
2
5
4
4
6
1
7

1
3
2
2
6
2
1
7
1
4
5
4
6
1
7
6
Grafos - 18