Marcar como concluído
Introdução aos Grafos
Introdução aos Grafos
1. O que são Grafos?
Definição
Um grafo G é uma estrutura matemática definida por um par ordenado G = (V, E), onde:
- •V: Conjunto não-vazio de vértices (ou nós)
- •E: Conjunto de arestas (conexões entre vértices)
Aplicações Práticas
Redes Sociais
Pessoas são vértices, amizades são arestas
Mapas e GPS
Locais são vértices, estradas são arestas
Circuitos Elétricos
Componentes são vértices, conexões são arestas
Internet
Servidores são vértices, conexões de rede são arestas
2. Tipos de Grafos
Grafo Não-Direcionado
As arestas não possuem direção. Se existe uma aresta entre A e B, podemos ir de A para B ou de B para A.
Notação: {u, v} ou uv
Grafo Direcionado (Digrafo)
As arestas possuem direção. Uma aresta de A para B não implica em uma aresta de B para A.
Notação: (u, v) ou u → v
Grafo Ponderado
Cada aresta possui um peso (valor) associado. Útil para representar distâncias, custos, capacidades.
w(u,v) = peso da aresta entre u e v
3. Terminologia Básica
Conceitos Fundamentais
- Adjacência
- Dois vértices são adjacentes se existe uma aresta entre eles
- Incidência
- Uma aresta é incidente a um vértice se o conecta a outro vértice
- Grau de um vértice
- Número de arestas incidentes ao vértice
Notação: d(v) ou deg(v)
- Laço (Loop)
- Aresta que conecta um vértice a ele mesmo
- Arestas Paralelas
- Duas ou mais arestas que conectam o mesmo par de vértices
4. Propriedades Importantes
Teorema do Aperto de Mãos
A soma dos graus de todos os vértices é igual ao dobro do número de arestas.
Σ d(v) = 2|E|
Consequência
Em qualquer grafo, o número de vértices com grau ímpar é sempre par.
5. Grafos Especiais
Grafo Completo (K₄)
Todo par de vértices está conectado
|E| = 4(3)/2 = 6 arestas
Ciclo (C₅)
Grafo em forma de círculo com n vértices
|V| = |E| = 5
Árvore
Grafo conexo sem ciclos
|E| = |V| - 1 = 5
Grafo Bipartido
Vértices divididos em dois conjuntos disjuntos
V = V₁ ∪ V₂, V₁ ∩ V₂ = ∅