Re: [obm-l] Problemas em Aberto III

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

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

Infelizmente não é tão simples. Retirar N arestas quaisquer, uma por caminho,
não necessariamente desconecta o grafo (mesmo se N for máximo).

Exemplo:

x .---.---.---.---.---.---.
  |   |   |   |   |   |   |
  .---.---.---.---.---.---. y

Neste exemplo claramente M=N=2 mas se tomarmos os dois caminhos como
sendo o bordo superior e o bordo inferior e retirarmos duas arestas para obter


x .---.---.   .---.---.---.
  |   |   |   |   |   |   |
  .---.---.---.   .---.---. y

isso não desconectou o grafo. É claro que *teríamos* desconectado
se tivéssemos escolhido ao invés

x .---.---.   .---.---.---.
  |   |   |   |   |   |   |
  .---.---.   .---.---.---. y


e é preciso provar que sempre existe uma escolha
de N arestas que de fato desconecta (se N for máximo, claro).

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