Matemática Discretapara Engenheiros

4. Prova de Correção

Esta parte formaliza o que afirmamos na Parte 1: o BFS calcula distâncias de menores caminhos em grafos não ponderados.

A prova é estrutural. A fila não é um detalhe de implementação: ela é a razão pela qual o argumento funciona.

4.1 O Que Deve Ser Provado

Seja G = (V, E) um grafo e s ∈ V a fonte. Defina δ(s, v) como a verdadeira distância de menor caminho (número de arestas) de s até v.

Devemos provar que o BFS calcula:

para todo vértice v alcançável a partir de s.

4.2 Invariante Principal

A prova se apoia em um invariante central:

Intuitivamente: a primeira vez que alcançamos v, nós o alcançamos pela camada mais curta.

Justificaremos isso usando a disciplina FIFO da fila (exploração em camadas).

4.3 Lema 1 — Distâncias Nunca Subestimam

Afirmação: Para todo vértice v, o BFS nunca subestima a distância verdadeira:

Esboço da prova

O BFS só atribui d[v] por meio de uma aresta (u, v) ∈ E:

Qualquer caminho até v passando por u tem comprimento pelo menos δ(s, u) + 1, então atribuir d[u] + 1 não pode ser menor do que o ótimo verdadeiro. Portanto, o BFS não produz distâncias menores do que a realidade.

4.4 Lema 2 — FIFO Garante Exploração em Camadas

A fila garante que os vértices sejam processados em ordem não decrescente de distância:

Por quê? Quando um vértice u é desenfileirado, todo vizinho recém-descoberto v recebe d[v] = d[u] + 1 e é colocado no final da fila. Assim, a fila forma camadas consecutivas.

Camada L0:  { s }                     d = 0
             |
Camada L1:  { vizinhos de s }         d = 1
             |
Camada L2:  { vizinhos de L1 }        d = 2
             |
Camada L3:  { vizinhos de L2 }        d = 3
...

4.5 Lema 3 — A Primeira Descoberta É Ótima

Afirmação: Quando v é descoberto pela primeira vez, o BFS atribui a verdadeira menor distância:

Prova (por contradição)

Suponha que o BFS descubra v pela primeira vez com d[v] > δ(s, v). Considere um menor caminho:

Então v_k-1 satisfaz δ(s, v_k-1) = δ(s, v) − 1, logo está em uma camada anterior. Pelo Lema 2, ele deve ser desenfileirado antes que qualquer vértice na camada δ(s, v) seja descoberto.

Quando o BFS processa v_k-1, ele examina a aresta (v_k-1, v) e atribuiria:

Contradição. Portanto, a primeira descoberta atribui a distância ótima.

4.6 Teorema — BFS Calcula Menores Caminhos

Pelo Lema 3, todo vértice alcançável v recebe d[v] = δ(s, v) na primeira descoberta.

4.7 A Árvore BFS É uma Árvore de Menores Caminhos

Todo vértice v ≠ s recebe exatamente um predecessor π[v]. Além disso, quando π[v] é definido, o BFS garante:

Portanto, seguir os ponteiros de predecessor de v de volta até s produz um caminho de comprimento d[v], que é igual à verdadeira menor distância.

4.8 Complexidade de Tempo (Revisão)

A prova de correção não altera o tempo de execução:

Cada vértice é descoberto uma vez. Cada aresta é examinada no máximo duas vezes (caso não direcionado).

4.9 Insight Estrutural

O BFS funciona porque ele impõe:

• crescimento monotônico da distância (d aumenta em exatamente 1 por camada)
• sem revisitas (coloração)
• ordem estrita por camadas (fila FIFO)