Marcar como concluído
Fórmulas Essenciais
Fórmulas Essenciais
Todas as fórmulas importantes de Teoria dos Grafos em um só lugar
📚 Conjuntos
Conjunto Potência
|P(A)| = 2|A|
Produto Cartesiano
|A × B| = |A| · |B|
União
A ∪ B = {x | x ∈ A ou x ∈ B}
Interseção
A ∩ B = {x | x ∈ A e x ∈ B}
Diferença
A - B = {x | x ∈ A e x ∉ B}
Complemento
Ac = U - A
Leis de De Morgan
(A ∪ B)c = Ac ∩ Bc
(A ∩ B)c = Ac ∪ Bc
🌐 Grafos - Definições Básicas
Grafo
G = (V, E)
V = vértices, E = arestas
Grau de um Vértice
deg(v) ou d(v)
número de arestas incidentes
Arestas em Grafo Completo
|E| = n(n-1)/2
Kn tem n vértices
Arestas em Árvore
|E| = |V| - 1
grafo acíclico conexo
🤝 Teorema do Aperto de Mãos
∑ deg(v) = 2|E|
v ∈ V
A soma dos graus de todos os vértices é igual ao dobro do número de arestas.
Consequência: O número de vértices com grau ímpar é sempre par.
🛤️ Caminhos e Distâncias
Comprimento do Caminho
ℓ(P) = número de arestas
Distância
d(u,v)
comprimento do menor caminho
Diâmetro
diam(G) = max d(u,v)
maior distância no grafo
Raio
rad(G) = minv maxu d(u,v)
excentricidade mínima
Hierarquia de Percursos
Caminho ⊂ Trilha ⊂ Passeio
• Passeio: vértices e arestas podem repetir
• Trilha: arestas não se repetem
• Caminho: vértices não se repetem
📊 Representação Matricial
Matriz de Adjacência
A[i][j] = 1 se (i,j) ∈ E
A[i][j] = 0 caso contrário
• Dimensão: n × n
• Espaço: O(n²)
• Simétrica para grafos não-direcionados
• deg(vi) = soma da linha i
Matriz de Incidência
M[i][j] = 1 se vi incidente em ej
M[i][j] = 0 caso contrário
• Dimensão: n × m
• Espaço: O(n·m)
• Cada coluna tem 2 valores "1"
• deg(vi) = soma da linha i
Potências da Matriz de Adjacência
Ak[i][j] = nº de passeios de tamanho k de i para j
A k-ésima potência da matriz de adjacência conta o número de passeios de comprimento k entre vértices.
⭐ Grafos Especiais
Grafo Completo Kn
|E| = n(n-1)/2
Todo par de vértices conectado
Ciclo Cn
|V| = |E| = n
Grafo em forma de círculo
Árvore
|E| = |V| - 1
Grafo acíclico conexo
Grafo Bipartido
V = V₁ ∪ V₂
V₁ ∩ V₂ = ∅
Grafo Regular
∀v: deg(v) = k
Todos vértices mesmo grau
Grafo Planar
|E| ≤ 3|V| - 6
Pode ser desenhado sem cruzamentos
🎯 Fórmulas de Euler
Fórmula de Euler para Grafos Planares
V - E + F = 2
V = número de vértices
E = número de arestas
F = número de faces (incluindo face externa)
Caminho e Ciclo Eulerianos
Caminho Euleriano existe se:
Exatamente 2 vértices com grau ímpar
Ciclo Euleriano existe se:
Todos os vértices têm grau par
⚡ Complexidades de Algoritmos
| Algoritmo | Lista de Adjacência | Matriz de Adjacência |
|---|---|---|
| BFS (Busca em Largura) | O(V + E) | O(V²) |
| DFS (Busca em Profundidade) | O(V + E) | O(V²) |
| Dijkstra | O((V + E) log V) | O(V²) |
| Floyd-Warshall | O(V³) | O(V³) |
| Kruskal | O(E log E) | O(V² log V) |
| Prim | O((V + E) log V) | O(V²) |