Estrutura de dados e algoritmos - árvore de abrangência

Uma árvore geradora é um subconjunto do Gráfico G, que possui todos os vértices cobertos com o número mínimo possível de arestas. Portanto, uma árvore geradora não tem ciclos e não pode ser desconectada.

Por essa definição, podemos chegar à conclusão de que todo Grafo G conectado e não direcionado tem pelo menos uma árvore geradora. Um gráfico desconectado não possui nenhuma árvore estendida, pois não pode ser estendido a todos os seus vértices.

Encontramos três árvores abrangentes em um gráfico completo. Um gráfico não direcionado completo pode ter no máximonn-2 número de árvores abrangentes, onde né o número de nós. No exemplo abordado acima,n is 3, conseqüentemente 33−2 = 3 árvores abrangentes são possíveis.

Propriedades Gerais de Spanning Tree

Agora entendemos que um gráfico pode ter mais de uma árvore de abrangência. A seguir estão algumas propriedades da árvore de abrangência conectada ao gráfico G -

  • Um grafo conectado G pode ter mais de uma árvore geradora.

  • Todas as árvores geradoras possíveis do grafo G têm o mesmo número de arestas e vértices.

  • A Spanning Tree não possui nenhum ciclo (loops).

  • Remover uma aresta da árvore de abrangência fará com que o gráfico seja desconectado, ou seja, a árvore de abrangência é minimally connected.

  • Adicionar uma aresta à árvore geradora criará um circuito ou loop, ou seja, a árvore geradora é maximally acyclic.

Propriedades matemáticas da árvore de expansão

  • Spanning tree tem n-1 bordas, onde n é o número de nós (vértices).

  • De um gráfico completo, removendo o máximo e - n + 1 bordas, podemos construir uma árvore geradora.

  • Um gráfico completo pode ter no máximo nn-2 número de árvores abrangentes.

Assim, podemos concluir que as árvores geradoras são um subconjunto do Gráfico G conectado e que os gráficos desconectados não possuem árvore geradora.

Aplicação de Spanning Tree

Spanning tree é basicamente usado para encontrar um caminho mínimo para conectar todos os nós em um gráfico. A aplicação comum de árvores geradoras são -

  • Civil Network Planning

  • Computer Network Routing Protocol

  • Cluster Analysis

Vamos entender isso por meio de um pequeno exemplo. Considere a rede da cidade como um grande gráfico e agora planeja implantar linhas telefônicas de forma que, no mínimo, possamos nos conectar a todos os nós da cidade. É aqui que a árvore de abrangência entra em cena.

Árvore de abrangência mínima (MST)

Em um gráfico ponderado, uma árvore de abrangência mínima é uma árvore de abrangência que tem peso mínimo do que todas as outras árvores de abrangência do mesmo gráfico. Em situações do mundo real, esse peso pode ser medido como distância, congestionamento, carga de tráfego ou qualquer valor arbitrário denotado para as bordas.

Algoritmo de árvore de abrangência mínima

Devemos aprender sobre dois algoritmos de spanning tree mais importantes aqui -

Ambos são algoritmos gananciosos.