Re: [obm-l] problema do caminhao

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Que tal o caminho
A-B-G-H-I-J-K-L-C-D-E-A?

Veja que ele passa por todas as cidades e ainda pode
voltar para A.

O que voc� descreveu na verdade pode ser visualizado
como um dodecaedro.

Se voc� estudou teoria dos grafos, pode notar que o
problema pede para provar a exist�ncia de um caminho
(ciclo) hamiltoniano nesse grafo que � c�bico. Se n�o
me engano (pode ser que eu esteja enganado), todo
grafo conexo c�bico (todo v�rtice tem grau 3) admite
um ciclo hamiltoniano.

[]'s
Shine

--- eritotutor <eritotutor@bol.com.br> wrote:
>  Boa tarde,
> 
>  Considere um caminh�o que abastece as  cidades A, B
> , C, D, E, F, G, H, I, J, K , L. Duas cidades s�o
> adjacentes se existe um caminho entre elas.
>  A � adjacente a B, J, E
> B � adjacente a A, C, G
> C � adjacente a L, B, D
> D � adjacente a E, C, H
> E � adjacente a D, A , F
> F � adjacente a L, E, G
> G � adjacente a H, F, B
> H � adjacente a I, G, D
> I � adjacente a K, J, H
> J � adjacente a K, I, A
> K � adjacente a J, I, L
> L � adjacente a K,C,F
> � poss�vel que o caminh�o saia da cidade A e
> percorra todas as cidades uma �nica vez? Justifique
> 
> 
> Desde j� agrade�o
> 
> 
> []s
>  
>
__________________________________________________________________________
> Acabe com aquelas janelinhas que pulam na sua tela.
> AntiPop-up UOL - � gr�tis!
> http://antipopup.uol.com.br/
> 
> 
> 


		
Discover Yahoo! 
Find restaurants, movies, travel and more fun for the weekend. Check it out! 
http://discover.yahoo.com/weekend.html 

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