Re: [obm-l] Problemas em Aberto III

["Luis Lopes" <llopes@xxxxxxxxxxxxx>]

Sauda,c~oes,

Oi Cláudio,

Acho que no livro (dos anos 60/70?)
"Flow Network" de Ford and Fulkerson
vc encontra a demonstração deste teorema.

[]'s
Luís

-----Mensagem Original-----
De: "Nicolau C. Saldanha" <nicolau@sucuri.mat.puc-rio.br>
Para: <obm-l@mat.puc-rio.br>
Enviada em: sexta-feira, 7 de março de 2003 16:03
Assunto: Re: [obm-l] Problemas em Aberto III


> On Fri, Mar 07, 2003 at 12:05:14PM -0300, Cláudio (Prática) wrote:
> > > Seja G um grafo direcionado e sejam x e y vértices distintos de G.
> > > Um fluxo de tamanho n de x para y é uma família de n caminhos
> > > indo de x para y que são disjuntos por arestas (ou seja, eles podem
> > > ter vértices em comum mas não arestas).
> > > Um corte de tamanho m é um conjunto de m arestas direcionadas tais
> > > que, se removidas, tornam impossível ir de x até y.
> > >
> > > Maxflow-mincut é o seguinte teorema: o tamanho (n) máximo possível (N)
> > > para um fluxo é igual ao tamanho (m) mínimo possível (M) para um
corte.
> >
> > Será que esta demonstração está correta?
> >


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================