Árvore geradora mínima: Kruskal e Prim

Prima Doze aldeias e acompanhe Kruskal passo a passo. O algoritmo percorre as 66 estradas possíveis da mais curta para a mais longa: K–L, com 13,89 km, é aceite de imediato; C–D e B–C são rejeitadas porque o caminho desenhado a vermelho já liga as respetivas extremidades. Mude para Prim, que faz crescer uma única rede a partir de A. As estradas surgem por outra ordem, K–L fica para o fim e as mesmas duas são rejeitadas. O resultado continua a ser as mesmas 11 estradas e os mesmos 199,04 km. Ambos obedecem à propriedade do corte: divida os pontos em dois grupos como quiser; se não houver duas estradas com o mesmo comprimento, a estrada mais curta entre os grupos pertence à árvore geradora mínima. Se a omitirmos, o caminho que a árvore oferece entre as suas extremidades terá de atravessar o corte por uma estrada mais longa. Substituir uma pela outra encurta a árvore. Em cada passo de Prim, a rede sombreada constitui um dos lados de um corte. Prima agora Vizinho mais próximo. Este método repete os passos de Prim com uma alteração: procura a partir da última aldeia alcançada, não a partir de toda a rede. No terceiro passo escolhe D–F, com 17,96 km, embora A–C atravesse o corte com apenas 17,67 km. Passa ao lado de A–C mais sete vezes e termina com mais 10,76%. Otakar Borůvka, o primeiro a resolver o problema, formulou-o em 1926 pensando na rede elétrica do sul da Morávia. Falou de pontos cujas “distâncias mútuas são diferentes”: é a mesma condição que impede Kruskal e Prim de chegarem a respostas distintas.

Prima Um anel de cidades. Dez cidades rodeiam um lago, e a árvore segue a margem deixando de fora um troço: a abertura mais larga, entre J e A. Essas duas cidades ficam a 25,89 km em linha reta e a 128,30 km ao longo da árvore, uma distância 4,96 vezes maior, pois o único percurso entre elas atravessa a rede inteira. A linha roxa tracejada assinala este par; arraste qualquer cidade e será encontrado o novo maior desvio. Uma árvore geradora mínima reduz ao mínimo o comprimento total, mas nada garante quanto à distância entre cada par de cidades. Construir também a estrada de 25,89 km tornaria direta a viagem de A para J. Saber se a estrada adicional compensa é uma questão sobre percursos: o problema do caminho mais curto, desenvolvido na página dedicada ao algoritmo de Dijkstra.

Prima Três cidades. Estão separadas por 40 km, portanto a árvore mede 80,00 km. Uma junção central, onde três estradas se encontram a 120°, liga-as com 69,28 km, menos 13,40%. Esta redução corresponde a 1 − √3/2. Prima Quatro cidades: quadrado e duas junções pouparão 8,93%. Regresse ao triângulo e arraste C para baixo, em direção a A e B: quando o ângulo em C ultrapassa 120°, a junção coincide com C e deixa de haver qualquer vantagem. Encontrar as melhores junções é o problema da árvore de Steiner. Em 1968, Edgar Gilbert e Henry Pollak conjecturaram que o triângulo equilátero representa o pior caso: para qualquer conjunto de pontos no plano, a árvore de Steiner não teria comprimento inferior a √3/2 do comprimento da árvore geradora mínima. Du e Hwang publicaram uma demonstração em 1990. Em 2010, Innami e três colegas apresentaram indícios de que um passo essencial dessa demonstração falha. Em 2012, Ivanov e Tuzhilin, que apontavam lacunas desde 2002, escreveram que a conjectura continuava em aberto. Uma coletânea de 2025 sobre problemas em aberto relativos a árvores de Steiner ainda a inclui. Não se sabe se alguma disposição de pontos permite poupar mais do que os 13,40% do triângulo.