Marcar como concluído
Exercícios Resolvidos
Exercícios Resolvidos
Questões selecionadas com resolução completa passo a passo
Produto Cartesiano e Relações
📝 Enunciado:
Dados os conjuntos A = {1, 2, 3} e B = {a, b}, determine:
- O produto cartesiano A × B
- O produto cartesiano B × A
- A cardinalidade de cada produto
- A × B é igual a B × A?
✅ Resolução:
a) A × B:
O produto cartesiano A × B é o conjunto de todos os pares ordenados (a, b) onde a ∈ A e b ∈ B.
A × B = {
(1, a), (1, b),
(2, a), (2, b),
(3, a), (3, b)
}
b) B × A:
B × A = {
(a, 1), (a, 2), (a, 3),
(b, 1), (b, 2), (b, 3)
}
c) Cardinalidade:
|A × B| = |A| · |B| = 3 · 2 = 6
|B × A| = |B| · |A| = 2 · 3 = 6
d) A × B = B × A?
Não! O produto cartesiano não é comutativo.
Exemplo: (1, a) ∈ A × B, mas (1, a) ∉ B × A
Função Injetora
📝 Enunciado:
Verifique se a função f: ℕ → ℕ definida por f(x) = 2x + 1 é injetora.
✅ Resolução:
Definição de Função Injetora:
Uma função é injetora se elementos distintos do domínio têm imagens distintas.
∀x₁, x₂ ∈ ℕ: x₁ ≠ x₂ ⇒ f(x₁) ≠ f(x₂)
ou equivalentemente:
∀x₁, x₂ ∈ ℕ: f(x₁) = f(x₂) ⇒ x₁ = x₂
Demonstração:
Suponha que f(x₁) = f(x₂). Então:
2x₁ + 1 = 2x₂ + 1
2x₁ = 2x₂
x₁ = x₂
✓ Conclusão: Como f(x₁) = f(x₂) implica x₁ = x₂, a função é injetora.
Verificação com exemplos:
- f(0) = 1
- f(1) = 3
- f(2) = 5
- f(3) = 7
- f(4) = 9
Todas as imagens são distintas ✓
Teorema do Aperto de Mãos
📝 Enunciado:
Um grafo possui 5 vértices com os seguintes graus:
deg(v₁) = 3, deg(v₂) = 2, deg(v₃) = 4, deg(v₄) = 1, deg(v₅) = ?
Se o grafo possui 6 arestas, qual é o grau do vértice v₅?
✅ Resolução:
Teorema do Aperto de Mãos:
∑ deg(v) = 2|E|
A soma dos graus é igual ao dobro do número de arestas
Aplicando o teorema:
∑ deg(v) = 2 · 6 = 12
deg(v₁) + deg(v₂) + deg(v₃) + deg(v₄) + deg(v₅) = 12
3 + 2 + 4 + 1 + deg(v₅) = 12
10 + deg(v₅) = 12
deg(v₅) = 2
Verificação:
Soma total: 3 + 2 + 4 + 1 + 2 = 12 ✓
2|E| = 2 · 6 = 12 ✓
Obs: Note que temos 2 vértices com grau ímpar (v₁ e v₄), o que confirma a consequência do teorema: o número de vértices com grau ímpar é sempre par.
Construindo Matriz de Adjacência
📝 Enunciado:
Dado o grafo G = (V, E) onde:
V = {1, 2, 3, 4}
E = { (1,2), (1,3), (2,4), (3,4) }
Construa a matriz de adjacência e determine o grau de cada vértice.
✅ Resolução:
Matriz de Adjacência A:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 0 | 1 |
| 3 | 1 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 | 0 |
Construção passo a passo:
1. Aresta (1,2): A[1][2] = 1 e A[2][1] = 1 (grafo não-direcionado)
2. Aresta (1,3): A[1][3] = 1 e A[3][1] = 1
3. Aresta (2,4): A[2][4] = 1 e A[4][2] = 1
4. Aresta (3,4): A[3][4] = 1 e A[4][3] = 1
Todos os outros elementos = 0
Grau dos vértices:
O grau de cada vértice = soma da linha (ou coluna) correspondente:
deg(v₁) = 0 + 1 + 1 + 0 = 2
deg(v₂) = 1 + 0 + 0 + 1 = 2
deg(v₃) = 1 + 0 + 0 + 1 = 2
deg(v₄) = 0 + 1 + 1 + 0 = 2
Verificação: ∑ deg(v) = 2 + 2 + 2 + 2 = 8 = 2 · 4 = 2|E| ✓
Identificando Passeios, Trilhas e Caminhos
📝 Enunciado:
Classifique cada sequência abaixo como passeio, trilha ou caminho:
- a) A → B → C → D → E
- b) A → B → C → B → D
- c) A → B → C → D → C → E
- d) A → B → A → C
✅ Resolução:
Definições:
- • Passeio: vértices e arestas podem repetir
- • Trilha: arestas não se repetem (vértices podem)
- • Caminho: vértices não se repetem (mais restritivo)
a) A → B → C → D → E
✓ Vértices distintos: A, B, C, D, E
✓ Arestas distintas: AB, BC, CD, DE
→ É um CAMINHO (e também trilha e passeio)
b) A → B → C → B → D
✗ Vértice B se repete
✓ Arestas distintas: AB, BC, CB, BD
→ É uma TRILHA (mas não é caminho)
c) A → B → C → D → C → E
✗ Vértice C se repete
✓ Arestas distintas: AB, BC, CD, DC, CE
→ É uma TRILHA (mas não é caminho)
d) A → B → A → C
✗ Vértice A se repete
✗ Aresta AB se repete (ida e volta)
→ É um PASSEIO (mas não é trilha nem caminho)