Calculadora de Árvore Geradora Mínima

Bem-vindo à Calculadora de Árvore Geradora Mínima, uma ferramenta interativa para computar a AGM de um grafo ponderado usando o algoritmo de Kruskal ou Prim. Esteja você estudando teoria dos grafos, projetando infraestrutura de rede ou otimizando a alocação de recursos, esta calculadora fornece uma exploração visual passo a passo de dois algoritmos fundamentais em otimização combinatória.

O que é uma Árvore Geradora Mínima (AGM)?

Uma Árvore Geradora Mínima de um grafo conectado, não direcionado e ponderado é um subconjunto de arestas que:

• Conecta todos os vértices juntos (geradora)
• Não contém ciclos (árvore)
• Tem o menor peso total de aresta possível

Para um grafo com V vértices, uma AGM sempre tem exatamente V - 1 arestas. Se o grafo estiver desconectado, o resultado é uma Floresta Geradora Mínima — uma coleção de AGMs para cada componente conectado.

Algoritmo de Kruskal

O algoritmo de Kruskal é um algoritmo ávido baseado em arestas que constrói a AGM processando as arestas em ordem crescente de peso. Ele usa uma estrutura de dados Union-Find (União-Busca) para detectar ciclos com eficiência.

Pseudocódigo de Kruskal

Algoritmo de Prim

O algoritmo de Prim é um algoritmo ávido baseado em vértices que expande a AGM a partir de um vértice inicial. A cada passo, ele adiciona a aresta mais barata que conecta um vértice na árvore a um vértice fora da árvore.

Pseudocódigo de Prim

Kruskal vs. Prim: Quando usar qual?

Como usar esta calculadora

1. Defina as arestas do seu grafo: Insira as arestas no formato nó1, nó2, peso, uma por linha. A AGM opera em grafos não direcionados, então cada aresta funciona em ambas as direções.
2. Escolha um algoritmo: Selecione Kruskal para grafos esparsos ou Prim para grafos densos. Ambos produzem uma AGM ótima.
3. Defina o nó inicial (apenas Prim): Opcionalmente, especifique onde o algoritmo de Prim começa. Isso afeta a ordem de seleção das arestas, mas não o peso total da AGM.
4. Calcule a AGM: Clique em "Encontrar AGM" para executar o algoritmo. Explore a visualização interativa, a tabela de arestas e o rastreamento passo a passo.
5. Percorra os passos: Use os botões Próximo/Anterior para observar a execução do algoritmo passo a passo, com destaque no canvas em tempo real.

Entendendo os resultados

Tabela de Arestas da AGM

Mostra cada aresta selecionada para a AGM, na ordem em que foram adicionadas, junto com os pesos individuais e o peso total da AGM.

Visualização do Grafo

O canvas interativo exibe seu grafo com elementos codificados por cores:

• Nós e arestas verdes = Parte da AGM
• Destaques em laranja = Atualmente sendo examinado
• Elementos cinzas = Ainda não fazem parte da AGM

Rastreamento Passo a Passo

Mostra cada decisão do algoritmo: qual aresta é examinada, se foi aceita ou rejeitada (e por quê), e o estado atual da construção da AGM.

Aplicações Reais da AGM

Design de Rede

A aplicação mais clássica. Ao conectar nós (cidades, servidores, dispositivos elétricos) com o comprimento total mínimo de cabo, fibra ou tubo, a AGM fornece a solução ideal. Empresas de telecomunicações usam algoritmos baseados em AGM para minimizar o custo de infraestrutura.

Análise de Clusters

Em aprendizado de máquina e ciência de dados, o agrupamento baseado em AGM (como o agrupamento de ligação única) agrupa pontos de dados removendo as arestas mais longas da AGM. Isso produz clusters naturais sem a necessidade de pré-especificar o número de grupos.

Segmentação de Imagem

Algoritmos de visão computacional usam AGM para segmentar imagens em regiões significativas. Os pixels são nós, os pesos das arestas representam a diferença de cor/intensidade, e o corte das arestas da AGM separa objetos distintos.

Algoritmos de Aproximação

A AGM fornece uma aproximação de fator 2 para o Problema do Caixeiro Viajante (TSP) métrico. O peso da AGM é um limite inferior para a rota ideal do TSP, e dobrar as arestas da AGM fornece uma rota dentro de 2x do ideal.

Design de Circuito

O design de chips VLSI usa AGM (via variantes da árvore de Steiner) para minimizar o comprimento total do fio conectando componentes em uma placa de circuito, reduzindo o atraso do sinal e o custo de fabricação.

Propriedades Chave da AGM

• Propriedade do Corte: Para qualquer corte do grafo, a aresta de peso mínimo que cruza o corte está na AGM.
• Propriedade do Ciclo: Para qualquer ciclo no grafo, a aresta de peso máximo no ciclo NÃO está na AGM (assumindo pesos únicos).
• Unicidade: Se todos os pesos das arestas forem distintos, a AGM é única. Com pesos duplicados, pode haver várias AGMs válidas com o mesmo peso total.
• Subgrafo: A AGM é um subgrafo com V-1 arestas e sem ciclos.

Perguntas Frequentes

O que é uma Árvore Geradora Mínima (AGM)?

Uma Árvore Geradora Mínima é um subconjunto de arestas de um grafo conectado, não direcionado e ponderado que conecta todos os vértices juntos com o peso total de aresta mínimo possível, sem formar nenhum ciclo. Uma AGM possui exatamente V-1 arestas para um grafo com V vértices.

Qual é a diferença entre o algoritmo de Kruskal e o de Prim?

O algoritmo de Kruskal é baseado em arestas: ele classifica todas as arestas pelo peso e adiciona avidamente arestas que não criam ciclos, usando uma estrutura de dados Union-Find. O algoritmo de Prim é baseado em vértices: ele expande a AGM a partir de um nó inicial, adicionando sempre a aresta mais barata que conecta a árvore a um novo vértice, usando uma fila de prioridade. Ambos produzem AGMs ótimas, mas podem diferir na ordem de seleção das arestas.

Quando devo usar o algoritmo de Kruskal vs. o de Prim?

Kruskal é geralmente melhor para grafos esparsos (poucas arestas em relação aos nós) com complexidade de tempo O(E log E). Prim é melhor para grafos densos com complexidade de tempo O(E log V) usando um heap binário. Para grafos muito densos, Prim com um heap de Fibonacci atinge O(E + V log V).

Um grafo pode ter várias AGMs válidas?

Sim, um grafo pode ter múltiplas AGMs válidas se houver arestas com pesos iguais. Diferentes AGMs terão o mesmo peso total, mas podem incluir arestas diferentes. Kruskal e Prim podem produzir AGMs diferentes para o mesmo grafo, mas ambos terão o mesmo peso mínimo total.

Quais são as aplicações reais da AGM?

As AGMs são usadas em design de rede (minimizando o comprimento de cabos/fibras), layout de placas de circuito, análise de clusters, segmentação de imagem, construção de taxonomia, aproximação de problemas NP-difíceis como o Problema do Caixeiro Viajante (TSP) e construção de redes rodoviárias/oleodutos/elétricas com custo mínimo.

A AGM funciona em grafos desconectados?

Uma AGM verdadeira requer um grafo conectado. Se o grafo estiver desconectado, os algoritmos produzirão uma Floresta Geradora Mínima — uma coleção de AGMs, uma para cada componente conectado. Esta calculadora indicará quando o grafo não estiver totalmente conectado.

Recursos Adicionais

• Árvore Geradora Mínima - Wikipedia
• Algoritmo de Kruskal - Wikipedia
• Algoritmo de Prim - Wikipedia