Re: [obm-l] Triângulos_em_grafos

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

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!