Re: [obm-l] problema do caminhao

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

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 <eritotutor@bol.com.br> 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
=========================================================================