Exercícios de Relações - Matemática Discreta

Universidade Federal do Ceará Lista 2 Matemática Discreta Grafos Prof Fábio Ribeiro 1 Um grafo é chamado de 𝑘 𝑐𝑢𝑏𝑜 ou cubo de dimensão 𝑘 quando seus vértices são 𝑥1 𝑥2 𝑥𝑘 onde cada 𝑥𝑖 01 e dois vértices são adjacentes se e somente se diferem por apenas uma coordenada Faça figuras dos cubos de dimensões 1 2 e 3 2 Quantas arestas tem um grafo com vértices de graus 5 2 2 2 2 1 Desenhe um possível grafo 3 Existe um grafo simples com cinco vértices dos seguintes graus 1 2 3 4 5 Se existir desenhe um possível grafo 4 Um grafo regular é aquele em que todos os vértices têm o mesmo grau Em um grafo regular de grau n todos vértices tem grau 𝑛 Quantos vértices tem um grafo regular de grau 4 com 10 arestas 5 Se um grafo simples 𝐺 tem 𝑛 vértices e 𝑚 arestas quantas arestas tem 𝐺𝑐 6 O grafo H é subgrafo de G ou de G Grafo H Grafo G Grafo G 7 O grafo H é subgrafo induzido pelos vértices de G 8 Seja 𝐺 um grafo com 𝑛 vértices e 𝑚 arestas e seja 𝑣 um vértice de 𝐺 de grau 𝑘 e 𝑎 uma aresta de 𝐺 Quantos vértices e arestas têm o grafo 𝐺 𝑎 e 𝐺 𝑣 9 Desenhe todos os subgrafos do grafo abaixo 10 Encontre um isomorfismo entre os grafos 11 Os grafos são isomorfos 12 Desenhe o grafo cuja matriz de adjacência é 0 1 0 1 0 1 0 1 1 13 Escreva a matriz de incidência do grafo 14 Seja 𝑉𝐺 𝑣1 𝑣2 𝑣𝑛 o conjunto de vértices de um grafo 𝐺 A sequência 𝑑𝑣1 𝑑𝑣2 𝑑𝑣𝑛 É chamada de sequência de graus de 𝐺 Uma sequência numérica 𝑑 𝑑1 𝑑𝑛 é dita gráfica se existe um grafo simples cuja sequência de graus é 𝑑 As sequências 7654332 e 6654331 são gráficas Universidade Federal do Ceará Lista 1 Matemática Discreta Relações Prof Fábio Ribeiro 1 Seja 𝐴 um conjunto não vazio e 𝑃𝐴 o conjunto das partes de 𝐴 Dizemos que um conjunto não vazio ℙ 𝑃𝐴 é uma partição do conjunto 𝐴 quando 1 𝐵1 𝐵2 ℙ 𝐵1 𝐵2 𝐵1 𝐵2 2 𝐵 𝐵ℙ 𝐴 Definimos a seguinte relação 𝑥𝑦 𝐵 ℙ tal que 𝑥 𝑦 𝐵 Essa relação é de equivalência Observação Dizemos que é induzida pela partição ℙ 2 Considere o conjunto 𝐴 0 1 2 3 4 e a partição ℙ 0 3 4 1 2 Determine a relação 𝑅 induzida por essa partição 3 Seja 𝑓 𝑋 𝑌 uma função Considere a relação 𝑥1 𝑥2 𝑋 𝑥1𝑥2 𝑓𝑥1 𝑓𝑥2 Isso defini uma relação de equivalência no conjunto 𝑋 Neste caso dizemos que é induzida pela função 𝑓 Descreva as classes de equivalência da relação induzida pela função 𝑎 𝑓 ℝ ℝ definida por 𝑓𝑥 𝑥2 7𝑥 10 𝑏 𝑓 ℝ ℝ ℝ definida por 𝑓𝑥 𝑦 𝑦 𝑐 𝑓 ℝ ℝ ℝ definida por 𝑓𝑥 𝑦 𝑥2 𝑦2 4 Em ℤ ℤconsidere a relação 𝑥 𝑦 𝑥 𝑦 𝑥𝑦 𝑥𝑦 É uma relação de equivalência Observação ℤ ℤ 0 5 Para cada item a seguir dê exemplo de relação de equivalência em um conjunto 𝑋 que satisfaça a condição dada 𝑎 𝑋 𝑋 𝑏 𝑥 𝑥 𝑥 𝑋 𝑐 𝑋 seja um conjunto infinito e 𝑋 contenha exatamente 11 elementos 𝑑 𝑋 seja um conjunto infinito e 𝑋 também seja infinito 6 Na figura a seguir as setas indicam que elementos estão relacionados entre si Por exemplo se uma seta sai de 𝑥 e chega em 𝑦 então 𝑥𝑦 Se uma seta sai de 𝑥 e se dirige a ele mesmo então 𝑥𝑥 Verifique se essas relações são de equivalência 𝑎 𝑏 7 É possível representar uma relação entre dois conjuntos finitos por uma matriz Considere os conjuntos 𝐴 𝑎1 𝑎2 𝑎𝑚 e 𝐵 𝑏1 𝑏2 𝑏𝑛 Definimos a matriz da Relação 𝑅 por 𝑀 𝑚𝑖𝑗𝑚𝑛 tal que 𝑚𝑖𝑗 1 𝑠𝑒 𝑎𝑖𝑏𝑗 0 𝑠𝑒 𝑎𝑖 𝑏𝑗 Considere os conjuntos 𝐴 1 2 3 e 𝐵 𝑟 𝑠 e a relação 𝑅 1 𝑟 2 𝑠 3 𝑟 Escreva a matriz de 𝑅 8 Considere a matriz 𝑀 1 0 1 0 1 0 0 1 1 1 0 0 Escreva uma relação entre dois conjuntos tais que a matriz da relação seja 𝑀 9 Seja 𝐴 1 4 5 e 𝑅 a relação em 𝐴 dada pela figura a seguir Encontre 𝑅 e a matriz dessa relação 10 A figura a seguir representa uma relação de ordenação parcial Escreva os pares ordenados que pertencem à relação 11 O diagrama a baixo representa um conjunto parcialmente ordenado Encontre o máximo o mínimo o elemento maximal e o elemento minimal 12 Quais os elementos de 𝐴 24510122025 considerando a relação de divisibilidade são maximais e quais são minimais 13 Quais dos conjuntos a seguir são relações de ordem parcial 𝑎 ℤ 𝑏 ℤ 𝑐 ℤ 𝑑 ℝ 𝑒 ℝ 𝑓 ℝ 14 Desenhe o diagrama de Hesse para inclusão no conjunto 𝑃𝑆 em que 𝑆 𝑎 𝑏 𝑐 𝑑 15 Desenhe o diagrama de Hesse para a divisibilidade no conjunto 23510111525 Soluções e sugestões 1 Seja 𝐴 um conjunto não vazio e 𝑃𝐴 o conjunto das partes de 𝐴 Dizemos que um conjunto não vazio ℙ 𝑃𝐴 é uma partição do conjunto 𝐴 quando 1 𝐵1 𝐵2 ℙ 𝐵1 𝐵2 𝐵1 𝐵2 2 𝐵 𝐵ℙ 𝐴 Definimos a seguinte relação 𝑥𝑦 𝐵 ℙ tal que 𝑥 𝑦 𝐵 Essa relação é de equivalência Solução Seja ℙ uma partição 𝑥𝑥 pois existe 𝐵 ℙ tal que 𝑥 𝐵 A relação é reflexiva Se 𝑥𝑦 então existe 𝐵 tal que 𝑥 𝑦 𝐵 Assim 𝑦𝑥 A relação é simétrica Se 𝑥𝑦 e 𝑦𝑧 então existem 𝐵1 e 𝐵2 tais que 𝑥 𝑦 𝐵1 e 𝑦 𝑧 𝐵2 Considere o conjunto 𝐵1 𝐵2 Então 𝑥 𝑧 𝐵1 𝐵2 ou seja 𝑥𝑧 A relação é transitiva 2 Considere o conjunto 𝐴 0 1 2 3 4 e a partição ℙ 0 3 4 1 2 Determine a relação 𝑅 induzida por essa partição Solução A relação dever ser 𝑥𝑦 𝐵 ℙ tal que 𝑥 𝑦 𝐵 A relação é 𝑅 00 33 4411 22 0304 34 43 Pois 00 33 44 11 22 03 04 34 43 3 Seja 𝑓 𝑋 𝑌 uma função Considere a relação 𝑥1 𝑥2 𝑋 𝑥1𝑥2 𝑓𝑥1 𝑓𝑥2 Isso defini uma relação de equivalência no conjunto 𝑋 Neste caso dizemos que é induzida pela função 𝑓 Descreva as classes de equivalência da relação induzida pela função 𝑎 𝑓 ℝ ℝ definida por 𝑓𝑥 𝑥2 7𝑥 10 𝑏 𝑓 ℝ ℝ ℝ definida por 𝑓𝑥 𝑦 𝑦 𝑐 𝑓 ℝ ℝ ℝ definida por 𝑓𝑥 𝑦 𝑥2 𝑦2 10 A figura a seguir representa uma relação de ordenação parcial Escreva os pares ordenados que pertencem à relação Solução Para ser ordenação parcial deve ser reflexiva antissimétrica e transitiva Então os pares da relação são 𝟏 𝟏 𝟐 𝟐 𝟑 𝟑 𝟒 𝟒 𝟓 𝟓 𝟏 𝟐 𝟏 𝟑 𝟐 𝟒 𝟑 𝟒 𝟒 𝟓 𝟏 𝟒 𝟏 𝟓 𝟐 𝟓 𝟑 𝟓 Deve se notar ainda a ordem na relação Por exemplo 1 2 mas 2 1 Se também tivéssemos 2 1 então pela propriedade antissimétrica 1 2 o que evidentemente não é verdade Assim Os seguintes pares não podem fazer parte da relação 54 43 42 41 31 21 1 O cubo de dimensão 1 é um segmento de reta o de dimensão 2 é um quadrado e o de dimensão 3 é o cubo comum Cubo 1D Cubo 2D Cubo 3D 2 A soma dos graus é 14 então o número de arestas é 7 Abaixo um exemplo de grafo com graus 5 2 2 2 2 1 Exemplo de grafo da questão 2 3 Não existe grafo com graus 12345 porque a soma é ímpar 4 Um grafo regular de grau 4 com 10 arestas tem 5 vértices 5 O número de arestas do complementar é nn12 m 6 O grafo H pode ser verificado na figura do enunciado para decidir se é subgrafo de G ou G 7 Para ser subgrafo induzido precisa conter todos os vértices escolhidos e todas as arestas entre eles 8 G a n vértices e m1 arestas G v n1 vértices e mk arestas 10 O isomorfismo deve mapear vértices preservando adjacência 11 Sim Dois grafos são isomorfos se existe uma bijeção entre seus conjuntos de vértices que preserva a adjacência 12 A matriz de adjacência dada corresponde a um grafo com vértices v1v2 v2v3 e um laço em v3 Grafo da matriz de adjacência 13 A matriz de incidência deve ser construída de acordo com o grafo fornecido no enunciado 14 As sequências 7654332 e 6654331 são gráficas pois passam pelo teste de Havel Hakimi