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