Re: [obm-l] Triângulos_em_grafos

[ronaldogandhi@xxxxxxxxx]

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