> É Ramsey. > Não precisa usar teoria de Ramsey não, isso é um dos primeiros teoremas > na teoria dos grafos, se não me engano foi o próprio Euler que provou. > A idéia é simples, construa um grafo onde os vértices são tartarugas e > as arestas unem tartarugas que já acasalaram. Some os graus (nrs. de > arestas saindo de um vértice) de cada vértice, é evidente que essa soma > dá um número par pois cada aresta tem dois extremos e deve ter sido > contada duas vezes. Sendo assim, o número de vértices com grau ímpar tem > que ser par, pegou?
Sim ! valeu ! Eu tinha pensado nisto também, na Eureka me lembro de ter um problema parecido, porém fala sobre conhecer ou desconhecer mutuamente, que é um fato semelhante a acasalar. Até mais. Atenciosamente, Osvaldo Mello Sponquiado 2º ano em Engenharia Elétrica UNESP - Ilha Solteira __________________________________________________________________________ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.com.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 =========================================================================