Re: [obm-l] Problemas em Aberto III

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

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" <nicolau@sucuri.mat.puc-rio.br>
To: <obm-l@mat.puc-rio.br>
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 � <nicolau@mat.puc-rio.br>
> =========================================================================

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