[obm-l] PROBLEMA DO CAIXEIRO VIAJANTE!

[jorgeluis@xxxxxxxxxxxxx]

O PCV é um dos mais tradicionais e conhecidos problemas de programação
matemática e lidam em sua maior parte com passeios ou tours sobre pontos de
demanda ou oferta. Dentre os tipos de passeios um dos mais importantes é o
denominado hamiltoniano. Seu nome é devido a Willian Rowan Hamilton que, em
1857, propôs um jogo que denominou Around the World. O jogo era feito sobre um
dodecaedro em que cada vértice estava associado a uma cidade importante da
época. O desafio consistia em encontrar uma rota através dos vértices do
dodecaedro que iniciasse e terminasse em uma mesma cidade sem nunca repetir uma
visita. Uma solução do jogo de Hamilton, em sua homenagem, passou a se denominar
um cliclo hamiltoniano. Hamilton não foi o primeiro a propor esse problema, mas
seu jogo o divulgou. Modernamente, a primeira menção conhecida do problema é
devida a Hassler Whitney em 1934 em um trabalho na Princeton University. A
literatura que aborda a solução do PCV nas suas diversas versões é uma das mais
ricas dentro da pesquisa operacional.

Prove que sempre existe um circuito hamiltoniano em um grafo conexo onde todos
os nós têm grau 2.

Um abraço à todos!



______________________________________________
WebMail UNIFOR - http://www.unifor.br.
=========================================================================
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
=========================================================================