Podemos afirmar que o caminho entre dois vértices de um grafo que faz parte da árvore geradora mínima é o caminho mais curto entre esses dois vértices?
Passo 1
O enunciado pergunta se, em um grafo com arestas ponderadas, o caminho que liga dois vértices dentro da árvore geradora mínima (MST) sempre coincide com o caminho de menor peso entre esses mesmos vértices no grafo original. Os conteúdos envolvidos são: definição de árvore geradora mínima e definição de caminho mínimo.
Passo 2
Uma árvore geradora mínima (MST) de um grafo é uma subárvore que conecta todos os vértices com o menor peso total possível. O critério de otimização aqui é global, ou seja, minimizamos a soma de todas as arestas incluídas na árvore.
Um caminho mínimo entre dois vértices em um grafo é uma sequência de arestas que liga esses vértices de modo que a soma dos pesos seja a menor possível. Aqui o critério é local, focado apenas naquele par de vértices.
Um caminho mínimo entre dois vértices em um grafo é uma sequência de arestas que liga esses vértices de modo que a soma dos pesos seja a menor possível. Aqui o critério é local, focado apenas naquele par de vértices.
Passo 3
Como a MST escolhe arestas para minimizar o peso total da árvore, ela pode optar por caminhos indiretos entre certos pares, desde que isso ajude a reduzir o peso global. Já o caminho mínimo busca minimizar exatamente o trecho entre dois vértices, sem considerar o impacto sobre o resto da árvore.
Passo 4
Para ver por que eles diferem, considere o grafo com vértices
e arestas e pesos:
Passo 5
No grafo original, o caminho mínimo de
a
é a aresta direta
com peso
. Mas a MST do grafo escolhe as arestas de peso
e
(isto é,
e
) para minimizar o peso total
, deixando de lado a aresta
. Nessa MST, o caminho de
a
passa por
e tem peso total
, maior que
.
Resposta
Não. Em geral, o caminho entre dois vértices na árvore geradora mínima não coincide com o caminho mínimo do grafo original.