Dado um grafo simples não-orientado G com pesos nas arestas, o problema da árvore geradora minimax consiste em encontrar uma árvore geradora T d...

O algoritmo eficiente para resolver o problema da árvore geradora minimax é o algoritmo de Kruskal. Ele funciona da seguinte maneira: 1. Ordena as arestas do grafo em ordem crescente de peso. 2. Inicializa uma floresta F vazia. 3. Para cada aresta (u, v) em ordem crescente de peso: 1. Se u e v estão em componentes diferentes de F, adiciona a aresta (u, v) a F. 4. A árvore geradora minimax é a árvore resultante de F. A corretude do algoritmo de Kruskal pode ser demonstrada por indução matemática. A cada iteração do algoritmo, adicionamos a aresta de menor peso que conecta duas componentes diferentes da floresta. Como as arestas são adicionadas em ordem crescente de peso, a aresta adicionada em cada iteração é a de menor peso possível que conecta duas componentes diferentes. Portanto, a árvore geradora resultante é a de menor peso possível que conecta todos os vértices do grafo. Além disso, como estamos adicionando arestas de menor peso possível, a aresta de maior peso da árvore geradora resultante também é a de maior peso possível dentre todas as árvores geradoras possíveis.