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.

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 u,v,x e arestas e pesos:
w(u,v)=2, w(u,x)=1, w(x,v)=2

Passo 5

No grafo original, o caminho mínimo de u a v é a aresta direta (u,v) com peso 2. Mas a MST do grafo escolhe as arestas de peso 1 e 2 (isto é, (u,x) e (x,v)) para minimizar o peso total 1+2=3, deixando de lado a aresta (u,v). Nessa MST, o caminho de u a v passa por x e tem peso total 1+2=3, maior que 2.

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.

Exercícios relacionados