Algoritmos para Grafos  |  Índice

Algoritmo de Kruskal

Este capítulo discute o célebre algoritmo de Kruskal para o problema da MST. (O algoritmo foi publicado por Joseph Kruskal em 1956.)

Problema:  Encontrar uma MST (árvore geradora de custo mínimo) de um grafo não-dirigido com custos nas arestas.

Os custos são números inteiros arbitrários (positivos e negativos).  Os conceitos básicos relativos ao problema da MST podem ser vistos no capítulo geral sobre árvores geradoras de custo mínimo.

O problema tem solução se e somente se o grafo é conexo. Assim, vamos tratar apenas de grafos não-dirigido conexos. (Mas veja exercício abaixo.)

Sumário:

O algoritmo

O algoritmo de Kruskal faz crescer uma floresta geradora até que ela se torne conexa.  A floresta cresce de modo a satisfazer o critério de minimalidade de MSTs baseado em circuitos.

Para discutir os detalhes, precisamos de um pouco de terminologia.  Uma sub­floresta de um grafo não-dirigido G é qualquer floresta que seja sub­grafo não-dirigido de G.  Uma floresta geradora de G é qualquer sub­floresta que tenha o mesmo conjunto de vértices que G.

Uma aresta a de G é externa a uma floresta geradora F se a não pertence a F e o grafo  F + a  é uma floresta, ou seja, um grafo sem circuitos.  Portanto, uma aresta é externa a F se tem uma ponta em uma componente conexa de F e outra ponta em outra componente.

Podemos agora tratar do algoritmo.  [!] Cada iteração do algoritmo de Kruskal começa com uma floresta geradora  F  de G.  O processo iterativo é muito simples: enquanto existe alguma aresta externa,

  1. escolha uma aresta externa que tenha custo mínimo;
  2. seja a a aresta escolhida;
  3. acrescente aF.

No início da primeira iteração, cada componente conexa da floresta F tem apenas um vértice.  No fim do processo iterativo, F é conexa, uma vez que G é conexo e não há arestas externas a F.

Como se vê, o algoritmo tem caráter guloso: em cada iteração, abocanha a aresta que parece mais promissora localmente sem se preocupar com o efeito global dessa escolha.  O algoritmo foi projetado pensando no critério de minimalidade de MSTs baseado em circuitos.

the-web/kruskal-meyavuz.png

Exemplo A.  O vídeo Kruskal's Algorithm Animation no YouTube aplica o algoritmo de Kruskal a um grafo cujos vértices são pontos aleatórios no plano. O grafo é completo e o custo de cada aresta é a distância geométrica entre suas pontas.

Sedgewick-part5-java/kruskal-fig-20-13-a.png

Sedgewick-part5-java/kruskal-fig-20-13-h.png

Exemplo B.  Considere o problema de encontrar uma MST no grafo não-dirigido com custos nas arestas definido a seguir.  (Para simplificar o rastreamento, as arestas são apresentadas em ordem crescente de custo.)  Em seguida, veja o rastreamento da execução do algoritmo de Kruskal. Cada linha da tabela registra, no início de cada iteração, as arestas da floresta e o custo da floresta.

3-5 1-7 6-7 0-2 0-7 0-1 3-4 4-5 4-7 0-6 4-6 0-5 
  0   1   2   3   4   5   6   7   8   9   9  11 
floresta                     custo
-                             0               
3-5                           0+0
3-5 1-7                       0+1
3-5 1-7 6-7                   1+2
3-5 1-7 6-7 0-2               3+3
3-5 1-7 6-7 0-2 0-7           6+4
3-5 1-7 6-7 0-2 0-7 3-4      10+6
3-5 1-7 6-7 0-2 0-7 3-4 4-7  16+8

A última linha dá as arestas de uma MST. Resumindo, o algoritmo de Kruskal escolhe as seguintes arestas para formar uma MST:

3-5 1-7 6-7 0-2 0-7     3-4     4-7              
  0   1   2   3   4       6       8 

(Os espaços em branco correspondem às arestas que foram rejeitadas porque formam um circuito com as arestas escolhidas em iterações anteriores.)

