Re: [obm-l] Problemas em Aberto III

["Cl�udio \(Pr�tica\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

----- Original Message -----
From: "Nicolau C. Saldanha" <nicolau@sucuri.mat.puc-rio.br>
To: <obm-l@mat.puc-rio.br>
Sent: Friday, March 07, 2003 9:15 AM
Subject: Re: [obm-l] Problemas em Aberto III


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

Caro Nicolau:

Ser� que esta demonstra��o est� correta?

Suponhamos que M > N. Isso significa que qualquer corte tem mais do que N
arestas.
Tome um (possivelmente o �nico) fluxo de tamanho N, o qual liga os v�rtices
X e Y e remova uma aresta de cada um dos N caminhos deste fluxo. Ap�s a
remo��o das arestas ser� imposs�vel ir de X a Y, pois cada caminho poss�vel
ter� sido interrompido. Logo, as N arestas removidas constituem um corte ==>
contradi��o, pois qualquer corte tem mais do que N arestas ==> M <= N.

Assim, concluimos que M = N.

Um abra�o,
Claudio.


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