[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: RES: Canos




On Fri, 31 Mar 2000, Marcos Paulo wrote:

> 
> Esse problema eh classico de grafos mas ouvi dizer q se os elementos
> estivessem num toro isso seria possivel!

� correto. Fica como exerc�cio determinar o maior N tal que � poss�vel
em um toro ligar todos os pares dentre N pontos sem criar interse��es.
[]s, N.

> -----Mensagem original-----
> De: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br]Em
> nome de Nicolau C. Saldanha
> Enviada em: quinta-feira, 30 de mar�o de 2000 18:38
> Para: obm-l@matinta.mat.puc-rio.br
> Assunto: Re: Canos
> 
> 
> 
> 
> On Thu, 30 Mar 2000, Eduardo Casagrande Stabel wrote:
> 
> > Faz um tempao que eu nao mando mensagem para a lista.
> > Tem um problema que nao sei resolver.
> >
> > Temos 3 asteriscos e 3 ozinhos, temos que ligar com uma linha (pode ser
> > curva) cada asterisco a cada ozinho sem que uma linha cruze uma outra.
> > A disposicao e' a seguinte:
> > *        *         *
> >
> > o        o         o
> > Pelo que sei nao da pra fazer, mas como que se prova isso?
> >
> > Eduardo Casagrande Stabel.
> >
> 
> A localiza��o dos pontos n�o � importante.
> Suponha por absurdo que fosse poss�vel com tr�s o e tr�s * na esfera.
> Obtemos assim uma decomposi��o da esfera com 6 v�rtices e 9 arestas.
> Pela f�rmula de Euler devemos ter 5 faces.
> Cada face tem um n�mero par de v�rtices
> (pois eles alternam entre o e *), donde pelo menos 4.
> Assim, o n�mero total de lados de todas as faces � pelo menos 5*4 = 20.
> Cada aresta corresponde a 2 lados, donde temos pelo menos 10 arestas,
> contradi��o.
> 
>