Re: [obm-l] PROBLEMA DO CAIXEIRO VIAJANTE!

[Chicao Valadares <chicaovaladares@xxxxxxxxxxxx>]

> Prove que sempre existe um circuito hamiltoniano em
> um grafo conexo onde todos
> os nós têm grau 2.
Base: Triangulo(facil)

Induçao:Suponha dado um grafo nesta condiçoes, com k
vertices,com um circuito hamiltoniano, pegue 2
vertices v1 e v2 arbitrarios
ligados por uma aresta e retire esta aresta e coloque
um novo vertice x e duas arestas a1 e a2, sendo que a1
e a2 esta ligado x e a1 esta ligado a v1 e a2 esta
ligado a v2.Observe que x tem grau 2 e v1 e v2
continuam tendo grau 2, alem do mais na caminhada que
representa o circuito hamiltoniano de v1 pra v2(ou v2
pra v1) pela aresta entre eles, passa a ser
substituida pela caminhada v1->x->v2(ou v2->x->v1)
passando ainda por v1 e v2 apenas uma vez e passando
por x apenas uma vez.Logo o circuito hamiltoniano é
preservado para o grafo de k + 1 vertices.   

=====
"O Binômio de Newton é tão belo como a Vênus de Milo.
O que há é pouca gente para dar por isso... "
Fernando Pessoa - Poesias de Alvaro Campos

_________________________________________________________________
As informações existentes nessa mensagem e no(s) arquivo(s) anexado(s) 
são
para uso restrito, sendo seu sigilo protegido por lei. Caso não seja
destinatário, saiba que leitura, divulgação ou cópia são proibidas. 
Favor
apagar as informações e notificar o remetente. O uso impróprio será 
tratado
conforme as normas da empresa e a legislação em vigor. Agradecemos sua
colaboração.


The information mentioned in this message and in the archives attached 
are
of restricted use, and its privacy is protected by law. If you are not 
the
addressee, be aware that reading, disclosure or copy are forbidden. 
Please
delete this information and notify the sender. Inappropriate use will 
be
tracted according to company's rules and valid laws. Thank you for your
cooperation.

__________________________________________________
Converse com seus amigos em tempo real com o Yahoo! Messenger 
http://br.download.yahoo.com/messenger/ 
=========================================================================
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
=========================================================================