[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Triângulos_em_grafos



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

Cláudio_(Prática) <claudio@praticacorretora.com.br> wrote:
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.
 
a) Prove que este grafo contém um triângulo (três vértices sendo que cada dois dos quais são ligados por uma aresta)
b) Prove que o grafo contém no mínimo n triângulos.
 
(para as definições relativas a grafos veja os artigos do Shine ou do Paulo César nas Eurekas)
 
Um abraço,
Claudio.



Yahoo! GeoCities: 15MB de espaço grátis para criar seu web site!