Exercícios 1

  1. Para que serve o algoritmo de Kruskal?  Que problema resolve?
  2. ★ Como começa cada iteração do algoritmo de Kruskal?  (Cuidado! Não quero uma descrição das ações que ocorrem no início de uma iteração! Quero saber, isto sim, quais as informações disponíveis no início de uma iteração genérica, antes que a execução da iteração comece.)
  3. Considere o grafo não-dirigido completo cujos vértices são os seguintes pontos no plano:  (2,1) (2,5) (1,6) (6,6) (3,3) (3,4) (5,2) (5,7).  O custo de cada aresta é o comprimento do segmento de reta que une os pontos. Dê a ordem em que o algoritmo de Kruskal descobre as arestas de uma MST.
  4. [Sedgewick 20.48] Considere o grafo não-dirigido conexo cujos vértices são os pontos no plano indicados a seguir. Suponha que as arestas do grafo são  1-0 3-5 5-2 3-4 5-1 0-3 0-4 4-2 2-3  e o custo de cada aresta v-w é igual ao comprimento do segmento de reta que liga os pontos vw no plano.
      0     1     2     3     4     5
    (1,3) (2,1) (6,5) (3,4) (3,7) (5,3)
    

    Aplique o algoritmo de Kruskal a esse grafo. Exiba uma figura do grafo e da floresta no início de cada iteração. Dê a ordem em que o algoritmo descobre as arestas da MST.

  5. [Sedgewick Property 20.4] Correção e invariantes.  Prove que o algoritmo de Kruskal está correto. (Sugestão: Use o critério de minimalidade baseado em circuitos. Mostre que no início de cada iteração, para cada aresta e de G, se F + e tem um circuito então o custo de e é máximo nesse circuito.)
  6. Discuta a seguinte variante do algoritmo de Kruskal. Cada iteração do algoritmo começa com uma floresta geradora F de G.  Enquanto F não for conexa, escolha uma aresta de custo mínimo dentre as que não estão em F e acrescente-a a F.
  7. A função abaixo é uma implementação do algoritmo de Kruskal?  Em caso afirmativo, quanto tempo ela consome?
    UGraph naiveK( UGraph G) { 
       UGraph F = UGRAPHinit( G->V);
       while (true) {
          int min = INFINITY;
          vertex x, y;
          for (vertex v = 0; v < G->V; ++v) 
             for (link a = G->adj[v]; a != NULL; a = a->next) {
                if (GRAPHreach( F, v, a->w)) continue;
                if (a->c < min) {
                   min = a->c;
                   x = v, y = a->w;
                }
             }
          if (min == INFINITY) 
             return F; 
          UGRAPHinsertEdge( F, x, y, min);
       }
    }
    
  8. Grafo desconexo.  Que acontece se o algoritmo de Kruskal for aplicado a um grafo não-dirigido desconexo?

Implementação ingênua do algoritmo

Para obter uma boa implementação do algoritmo de Kruskal, é preciso escolher duas estruturas de dados: uma para representar a floresta geradora (e a MST final) e uma estrutura auxiliar que permita decidir facilmente se uma aresta é externa a uma dada floresta geradora.

Como representar a floresta geradora?  A representação por vetor de pais que usamos em outros algoritmos é incômoda no caso do algoritmo de Kruskal. Adotaremos como representação uma simples lista das arestas da floresta, armazenada num vetor. Cada aresta v-w será representada por uma struct edge, construída por uma função EDGE():

typedef struct { 
    vertex v, w; 
    int c; 
} edge;
static edge EDGE( vertex v, vertex w, int c) {
   edge e;
   e.v = v, e.w = w; e.c = c;
   return e;
}

Para decidir arestas externas, usaremos um vetor de chefes assim construído:  (1) eleja um dos vértices de cada componente conexa da floresta para ser o chefe da componente;  (2) para cada vértice v do grafo, denote por chefe[v] o chefe da componente que contém v;  (3) agora, uma aresta v-w é externa à floresta se e somente se chefe[v] ≠ chefe[w].

Decididas essas estruturas, podemos escrever uma implementação simples do algoritmo de Kruskal. A função UGRAPHmstK0() abaixo recebe um grafo não-dirigido conexo G e armazena no vetor mst[] as arestas de uma MST do grafo. É claro que mst[] terá G->V-1 elementos.  A função usa uma constante INFINITY de valor maior que o custo de qualquer aresta do grafo.

#define UGraph Graph

