Oi gente, Nossa, quando eu escrevi a outra mensagem eu me esqueci de um grafo c�bico que n�o � hamiltoniano muito familiar (pelo menos para mim): o grafo de Petersen, s�mbolo da OPM. Dicas de como demonstrar que esse grafo n�o � hamiltoniano est�o em http://www.opm.mat.br/misc/petersen.php
L� tamb�m tem a hist�ria do grafo de Petersen, e exatamente como ele serviu como contra-exemplo em v�rios problemas. As dicas de como provar que o grafo n�o � hamiltoniano est�o no final do artigo. H� tr�s problemas l� tamb�m (sendo que um deles � exatamente provar que o grafo n�o � hamiltoniano). Momento propaganda: aproveitem e visitem o site da OPM, que est� de cara nova! http://www.opm.mat.br/ []'s Shine --- eritotutor <[EMAIL PROTECTED]> wrote: > >Boa noite, > > Domingos, e demais colegas, > cmo poderia mostrar ent�o q o grafo n�o � > hamiltoniano? > > > > > > > >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 > > > ========================================================================= > > __________________________________________________________________________ > Acabe com aquelas janelinhas que pulam na sua tela. > AntiPop-up UOL - � gr�tis! > http://antipopup.uol.com.br/ > > > __________________________________ Do you Yahoo!? Make Yahoo! your home page http://www.yahoo.com/r/hs ========================================================================= 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 =========================================================================
