Neste artigo, discutiremos a árvore geradora e a árvore geradora mínima. Mas antes de passarmos diretamente para a árvore geradora, vamos primeiro ver uma breve descrição do gráfico e seus tipos.
Gráfico
Um gráfico pode ser definido como um grupo de vértices e arestas para conectar esses vértices. Os tipos de gráficos são fornecidos a seguir -
Agora, vamos avançar para a árvore geradora de tópicos.
O que é uma árvore geradora?
Uma árvore geradora pode ser definida como o subgrafo de um grafo conectado não direcionado. Inclui todos os vértices junto com o menor número possível de arestas. Se algum vértice for perdido, não é uma árvore geradora. Uma árvore geradora é um subconjunto do gráfico que não possui ciclos e também não pode ser desconectado.
Uma árvore geradora consiste em (n-1) arestas, onde 'n' é o número de vértices (ou nós). As arestas da árvore geradora podem ou não ter pesos atribuídos a elas. Todas as árvores geradoras possíveis criadas a partir do grafo G dado teriam o mesmo número de vértices, mas o número de arestas na árvore geradora seria igual ao número de vértices no grafo dado menos 1.
Um gráfico não direcionado completo pode ter nn-2 número de árvores geradoras onde n é o número de vértices no gráfico. Suponha que, se n = 5 , o número máximo de árvores geradoras possíveis seria 55-2= 125.
Aplicações da árvore geradora
Basicamente, uma árvore geradora é usada para encontrar um caminho mínimo para conectar todos os nós do grafo. Algumas das aplicações comuns da árvore geradora estão listadas a seguir -
- Análise de Cluster
- Planejamento de rede civil
- Protocolo de roteamento de rede de computadores
Agora, vamos entender a árvore geradora com a ajuda de um exemplo.
Exemplo de árvore geradora
Suponha que o gráfico seja -
Conforme discutido acima, uma árvore geradora contém o mesmo número de vértices que o gráfico, o número de vértices no gráfico acima é 5; portanto, a árvore geradora conterá 5 vértices. As arestas na árvore geradora serão iguais ao número de vértices no gráfico menos 1. Portanto, haverá 4 arestas na árvore geradora.
Algumas das árvores geradoras possíveis que serão criadas a partir do gráfico acima são fornecidas a seguir -
Propriedades da árvore geradora
Algumas das propriedades da árvore geradora são fornecidas a seguir -
- Pode haver mais de uma árvore geradora de um grafo conectado G.
- Uma árvore geradora não possui ciclos ou loops.
- Uma árvore geradora é minimamente conectado, portanto, remover uma aresta da árvore fará com que o gráfico seja desconectado.
- Uma árvore geradora é maximamente acíclico, portanto, adicionar uma aresta à árvore criará um loop.
- Pode haver um máximo nn-2 número de árvores geradoras que podem ser criadas a partir de um gráfico completo.
- Uma árvore geradora tem n-1 arestas, onde 'n' é o número de nós.
- Se o gráfico for um gráfico completo, então a árvore geradora pode ser construída removendo o máximo (en+1) arestas, onde 'e' é o número de arestas e 'n' é o número de vértices.
Portanto, uma árvore geradora é um subconjunto do grafo conectado G, e não existe uma árvore geradora de um grafo desconectado.
Árvore de abrangência mínima
Uma árvore geradora mínima pode ser definida como a árvore geradora em que a soma dos pesos da aresta é mínima. O peso da árvore geradora é a soma dos pesos atribuídos às arestas da árvore geradora. No mundo real, esse peso pode ser considerado como distância, carga de tráfego, congestionamento ou qualquer valor aleatório.
Exemplo de árvore geradora mínima
Vamos entender a árvore geradora mínima com a ajuda de um exemplo.
A soma das arestas do gráfico acima é 16. Agora, algumas das possíveis árvores geradoras criadas a partir do gráfico acima são -
Portanto, a árvore geradora mínima selecionada a partir das árvores geradoras acima para o gráfico ponderado fornecido é -
Aplicações de árvore geradora mínima
As aplicações da árvore geradora mínima são fornecidas a seguir -
- A árvore geradora mínima pode ser usada para projetar redes de abastecimento de água, redes de telecomunicações e redes elétricas.
- Ele pode ser usado para encontrar caminhos no mapa.
Algoritmos para árvore geradora mínima
Uma árvore geradora mínima pode ser encontrada a partir de um gráfico ponderado usando os algoritmos fornecidos abaixo -
- Algoritmo de Prim
- Algoritmo de Kruskal
Vamos ver uma breve descrição de ambos os algoritmos listados acima.
Algoritmo de Prim - É um algoritmo ganancioso que começa com uma árvore geradora vazia. É usado para encontrar a árvore geradora mínima do gráfico. Este algoritmo encontra o subconjunto de arestas que inclui todos os vértices do gráfico, de modo que a soma dos pesos das arestas possa ser minimizada.
indústria e fábrica
Para saber mais sobre o algoritmo do prim, você pode clicar no link abaixo - https://www.javatpoint.com/prim-algorithm
Algoritmo de Kruskal - Este algoritmo também é usado para encontrar a árvore geradora mínima para um grafo ponderado conectado. O algoritmo de Kruskal também segue uma abordagem gananciosa, que encontra uma solução ótima em cada estágio, em vez de focar em um ótimo global.
Para saber mais sobre o algoritmo do prim, você pode clicar no link abaixo - https://www.javatpoint.com/kruskal-algorithm
Então, isso é tudo sobre o artigo. Espero que o artigo seja útil e informativo para você. Aqui, discutimos a árvore geradora e a árvore geradora mínima junto com suas propriedades, exemplos e aplicações.