fluxo

Fluxo em Redes http://www.ime.usp.br/~pf/flows/ Paulo Feofiloff
Departamento de Ciência da Computação
Instituto de Matemática e Estatística
Universidade de São Paulo

//

Prefácio
Estas notas de aula foram escritas em 2002 para as disciplinas de Otimização Combinatória (MAC5781 e MAC0325) no IME–USP (Instituto de Matemática e Estatística da
Universidade de São Paulo). As notas foram baseadas em dois livros:
• Ahuja–Magnanti–Orlin [AMO93], que chamaremos de “AMO”, e
• Cormen–Leiserson–Rivest–Stein [CLRS01], que chamaremos de “CLRS”.
Também serviu de referência o excelente livro de Cook, Cunningham, Pulleyblank e Schrijver [CCPS98], que chamaremos de “CCPS”.
Ocasionalmente citamos também os números de capítulos do “CLR” [CLR91], que é a primeira edição do CLRS.
Ao contrário do que fazem os livros citados, estas notas identificam as invariantes dos algoritmos, permitindo assim uma análise mais rigorosa de sua correção.

1

Sumário
1

8

1.1

O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.2

Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3
2

Programação linear: resumo

Um caso particular importante . . . . . . . . . . . . . . . . . . . . . . . . .

10

Conceitos básicos de redes

11

2.1

Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2

Matriz de incidências e matriz de adjacências . . . . . . . . . . . . . . . . .

12

2.3

Passeios, caminhos, ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.4

Função-predecessor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.5

Grafo de predecessores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.6

Cortes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.7

Redes . . . . . . . . . . . . . . . . . . . . . . .