Re: [obm-l] Triângulos em Grafos

[ronaldogandhi@xxxxxxxxx]

> Oi, pessoal: 
> 
> Aqui vai um probleminha que, se não me engano, foi inventado pelo 
>Erdos: 
> 
> Seja n um inteiro >= 2. Um grafo simples (sem "loops" e com no máximo 
>uma aresta ligando dois vértices quaisquer) tem 2n vértices e n^2+1 
arestas. 
> b) Prove que o grafo contém no mínimo n triângulos. 

   Para provar que o grafo contém 1 triângulo, o procedimento 
não é tão complexo: temos que calcular a probabilidade 
de um grafo com p vértices e q arestas possuir um 
triângulo (isso é um teorema de Pál Erdös que não 
lembro de cabeça) e provar que para p=2n e q=n^2+1 
essa probabilidade é 1. 
Estou meio apressado agora... para quem gosta do 
assunto há uma tese interessante em: 

 http://tumb1.biblio.tu-muenchen.de/publ/diss/in/2003/schickinger.pdf 



[]s  Ronaldo L. Alonso 

_________________________________________________________
Voce quer um iGMail protegido contra vírus e spams? 
Clique aqui: http://www.igmailseguro.ig.com.br
Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/

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