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.
Você poderia recomendar alguma bibliografia a respeito (especialmente na
internet)?

Obrigado e um abraço,
Claudio.

----- Original Message -----
From: "Nicolau C. Saldanha" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Sunday, March 02, 2003 10:04 AM
Subject: Re: [obm-l] Problemas em Aberto III


> On Thu, Feb 27, 2003 at 03:04:48PM -0300, Cláudio (Prática) wrote:
> > 24) Prove que a soma dos comprimentos dos lados de um poliedro
> > convexo qualquer é maior que 3 vezes a maior distancia entre dois
vertices
> > do poliedro.
>
> Sejam x e y vértices a distância máxima. Queremos construir três
> caminhos formados por arestas indo de x até y, e estes caminhos
> devem ser disjuntos (exceto por x, y e possivelmente algum vértice
> no meio). Ora, por maxflow-mincut estes três caminhos só *não*
> existem se existir um corte feito por duas arestas, ou seja,
> se existirem duas arestas que, se removidas, desconectam o grafo
> formado por vértices e arestas. Mas isso estaria em contradição
> com o fato de termos um poliedro convexo.
>
> > 25) Um alienígena move-se na superfície de um planeta com velocidade
> > não superior a U. Uma espaçonave que procura pelo alienígena move-se com
> > velocidade V. Prove que a espaçonave sempre  poderá encontrar o
alinígena
> > se V > 10U.
>
> Não entendi nada. Quando é que a nave encontra o alienígena?
>
> []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 é <[EMAIL PROTECTED]>
> =========================================================================

=========================================================================
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 é <[EMAIL PROTECTED]>
=========================================================================

Responder a