Re: [obm-l] Problemas em Aberto III

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Thu, Mar 06, 2003 at 04:28:24PM -0300, Cláudio (Prática) wrote:
> Caro Nicolau:
> 
> No no. 24, eu empaquei exatamente na hora de provar que existem 3 caminhos
> disjuntos de X até Y.
> Como eu não conheço teoria dos grafos, maxflow-mincut (seja lá o que isso
> for) é novidade pra mim.


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.

Observe que M >= N é trivial.

[]s, N.

=========================================================================
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>
=========================================================================