Matemática Discretapara Engenheiros

Modelo de Grafo e Formulação do Problema

1. Por que começar pelo modelo?

Antes de discutir algoritmos, devemos definir precisamente qual problema estamos resolvendo.

A Busca em Largura não é apenas uma técnica de percurso.
Ela é um algoritmo de caminho mínimo em teoria dos grafos para uma estrutura matemática específica.

Começamos, portanto, pelo objeto:

Onde:

• V = conjunto de vértices
• E ⊆ V × V = conjunto de arestas

Esta é a base formal apresentada em Introduction to Algorithms.

2. Grafos orientados e não orientados

Distinguimos dois modelos fundamentais.

Grafo orientado (dígrafo)

As arestas têm orientação: se (u, v) ∈ E, você pode ir de u para v, mas não necessariamente de v para u.

Grafo não orientado

As arestas são simétricas: se u é adjacente a v, então v é adjacente a u.

A BFS funciona em ambos os modelos.

3. Representação do grafo

Um algoritmo precisa operar sobre uma representação de dados de G.

3.1 Lista de adjacência (recomendada)

Cada vértice armazena uma lista de seus vizinhos:

Esta é a representação padrão no CLRS porque ela resulta em complexidade de tempo O(V + E) para a BFS.

3.2 Matriz de adjacência

Uma matriz A ∈ {0, 1}^|V|×|V|:

Essa representação leva a complexidade O(V²) para o percurso.

Para grafos esparsos (comuns em sistemas de engenharia), listas de adjacência são superiores.

4. O problema que a BFS resolve

Seja s ∈ V um vértice de origem (fonte) distinguido.

Queremos calcular:

4.1 Atingibilidade

Quais vértices são alcançáveis a partir de s?

4.2 Distância de caminho mínimo (grafos não ponderados)

Defina δ(s, v) como o número mínimo de arestas em qualquer caminho de s até v. Isso é chamado de distância no grafo.

A BFS computa d[v] = δ(s, v) para todos os vértices alcançáveis.

5. Caminhos — definição formal

Um caminho de comprimento k é uma sequência v₀, v₁, …, v_k tal que (v_i−1, v_i) ∈ E para todo i = 1, …, k.

O comprimento do caminho é k.

Problema de caminho mínimo: min k, sujeito à existência de tal sequência.

6. Estrutura em camadas — uma prévia da geometria da BFS

Embora ainda não tenhamos definido o algoritmo, introduzimos uma ideia estrutural.

Defina as camadas por distância:

• L₀ = {s}
• L₁ = vizinhos de s
• L₂ = vértices a distância 2
• etc.

Essas camadas particionam o subgrafo alcançável. A BFS explorará os vértices exatamente nessa ordem por camadas.

Essa estrutura em camadas é o coração geométrico do algoritmo.

7. Objetivo da BFS (enunciado preciso)

Dado um grafo G = (V, E) e uma origem s ∈ V, compute:

• A função distância d : V → N ∪ {∞}
• Uma função predecessor π : V → V ∪ {NIL}

tal que:

• d[v] = δ(s, v)
• Os ponteiros de predecessor formam uma árvore de caminhos mínimos enraizada em s

8. Por que isso importa em engenharia

A BFS aparece em:

• Roteamento em redes (saltos não ponderados)
• Distância em redes sociais
• Rastreamento/crawling na web
• Resolução de dependências
• Análise de conectividade
• Teste de bipartição

Em termos de matemática discreta: a BFS constrói a estrutura métrica induzida pela distância por número de arestas.

Isso não é apenas um percurso. É a construção de um espaço métrico de caminhos mínimos sobre G.