void UGRAPHmstK0( UGraph G, edge mst[]) 
{ 
   vertex chefe[1000];
   for (vertex v = 0; v < G->V; ++v) 
      chefe[v] = v;
   int k = 0;
   while (true) {
      // a floresta tem arestas mst[0..k-1]
      int min = INFINITY;
      vertex x, y;
      for (vertex v = 0; v < G->V; ++v) {
         for (link a = G->adj[v]; a != NULL; a = a->next) {
            vertex w = a->w; int c = a->c;
            if (v < w && chefe[v] != chefe[w] && c < min) {
               min = c;
               x = v, y = w;
            }
         }
      }
      if (min == INFINITY) return; 
      mst[k++] = EDGE( x, y, min);
      vertex v0 = chefe[x], w0 = chefe[y]; // 1
      for (vertex v = 0; v < G->V; ++v)    // 2
         if (chefe[v] == w0)               // 3
            chefe[v] = v0;                 // 4
   }
}

As linhas 1 a 4 fazem a união de duas componentes conexas da floresta: a componente que contém x absorve a componente que contém y e as duas passam a ter o mesmo chefe v0.

Essa função é muito lenta. Ela consome  V (E + V)  unidades de tempo, no pior caso, para processar um grafo não-dirigido com V vértices e E arestas.  Como E < V2, podemos dizer que o consumo de tempo é limitado por V3.

Sedgewick-part5-java/kruskal-fig-20-13-a.png

Sedgewick-part5-java/kruskal-fig-20-13-h.png

Exemplo C.  Voltamos a examinar o grafo não-dirigido do exemplo A. Veja a lista de arestas do grafo (em ordem crescente de custos).  Cada linha da tabela seguinte registra o estado de coisas no início de uma iteração do while na função UGRAPHmstK0():  a aresta mais recente de mst[], o vetor chefe[], e o custo da floresta.

3-5 1-7 6-7 0-2 0-7 0-1 3-4 5-4 4-7 0-6 4-6 0-5 
  0   1   2   3   4   5   6   7   8   9   9  11 
          chefe[]           custo da   
mst[k-1]  0 1 2 3 4 5 6 7   floresta   
                           
          0 1 2 3 4 5 6 7    0
3-5       0 1 2 3 4 3 6 7    0+0
1-7       0 1 2 3 4 3 6 1    0+1
6-7       0 6 2 3 4 3 6 6    1+2
0-2       0 6 0 3 4 3 6 6    3+3
0-7       0 0 0 3 4 3 0 0    6+4
3-4       0 0 0 3 3 3 0 0   10+6
4-7       3 3 3 3 3 3 3 3   16+8

Resumindo, o algoritmo de Kruskal escolhe as seguintes arestas para formar uma MST:

3-5 1-7 6-7 0-2 0-7     3-4     4-7              
  0   1   2   3   4       6       8 

Exercícios 2

  1. Verifique que UGRAPHmstK0() é uma implementação correta do algoritmo de Kruskal.
  2. [Alunos de Juan Gutiérrez Alva]  O que acontece se as 4 últimas linhas de UGRAPHmstK0() forem trocadas pelo seguinte código mais simples?
    for (v = 0; v < G->V; ++v) 
       if (chefe[v] == chefe[y])
           chefe[v] = chefe[x];
    
  3. Mostre que a função UGRAPHmstK0() consome no máximo  V (E + V)  unidades de tempo.
  4. Escreva uma variante de UGRAPHmstK0() que comece por colocar as arestas em ordem crescente de custos. Quanto tempo essa variante consome?
  5. [Sedgewick 20.18]  Vetor de pais. Escreva uma função UGRAPHmstK0pai() que invoque UGRAPHmstK0() e depois calcule um vetor de pais que represente a árvore geradora que UGRAPHmstK0() depositou no vetor mst[].

Implementação eficiente com union-find

A função UGRAPHmstK0() é ineficiente por dois motivos. Primeiro, porque cada iteração examina todas as arestas do grafo à procura da aresta externa mais barata. Segundo, porque cada iteração examina todos os vértices do grafo para atualizar o vetor de chefes. Para corrigir a primeira ineficiência, basta colocar as arestas em ordem crescente de custo e então examinar cada aresta uma só vez. A segunda ineficiência é mais difícil de corrigir: será preciso recorrer à estrutura union-find, que usa um vetor de chefes mais flexível.

