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