> 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 =========================================================================