logo

Árvore e Floresta

1. O que é Árvore e Floresta?

Árvore

  • Na teoria dos grafos, um árvore é um gráfico não direcionado, conectado e acíclico . Em outras palavras, um grafo conectado que não contém nem mesmo um único ciclo é chamado de árvore.
  • Uma árvore representa a estrutura hierárquica em forma gráfica.
  • Os elementos das árvores são chamados de nós e as bordas da árvore são chamadas de galhos.
  • Uma árvore com n vértices possui (n-1) arestas.
  • As árvores fornecem muitas aplicações úteis, tão simples como uma árvore genealógica até tão complexas quanto as árvores em estruturas de dados da ciência da computação.
  • A folha em uma árvore há um vértice de grau 1 ou qualquer vértice que não tenha filhos é chamado de folha.

Exemplo

Árvore e Floresta

No exemplo acima, todas são árvores com menos de 6 vértices.

Floresta

Na teoria dos grafos, um floresta é um gráfico não direcionado, desconectado e acíclico . Em outras palavras, um conjunto disjunto de árvores é conhecido como floresta. Cada componente de uma floresta é uma árvore.

Exemplo

Árvore e Floresta

O gráfico acima se parece com dois subgráficos, mas é um único gráfico desconectado. Não há ciclos no gráfico acima. Portanto é uma floresta.


2. Propriedades das árvores

  1. Toda árvore que possui pelo menos dois vértices deve ter pelo menos duas folhas.
  2. As árvores têm muitas caracterizações:
    Seja T um gráfico com n vértices, então as seguintes afirmações são equivalentes:
    • T é uma árvore.
    • T não contém ciclos e possui n-1 arestas.
    • T está conectado e tem (n -1) aresta.
    • T é um gráfico conectado e cada aresta é uma aresta de corte.
    • Quaisquer dois vértices do grafo T estão conectados por exatamente um caminho.
    • T não contém ciclos e, para qualquer nova aresta e, o grafo T+ e possui exatamente um ciclo.
  3. Cada borda de uma árvore é cortada.
  4. Adicionar uma aresta a uma árvore define exatamente um ciclo.
  5. Cada gráfico conectado contém uma árvore geradora.
  6. Toda árvore possui pelo menos dois vértices de grau dois.

3. Árvore Geradora

A árvore geradora em um grafo conectado G é um subgrafo H de G que inclui todos os vértices de G e também é uma árvore.

Exemplo

Considere o seguinte gráfico G:

Árvore e Floresta

A partir do gráfico G acima, podemos implementar as seguintes três árvores geradoras H:

Árvore e Floresta

Métodos para encontrar a árvore geradora

Podemos encontrar a árvore geradora sistematicamente usando um dos dois métodos:

  1. Método de redução
  2. Método de construção

1. Método de redução

  • Comece escolhendo qualquer ciclo no Gráfico G.
  • Remova uma das bordas do ciclo.
  • Repita esse processo até que não haja mais ciclos.

Exemplo

  • Considere um gráfico G,
Árvore e Floresta
  • Se removermos a aresta ac que destrói o ciclo a-d-c-a no gráfico acima, obteremos o seguinte gráfico:
Árvore e Floresta
  • Remova a aresta cb, que destrói o ciclo a-d-c-b-a do gráfico acima, então obtemos o seguinte gráfico:
Árvore e Floresta
  • Se removermos a aresta ec, que destrói o ciclo d-e-c-d do gráfico acima, obteremos a seguinte árvore geradora:
Árvore e Floresta

2. Método de construção

  • Selecione as arestas do gráfico G, uma de cada vez. De forma que não sejam criados ciclos.
  • Repita este processo até que todos os vértices sejam incluídos.

Exemplo

Considere o seguinte gráfico G,

Árvore e Floresta
  • Escolha a borda ab ,
Árvore e Floresta
  • Escolha a borda de ,
Árvore e Floresta
  • Depois disso, escolha a borda CE ,
Árvore e Floresta
  • Em seguida, escolha a borda cb , finalmente obtemos a seguinte árvore geradora:
Árvore e Floresta

Classificação do Circuito

O número de arestas que precisamos excluir de G para obter uma árvore geradora.

Árvore geradora G = m- (n-1) , que é chamado de classificação do circuito de G.

 Where, m = No. of edges. n = No. of vertices. 

Exemplo

Árvore e Floresta

No gráfico acima, arestas m = 7 e vértices n = 5

Então a classificação do circuito é,

 G = m - (n - 1) = 7 - (5 - 1) = 3