A função UGRAPHmstK1() começa por invocar uma função UGRAPHedges() que armazena as E arestas do grafo num vetor e[0..E-1].  Em seguida, invoca uma função sort() para rearranjar e[0..E-1] em ordem crescente de custos.   Finalmente, examina as arestas na ordem em que elas estão em e[0..E-1] e escolhe as que farão parte da MST.

#define UGraph Graph
/* A função UGRAPHmstK1() recebe 
   um grafo não-dirigido conexo G 
   com custos arbitrários nas arestas
   e calcula uma MST 
   de G. 
   O grafo é dado por suas 
   listas de adjacência.
   A função armazena as arestas 
   da MST no vetor mst[0..V-1],
   alocado pelo usuário. 
   (A função implementa o algoritmo de Kruskal.
   
   O código foi copiado, com ligeiras modificações, 
   do programa 20.5 de Sedgewick.) */
void UGRAPHmstK1( UGraph G, edge mst[]) 
{ 
   edge e[500000]; 

   UGRAPHedges( G, e);
   int E = G->A/2; 
   sort( e, 0, E-1); 

   UFinit( G->V);
   int k = 0;
   for (int i = 0; k < G->V-1; ++i) {
      vertex v0 = UFfind( e[i].v);
      vertex w0 = UFfind( e[i].w);
      if (v0 != w0) {
         UFunion( v0, w0);
         mst[k++] = e[i];
      }
   }
}
/* Esta função armazena as arestas do grafo não-dirigido G 
   no vetor e[0..E-1]. */
static void UGRAPHedges( UGraph G, edge e[]) 
{
   int i = 0;
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next) 
         if (v < a->w) 
            e[i++] = EDGE( v, a->w, a->c);
}

As funções UFinit(), UFfind() e UFunion() fazem o seguinte:

Para fazer uma implementação eficiente das funções UFfind() e UFunion(), vamos usar as ideias do tipo-de-dados abstrato union-find[O union-find é discutida na seção 1.3 do volume 1 do livro de Sedgewick. Também aparece no programa 4.8 do livro. A variante discutida a seguir é menos pura que a de Sedgewick, mas mais apropriada ao nosso contexto.]

Union-find.  A estrutura union-find é uma flexibilização ch[0..V-1] do vetor de chefes que já usamos acima.  A flexibilização consiste no seguinte:  para cada vértice v, o vértice ch[v] não mais precisa ser o chefe de v, desde que seja possível chegar ao chefe iterando ch[], ou seja, fazendo ch[ch[v]], ch[ch[ch[v]]], etc.  Com essa flexibilização, ch[v] passa a ser uma espécie de superior imediato de v.   É claro que v é um chefe se e somente se ch[v] ≡ v.

Digamos agora que os chefes de v e w são v0 e w0 respectivamente. Se esses dois vértice são diferentes, a função UFunion() une as componente chefiadas por v0w0 em uma só tornando v0 o superior imediato de w0 ou vice versa.  Para evitar que a estrutura fique muito alta (isto é, que seja necessário iterar ch[] muitas vezes para chegar a um chefe), a função UFunion() faz com que o chefe da maior das duas componente seja também o chefe da menor.  (Esse truque é conhecido como union-by-rank.)  O tamanho das componentes é mantido em um vetor sz[]:  se v0 é um chefe então  sz[v0]  é o número de vértices chefiados por v0.

/* A função UFfind() devolve o chefe de v
   (ou seja, o chefe da componente conexa que contém v
   na floresta geradora mst[0..k-1]). 
   A função UFunion() recebe dois chefes distintos 
   v0w0
   e faz a união das correspondentes componentes. */
static vertex ch[1000];
static int sz[1000];

void UFinit( int V) { 
   for (vertex v = 0; v < V; ++v) { 
      ch[v] = v; 
      sz[v] = 1; 
   }
}

vertex UFfind( vertex v) { 
   vertex v0 = v; 
   while (v0 != ch[v0]) 
      v0 = ch[v0]; 
   return v0; 
}

void UFunion( vertex v0, vertex w0) { 
   if (sz[v0] < sz[w0]) { 
      ch[v0] = w0; 
      sz[w0] += sz[v0]; 
   }
   else { 
      ch[w0] = v0; 
      sz[v0] += sz[w0]; 
   }
}

