Para que um grafo completo — nas aplicações ele não costuma ser esparso?

O grafo **euclidiano completo** é um modelo claro: em teoria dá para ligar qualquer par, e a MST escolhe as **n−1** ligações mais baratas sem ciclos. Em redes reais há menos arestas; os mesmos algoritmos valem lá, mas o caso denso mostra bem a ordenação de **Kruskal** e a varredura de candidatos de **Prim**.

A MST muda se se troca a raiz de Prim?

Se os pesos **não são únicos**, podem existir **vários** conjuntos distintos de arestas com o mesmo peso mínimo. Então raízes diferentes (e outra ordem) podem dar **MST distintas** como conjuntos de arestas, mas o **peso total** continua o mesmo: confere-se com **Kruskal**.

O que significa a linha vermelha tracejada no modo Kruskal?

É a aresta atual da lista ordenada que **não se pode** acrescentar: as duas pontas já estão na **mesma** componente dos conjuntos disjuntos; acrescentá-la fecharia um **ciclo** e o algoritmo a **omite**.

Árvore geradora mínima (Prim e Kruskal)

Pontos ao acaso no plano, grafo completo com pesos euclidianos: Prim passo a passo a partir da raiz ou Kruskal com conjuntos disjuntos; compara-se o peso total.

Sobre o modelo

A árvore geradora mínima liga todos os vértices sem ciclos e com a menor soma de pesos. n pontos pseudoaleatórios no plano (reproduzíveis a partir da semente da disposição). O grafo toma-se completo: o peso de uma aresta é a distância euclidiana entre vértices; qualquer árvore geradora tem n−1 arestas. Prim parte de uma raiz escolhida e em cada passo acrescenta a aresta mínima que cruza o corte «já na árvore / fora» (regra gulosa pela propriedade do corte). Kruskal ordena todas as arestas por peso (se empatam, por ordem lexicográfica das pontas, para ser determinístico) e percorre a lista com conjuntos disjuntos: a aresta é aceita se une componentes distintas e é rejeitada (destaque vermelho tracejado) se fecharia um ciclo. Os pesos totais da MST dos dois algoritmos coincidem.

Para quem: Matemática discreta e algoritmos: construções gulosas da MST, propriedades do corte e do ciclo, conjuntos disjuntos.

Conceitos-chave

árvore geradora mínima (MST)
algoritmo de Prim
algoritmo de Kruskal
propriedade do corte
propriedade do ciclo
conjuntos disjuntos (DSU)
grafo completo
pesos euclidianos

Como funciona

Grafo completo de n pontos no plano com pesos de distâncias euclidianas: Prim cresce a árvore a partir da raiz com a aresta mínima que cruza o corte; Kruskal percorre as arestas por peso crescente e os conjuntos disjuntos descartam a aresta se ela fecharia um ciclo; o peso total da MST coincide nos dois.

Perguntas frequentes

Para que um grafo completo — nas aplicações ele não costuma ser esparso?: O grafo euclidiano completo é um modelo claro: em teoria dá para ligar qualquer par, e a MST escolhe as n−1 ligações mais baratas sem ciclos. Em redes reais há menos arestas; os mesmos algoritmos valem lá, mas o caso denso mostra bem a ordenação de Kruskal e a varredura de candidatos de Prim.
A MST muda se se troca a raiz de Prim?: Se os pesos não são únicos, podem existir vários conjuntos distintos de arestas com o mesmo peso mínimo. Então raízes diferentes (e outra ordem) podem dar MST distintas como conjuntos de arestas, mas o peso total continua o mesmo: confere-se com Kruskal.
O que significa a linha vermelha tracejada no modo Kruskal?: É a aresta atual da lista ordenada que não se pode acrescentar: as duas pontas já estão na mesma componente dos conjuntos disjuntos; acrescentá-la fecharia um ciclo e o algoritmo a omite.

Continue com temas próximos desta categoria — ou todos os 48 em «Engenharia».

Toda a categoria →

NovoEscola

Labirintos e A*

Abrir o simulador

Labirintos perfeitos numa grade 40×28: percurso recursivo, Wilson, Eller ou Prim aleatório; resolve-se com A* (Manhattan, 4-vizinhança). Dá para desenhar paredes e mover o início e a meta.

NovoEscola

A* e Dijkstra

Abrir o simulador

Grade 40×28: A*, Dijkstra ou busca gulosa; heurísticas, 4- e 8-vizinhança, paredes e células caras; coloração do conjunto aberto e do fechado.

NovoEscola

Autômato finito

Abrir o simulador

Autômato de Moore para um semáforo: ciclo verde–amarelo–vermelho no temporizador ou avanço manual; grafo de estados.

NovoEscola

Planejador RRT

Abrir o simulador

O mesmo mapa de paredes 40×28: amostras ao acaso, nó mais próximo, passo com verificação de colisões, viés de amostragem rumo à meta; botão para comparar com A*.

NovoEscola

Cinemática inversa de um braço de 2 elos

Abrir o simulador

Braço plano de dois elos: alvo na tela, duas soluções — cotovelo para cima e cotovelo para baixo — e os ângulos θ₁ e θ₂.

NovoEscola

Deflexão de viga: carga unitária

Abrir o simulador

Viga biapoiada de Euler–Bernoulli com força P e carga w: deflexão analítica contra a integral do trabalho virtual ∫Mm/EI dx.

Árvore geradora mínima (Prim e Kruskal)

Sobre o modelo

Como funciona

Perguntas frequentes

Simuladores relacionados

Labirintos e A*

A* e Dijkstra

Autômato finito

Planejador RRT

Cinemática inversa de um braço de 2 elos

Deflexão de viga: carga unitária

Árvore geradora mínima (Prim e Kruskal)

Sobre o modelo

Como funciona

Perguntas frequentes