Re: [obm-l] problema do caminhao

[fabiodjalma <fabiodjalma@xxxxxxxxx>]

Shine, infelizmente nunca estudei grafos. Poderia dar uma dica (livro, 
artigo ou página) onde eu possa compensar essa deficiência? 


Em (15:06:29), obm-l@mat.puc-rio.br escreveu: 


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