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