[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] problema do caminhao
>Mas nesse caso, o caminhao não passa pela cidade F.....
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
> =========================================================================