Marcar como concluído
Representação Matricial
Representação Matricial de Grafos
1. Matriz de Adjacência
Definição
Para um grafo G = (V, E) com n vértices, a matriz de adjacência A é uma matriz n × n onde:
A[i][j] = 1, se existe aresta entre vᵢ e vⱼ
A[i][j] = 0, caso contrário
Exemplo Prático
Grafo G:
V = {1, 2, 3, 4}
E = {
(1,2), (1,3),
(2,3), (3,4)
}
Matriz de Adjacência A:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 1 | 0 |
| 3 | 1 | 1 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 |
Propriedades da Matriz de Adjacência
✓ Grafos Não-Direcionados
A matriz é simétrica: A[i][j] = A[j][i]
✓ Grau dos Vértices
deg(vᵢ) = soma da linha i (ou coluna i)
✓ Complexidade de Espaço
O(n²) - sempre usa n² espaço, independente do número de arestas
✓ Verificação de Adjacência
O(1) - tempo constante para verificar se existe aresta entre dois vértices
2. Matriz de Incidência
Definição
Para um grafo G = (V, E) com n vértices e m arestas, a matriz de incidência M é uma matriz n × m onde:
M[i][j] = 1, se o vértice vᵢ é incidente à aresta eⱼ
M[i][j] = 0, caso contrário
Exemplo Prático
Grafo G:
V = {1, 2, 3}
E = {
e₁ = (1,2)
e₂ = (2,3)
e₃ = (1,3)
}
Matriz de Incidência M:
| e₁ | e₂ | e₃ | |
|---|---|---|---|
| v₁ | 1 | 0 | 1 |
| v₂ | 1 | 1 | 0 |
| v₃ | 0 | 1 | 1 |
Propriedades da Matriz de Incidência
✓ Soma por Coluna
Cada coluna tem exatamente 2 valores "1" (as duas extremidades da aresta)
✓ Grau dos Vértices
deg(vᵢ) = soma da linha i
✓ Complexidade de Espaço
O(n × m) - mais eficiente para grafos esparsos
3. Potências da Matriz de Adjacência
Teorema dos Passeios
O elemento Ak[i][j] da k-ésima potência da matriz de adjacência representa o número de passeios de comprimento k entre os vértices vᵢ e vⱼ.
Ak[i][j] = número de passeios de tamanho k de i para j
Exemplos:
- • A¹: número de passeios de comprimento 1 (arestas diretas)
- • A²: número de passeios de comprimento 2
- • A³: número de passeios de comprimento 3
💡 Aplicação Prática:
Para verificar se existe caminho de comprimento k entre dois vértices, calcule Ak e verifique se o elemento correspondente é maior que zero.
4. Comparação: Adjacência vs Incidência
| Aspecto | Matriz de Adjacência | Matriz de Incidência |
|---|---|---|
| Dimensão | n × n | n × m |
| Espaço | O(n²) | O(n × m) |
| Verificar adjacência | O(1) - muito rápido | O(m) - mais lento |
| Listar vizinhos | O(n) | O(m) |
| Melhor para | Grafos densos | Grafos esparsos |
| Informação sobre arestas | Implícita | Explícita (cada coluna = aresta) |
5. Algoritmos com Matrizes
Busca em Profundidade (DFS)
Usa matriz de adjacência para explorar recursivamente todos os vértices conectados.
Busca em Largura (BFS)
Explora vértices por níveis de distância usando fila e matriz de adjacência.
Floyd-Warshall
Encontra menores caminhos entre todos os pares de vértices.
Warshall
Calcula o fecho transitivo (alcançabilidade entre vértices).