Re: [obm-l] problema do caminhao

["Domingos Jr." <dopikas@xxxxxxxxxx>]

>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.
>  
>
Isso � falso... at� mesmo se nos restringirmos a grafos c�bicos 
bipartidos 3-conexos, veja
http://mathworld.wolfram.com/BicubicGraph.html

H� a seguinte conjectura em aberto
http://mathworld.wolfram.com/BarnettesConjecture.html

[ ]'s
=========================================================================
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
=========================================================================