Com essa implementação, a altura de cada estrutura de superiores imediatos (ou seja, o número de repetições de ch[] necessário para se chegar a um chefe) não passa de log V, sendo V o número de vértices de G. Assim, cada invocação de UFfind() e UFunion() consome  log V  unidades de tempo no máximo.  (Poderíamos fazer uma implementação mais eficiente embutindo o truque path compression no código de UFfind().  Isso faria com que cada operação consumisse apenas log* V unidade de tempo no pior caso. Mas a função UGRAPHmstK1() não se beneficiaria desse melhoramento porque a primeira parte do algoritmo, que coloca as arestas em ordem, consome tempo E log V.)

Sedgewick-part5-java/kruskal-fig-20-13-a.png

Sedgewick-part5-java/kruskal-fig-20-13-h.png

Exemplo D.  Considere novamente o grafo não-dirigido do exemplo C. Veja abaixo o vetor e[0..E-1] de arestas do grafo, já em ordem crescente de custos.  Logo em seguida, veja os vetores mst[], ch[] e sz[] no início das sucessivas iterações da função UGRAPHmstK1():

3-5 1-7 6-7 0-2 0-7 0-1 3-4 5-4 4-7 0-6 4-6 0-5 
  0   1   2   3   4   5   6   7   8   9   9  11 
mst[]                         ch[]              sz[]
0   1   2   3   4   5   6     0 1 2 3 4 5 6 7   0 1 2 3 4 5 6 7
                                                               
                              0 1 2 3 4 5 6 7   1 1 1 1 1 1 1 1
3-5                           0 1 2 3 4 3 6 7   1 1 1 2 1 1 1 1
3-5 1-7                       0 1 2 3 4 3 6 1   1 2 1 2 1 1 1 1
3-5 1-7 6-7                   0 1 2 3 4 3 1 1   1 3 1 2 1 1 1 1
3-5 1-7 6-7 0-2               0 1 0 3 4 3 1 1   2 3 1 2 1 1 1 1
3-5 1-7 6-7 0-2 0-7           1 1 0 3 4 3 1 1   2 5 1 2 1 1 1 1
3-5 1-7 6-7 0-2 0-7 3-4       1 1 0 3 3 3 1 1   2 5 1 3 1 1 1 1
3-5 1-7 6-7 0-2 0-7 3-4 4-7   1 1 0 1 3 3 1 1   2 8 1 3 1 1 1 1

Veja a evolução da estrutura union-find à medida que arestas são acrescentadas à MST:

                    1   
                          
                           
                 3  7  6  0
                          
                          2
               5   4
          
          

      3-5 
                    1   
                          
                           
                 3  7  6  0
                _|        
               |          2
               5   4
          
          

      1-7 
                    1   
                    |     
                    |      
                 3  7  6  0
                _|        
               |          2
               5   4
          
          

      6-7 
                    1   
                    |__   
                    |  |   
                 3  7  6  0
                _|        
               |          2
               5   4
          
          

      0-2 
                    1   
                    |__   
                    |  |   
                 3  7  6  0
                _|        |
               |          2
               5   4
          
          

      0-7 
                    1   
                    |_____
                    |  |  |
                 3  7  6  0
                _|        |
               |          2
               5   4
          
          

      0-1 
      3-4 
                    1   
                    |_____
                    |  |  |
                 3  7  6  0
                _|_       |
               |   |      2
               5   4
          
          

      4-5 
      4-7 
                    1   
                  __|_____
                 |  |  |  |
                 3  7  6  0
                _|_       |
               |   |      2
               5   4
          

      0-6 
      4-6 
      0-5 

 

Desempenho.  Digamos que o grafo tem V vértices e E arestas.  Então a função sort() consome tempo limitado por  E log E.  O restante do código de UGRAPHmstK1() consiste em 2V invocações de UFfind() e V invocações de UFunion(), e portanto consome tempo limitado por V log V.  Como log E < 2 log V,  podemos dizer que o consumo de UGRAPHmstK1() é limitado por

(E + V) log V

no pior caso. Como o grafo é conexo, temos EV−1 e portanto podemos dizer que o algoritmo consome tempo proporcional a E log V no pior caso.  Diz-se que o algoritmo é linearítmico.

