Teoria dos Grafos  - Árvores

---

Definição

Grafo Acíclico é um grafo que não contém ciclos.
Todo grafo acíclico é simples.
Um grafo acíclico e conexo é uma árvore
Um grafo acíclico é chamado também de Floresta ( Cada componente conexo é uma árvore ) .
 

G1	G2	G3

Onde G1, G2,G3 são árvores
G1+G2+G3 é uma floresta.

Teorema: Se G é uma árvore, então um único caminho entre cada par de vértices

Demonstração:
Parte1:um caminho
G é uma árvore então G é conexopelo menos um caminho ligando cada par de vértices.
Parte2: O caminho é único

Suponhamos que existam 2 caminhos distintos P e Q ligando dois vértices x,y VG.
Logo, existe uma aresta  = (u,v)  AG tal que P  e  Q ( sem perda de generalidade ) .
PQ é um subgrafo conexo de G, logo, em PQ - existe um passeio de u a v.
Então, por um teorema anterior ,  um caminho R de u a v em PQ -  .
Portanto, R  é um ciclo em G.
Absurdo, visto que G é árvore.

Teorema:  Se G é uma árvore com n vértices, então G possui n-1 arestas.

Por indução em n {Ordenado por numeros de Vértices)
Base: ( n = 1 )

|AG| = 0 = n - 1

Hípotese de Indução

Se G é uma árvore  com k < n vértices, então G possui k-1 arestas.

Passo: ( n >1 ){Assumir que é verdade para todas as árvores com mais que 1 árvore}

Seja G uma árvore com n vértices.
Tome uma aresta  (u,v) AG e considere os componentes distintos K₁ e K₂ obtidos pela retirada de (u,v) de AG, de forma que u  K₁  e  v  K₂ . {Quando eu retiro a aresta u e v eu tenho K1 e K2 que são componentes conexas,Problema:Provar que quando eu retiro a aresta eu realmente tenho uma componente conexa}
 

Árvore com n vértices	K1	K2

Como  |VK₁| < n e |VK₂| < n,  temos pela Hipótese de Indução que:

|AK₁| = |VK₁| - 1 e |AK₂| = |VK₂| - 1{O numero de arestas é igual ao numero de vértices -1}.

Agora,  |AG| = |AK₁| + |AK₂| + 1,
Logo  |AG| = |VK₁| -1 +  |VK₂| - 1  + 1
E portanto,

|AG| = |VK₁| +  |VK₂| - 1 = n -1.

Corolário:  Toda árvore não trivial tem pelo menos 2 vértices de grau 1

Prova: (Por Absurdo)
Vamos supor por absurdo que o total de vértices de  grau 1 não seja maior ou igual a 2
Como G é uma árvore não trivial, ela não possui vértices com grau 0.
Temos então que G possui pelo menos (n-1) vértices de grau maior de 1,

Portanto:
 

gr(v)  2(n-1)  +1

Como gr(v)  = 2 |AG| e,{Teorema da Soma dos Graus}
 pelo teorema anterior,  |AG| = n  -1

Temos que

2(n-1) 2(n-1)  +1 {A soma dos graus do vertice de uma Arvore = 2(narestas-1)
2n -2 2n -1
- 2 - 1
1 2   Absurdo!!!