RECESSO
1 NOV, SEG |
Não haverá aula.
|
AULA 20
4 NOV, QUI |
- Resumo da aula anterior.
- Fluxos em redes: redes; fluxos em redes; Problema do Fluxo Máximo;
cortes em redes; caminhos aumentantes [ps | dvi].
- Proposição 1. Seja f e delta(S) um fluxo e um corte
em (D,s,t,c), respectivamente. Então val(f) <= cap(S).
- Trailer dos próximos episódios.
|
AULA 21
8 NOV, SEG |
- Resumo da aula anterior.
- Fluxos em redes: redes; fluxos em redes; Problema do Fluxo Máximo;
cortes em redes; caminhos aumentantes [ps | dvi].
- Proposição 2. Um fluxo f em N é máximo se e
somente se não existe um f-caminho aumentante até t. Ademais,
se f é um fluxo máximo então existe um s-t-corte
delta(S) tal que cap(S) = val(f).
- Teorema 1. (Teorema do Fluxo Máximo e Corte Mínimo)
Se N=(D,s,t,c) é uma rede então
max{ val(f) | f é um fluxo em N} = min{cap(S) | delta(S) é um corte
em N}.
- Emparelhamentos máximos em grafos bipartidos do ponto de vista de fluxos.
- Trailer dos próximos episódios.
|
AULA 22
11 NOV, QUI |
- Resumo da aula anterior.
- Fluxos do ponto de vista algorítmico: O Método dos caminhos aumentantes
de Ford e Fulkerson e o algoritmo de Edmonds e Karp
[ps | dvi].
- Trailer dos próximos episódios.
|
FERIADO
15 NOV, SEG |
PROCLAMAÇÃO DA REPÚBLICA, não haverá aula.
|
SACO CHEIO
18 NOV, QUI |
SEMANA DO SACO CHEIO, não haverá aula.
|
AULA 23
22 NOV, SEG |
|
AULA 24
25 NOV, QUI |
- Resumo da aula anterior.
- Trailer dos próximos episódios.
|
AULA 25
29 NOV, SEG |
- Resumo da aula anterior.
- Trailer dos próximos episódios.
|