Marcar como concluído
Caminhos e Ciclos
Caminhos e Ciclos em Grafos
1. Hierarquia: Passeio → Trilha → Caminho
Passeio (Walk)
Uma sequência de vértices v₀, v₁, v₂, ..., vₙ onde cada par consecutivo (vᵢ, vᵢ₊₁) forma uma aresta do grafo.
Características:
- • Vértices podem se repetir
- • Arestas podem se repetir
- • É a forma mais geral de percurso
Exemplo: A → B → C → B → D
(vértice B se repete)
Trilha (Trail)
Um passeio onde nenhuma aresta se repete.
Características:
- • Vértices podem se repetir
- • Arestas NÃO podem se repetir ✓
- • Mais restritivo que passeio
Exemplo: A → B → C → D → B → E
(vértice B se repete, mas cada aresta é única)
Caminho (Path)
Uma trilha onde nenhum vértice se repete (exceto possivelmente o primeiro e o último).
Características:
- • Vértices NÃO podem se repetir ✓
- • Arestas NÃO podem se repetir ✓
- • É a forma mais restritiva
Exemplo: A → B → C → D → E
(todos os vértices são únicos)
📌 Resumo da Hierarquia:
Caminho ⊂ Trilha ⊂ Passeio
Todo caminho é uma trilha, e toda trilha é um passeio.
2. Ciclos
Definição de Ciclo
Um ciclo é um caminho que começa e termina no mesmo vértice, com comprimento mínimo 3.
v₀ → v₁ → v₂ → ... → vₙ → v₀
onde v₀ = vₙ e n ≥ 3
Ciclo Simples
Ciclo onde não há repetição de vértices (exceto o início/fim).
A → B → C → D → A
Ciclo Hamiltoniano
Ciclo que visita cada vértice do grafo exatamente uma vez.
Ciclo Euleriano
Ciclo que passa por todas as arestas exatamente uma vez.
Grafo Acíclico
Grafo que não contém nenhum ciclo.
3. Conectividade
Grafo Conexo
Um grafo é conexo se existe um caminho entre qualquer par de vértices.
✓ Grafo Conexo
Você consegue ir de qualquer vértice para qualquer outro vértice seguindo as arestas.
✗ Grafo Desconexo
Existem vértices isolados ou grupos isolados que não podem ser alcançados.
Componentes Conexos
Em um grafo desconexo, cada subgrafo maximal conexo é chamado de componente conexo.
Exemplo:
Se um grafo tem 3 "ilhas" separadas de vértices conectados, ele possui 3 componentes conexos.
4. Teorema do Aperto de Mãos
Teorema Fundamental
Em qualquer grafo, a soma dos graus de todos os vértices é igual ao dobro do número de arestas.
∑ deg(v) = 2|E|
v ∈ V
Por quê?
Cada aresta contribui com 2 para a soma total dos graus (um para cada extremidade).
🔍 Consequência Importante:
Em qualquer grafo, o número de vértices com grau ímpar é sempre par.
5. Distância e Diâmetro
Distância d(u, v)
Comprimento do menor caminho entre dois vértices u e v.
Se não existe caminho: d(u, v) = ∞
Diâmetro diam(G)
Maior distância entre qualquer par de vértices no grafo.
Indica o "tamanho" do grafo