Exercícios 3

  1. Aplique a função UGRAPHmstK1() ao grafo não-dirigido com custos descrito a seguir. Faça uma figura da estrutura union-find definida por ch[].
    3-4 2-4 5-6 0-2 0-3 2-3 4-5 4-6 1-2 3-5 1-6 1-4
      2   3   4   5   8  10  12  14  16  18  26  30
    
  2. Aplique a função UGRAPHmstK1() ao grafo não-dirigido com custos descrito a seguir. Faça uma figura da estrutura union-find definida por ch[].
    0-1 2-3 0-3 4-5 5-6 5-7 6-8 2-7
      1   2   3   4   5   6   7   8
    
  3. Na implementação da estrutura union-find dada acima, é verdade que, para todo vértice v, o valor de ch[v] muda no máximo uma vez durante a execução do algoritmo de Kruskal?
  4. Na implementação da estrutura union-find dada acima, é verdade que, para todo vértice v, o valor de sz[v] é igual ao número de vértices da árvore radicada da estrutura union-find que contém v?
  5. Escreva uma versão all-in-one da função UGRAPHmstK1() que incorpore, tanto quanto razoável, o código das funções de manipulação da estrutura union-find.
  6. Alocação dinâmica.  Reescreva a função UGRAPHmstK1() substituindo a alocação estática de e[] por alocação dinâmica (e correspondente desalocação).
  7. ★ Escreva uma versão simplificada da função UGRAPHmstK1() que receba um grafo não-dirigido G possivelmente desconexo e devolva o custo — apenas o custo — de uma floresta geradora maximal de custo mínimo de G.  (Cada componente conexa da floresta será uma MST de uma das componentes de G.)  Escreva o código do union-find tão embutido quanto possível no código de sua função.  Escreva código enxuto, sem variáveis supérfluas.
  8. [Sedgewick 20.50]  Escreva uma implementação da estrutura union-find em que a operação find consome tempo constante (ou seja, independente de V) e a operação union consome tempo proporcional a  log V.

Exercícios 4

  1. [Sedgewick-Wayne 4.3.24]  Escreva um algoritmo que calcule uma MST de um grafo não-dirigido conexo da seguinte maneira. Comece com um sub­grafo contendo todas as arestas. Examine as arestas do sub­grafo uma a uma, em ordem decrescente de custo. Remova a aresta se isso não desconectar o sub­grafo. Prove que o seu algoritmo está correto. Quanto tempo o seu algoritmo consome no pior caso?
  2. [Sedgewick-Wayne 4.3.14]  Seja M uma MST de um grafo não-dirigido conexo G com custos nas arestas. Seja e uma aresta de G. Como é possível encontrar, em tempo limitado pelo número E de arestas de G, uma MST de Ge?
  3. [Sedgewick-Wayne 4.3.16]  Seja M uma MST de um grafo não-dirigido conexo G com custos nas arestas. Dados dois vértices v e w que não são adjacentes em G, imagine acrescentar a G uma nova aresta e com pontas vw. Que custo devemos atribuir a e para que e faça parte de uma MST de G+e?
  4. [Sedgewick-Wayne 4.3.32]  Seja G um grafo não-dirigido conexo com custos nas arestas e seja B um conjunto de arestas de G. Suponha que o grafo não-dirigido induzido por B não tem circuitos. Queremos encontrar uma sub­árvore geradora de custo mínimo dentre aquelas que contêm B. Descreva um algoritmo eficiente para resolver o problema.
  5. Use a estrutura union-find para construir uma árvore aleatória com V vértices. Todas as árvores com vértices 0..V-1 devem ser igualmente prováveis.  (Veja exercício no capítulo Circuitos e florestas.)
  6. Desafio.  Encontre um algoritmo linear para o problema da MST, ou seja, um algoritmo que consuma apenas V+E unidades de tempo para calcular uma MST num grafo não-dirigido conexo com V vértices e E arestas.
  7. Árvore minmax.  Uma árvore minmax de um grafo não-dirigido conexo com custos nas arestas é uma árvore geradora com a seguinte propriedade: a aresta mais cara da árvore é a mais barata possível.  Mostre que toda MST é uma árvore minmax.
  8. [Sedgewick 21.30]  Caminho minmax.  Digamos que o gargalo de um caminho é o custo de sua aresta mais cara.  Mostre que toda MST T de um grafo não-dirigido com custos nas arestas tem a seguinte propriedade:  para todo par (v,w) de vértices, o caminho entre v e w em T é um caminho de gargalo mínimo dentre todos os que ligam v a w no grafo.