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
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
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
- Toda árvore que possui pelo menos dois vértices deve ter pelo menos duas folhas.
- 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.
- Cada borda de uma árvore é cortada.
- Adicionar uma aresta a uma árvore define exatamente um ciclo.
- Cada gráfico conectado contém uma árvore geradora.
- 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:
A partir do gráfico G acima, podemos implementar as seguintes três árvores geradoras H:
Métodos para encontrar a árvore geradora
Podemos encontrar a árvore geradora sistematicamente usando um dos dois métodos:
- Método de redução
- 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,
- Se removermos a aresta ac que destrói o ciclo a-d-c-a no gráfico acima, obteremos o seguinte gráfico:
- 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:
- Se removermos a aresta ec, que destrói o ciclo d-e-c-d do gráfico acima, obteremos a seguinte árvore geradora:
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,
- Escolha a borda ab ,
- Escolha a borda de ,
- Depois disso, escolha a borda CE ,
- Em seguida, escolha a borda cb , finalmente obtemos a seguinte árvore geradora:
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
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