MD - Lista 3

Prévia do material em texto

Terceira lista de exercícios de Matemática Discreta 
 
1. Usando a equação f(x) = 2x - 1 para descrever a associação funcional, escreva a função 
como um conjunto de pares ordenados se o contradomínio é R e 
 
a) o domínio é S = {0, 1, 2} 
b) o domínio é S = {1, 2, 4, 5} 
 
2. Sejam S = {0, 2, 4, 6} e T = {1, 3, 5, 7}. Determine se cada um dos conjuntos de pares 
ordenados a seguir é uma função com domínio S e contradomínio T. Se esse for o caso, a 
função é injetora? É sobrejetora? 
 
a) {(0, 2), (2, 4), (4, 6), (6, 0)} 
b) {(6, 3), (2, 1), (0, 3), (4, 5)} 
c) {(2, 3), (4, 7), (0, 1), (6, 5)} 
d) {(6, 1), (0, 3), (4, 1), (0, 7), (2, 5)} 
 
3. Teste se as relações abaixo são reflexivas, simétricas, transitivas e anti-simétricas. Diga se é 
uma relação de equivalência. Justifique a resposta apenas quando a relação não tiver a 
propriedade. 
 
a) R = {1, 2}, ρ = {(1,1), (2,2), (1, 2)} 
b) S = {1, 2, 3}, ρ = {(1,1), (2,2), (2,3),(3,2)} 
c) R = N, x ρ y ↔ x é ímpar 
d) S = {0, 1, 2, 3, 4, 5}, x ρ y ↔ x + y = 5 
e) S = R; x  y  7 divide 3x + 4y é um múltiplo de 3 
 
4. Responda as perguntas a seguir sobre o grafo na figura abaixo: 
 
5. Quais dos grafos a seguir não são isomorfos aos outros e por quê? 
 
a) O grafo é simples? 
b) O grafo é completo? 
c) Você pode encontrar dois caminhos de 3 para 6? 
d) Você pode encontrar uma aresta cuja remoção 
transforamará o grafo em um grafo acíclico? 
e) Você pode encontrar uma aresta cuja remoção 
tranformará o grafo em um grafo não conexo ? 
 
6. Considere os grafos A e B mostrados abaixo: 
 
 
 
 
 
 
 
 
 
 
 
 
Diga se eles são planares ou não. Justifique sua resposta. 
 
G H