>Este e o famoso teorema de Turan.Tenho uma demo com PIF.A parte dos n triangulos parece meio louca... > Vamos ver como um grafo de n vertices nao tem triangulos. > n=1, e obvio(ou nao...) que com 1 aresta nao da triangulo > Se vale para n=k vamos ver para n=k+1 > Basta ver um grafo de 2n+2 vertices sem triangulos, e retirar dois vertices.Os restantes ainda dao um grafo sem triangulos.Agora e so ver quantas arestas saem no maximo de cada vertice fantasma, de modo a nao dar K_3.Este valor seria 2n+1, que com os n^2 restantes serve! > Acho que e isso...
Não entendi... A seção III do paper abaixo há uma explicação bastante detalhada da teoria de Erdös-Rény sobre grafos randômicos que mencionei na mensagem anterior: http://www.nd.edu/~networks/PDF/rmp.pdf A primeira propriedade de grafos randômicos a ser estudada pelos dois foi o aparecimento de subgrafos. Os exemplos mais simples de subgrafos são ciclos. Um ciclo de ordem k é um loop fechado de k arestas tais que duas arestas consecutivas só tem um nó comum. Isso é, um triângulo é um ciclo de ordem 3, enquanto que um retângulo é um ciclo de ordem 4. Subgrafos completos de ordem k são subgrafos totalmente conectatos, isto é possuem comb(k 2) = k(k-1)/2 arestas. Se começarmos com N nós isolados e conectarmos cada par de nós (vértices) com probabilidade p, para valores pequenos de p os grafos são isolados. Mas a medida que p aumenta vão necessariamente surgindo ciclos de ordem 3, 4 e assim por diante. Uma refraseamento do problema colocado, seria determinar a probabilidade p para a qual todos os grafos contém ciclos de ordem 3. Basicamente os resultados da teoria são os seguintes: Se temos um grafo randômico G=G(N,p) (N vértices conectados com probabilidade p) e seja um subgrafo F contendo k vértices e l arestas. Quantos desses subgrafos podem existir em G? Os resultados básicos da teoria são. (a) a probabilidade crítica de ter um ciclo de ordem k é pc(N) = cN^(-k/(k-1)) (b) a probabilidade crítica de ter um subgrafo completo de ordem k é pc(N)=cN^(-2(k-1)) Obs: Ciclos de ordem 3 podem ser vistos como subgrafos completos de ordem 3 e a probabilidade deles ocorrerem com N arestas é (considerando c = 1) -- []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 =========================================================================