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