• Você deve justificar adequadamente todas as suas respostas;
• Os exercícios devem ser entregues escritos à mão;
• A apresentação tem valor preponderante na nota do exercício.

1. (2.5) Considere círculos com cordas dentro de uma região R limitada do plano (essa região é um retângulo). Os círculos podem ter tamanhos diferentes e podem se superpor (e ficam todos completamente dentro da região retangular). Nenhum círculo tangencia outro círculo ou uma corda. Cordas não se superpoões a outras cordas nem tangenciam outras cordas. Considere agora o seguinte teorema.
   
   
   Teorema 1  (K): É possível colorir todas as sub-regiões definidas por K círculos com cordas na região R de modo que as sub-regiões adjacentes (têm uma fronteira em comum) tenham cores diferentes, utilizando-se apenas três (3) cores.
   
   
   
   1. Prove este teorema por indução SIMPLES.
   2. Descreva como a sua prova no item anterior mostra como se pode colorir com três cores as regiões definidas por um número qualquer de círculos com cordas em posições quaisquer.
   3. Escreva o algoritmo correspondente ao item anterior.
   4. Aplique o algoritmo anterior para colorir as regiões definidas por 3 (ou mais) círculos com cordas, que se superpõem e se cortam.
   
   
2. Considere o seguinte teorema onde K £ m:
   
   
   Teorema 2  (K): O número de números inteiros de K dígitos diferentes 1,2,...,m é m.(m-1). .... . (m-k+1).
   
   
   Observe que um dígito pode ter valor ilimitado (m pode ser maior que 9).
   
   
   1. Considere K=2 e m=5 e enumere todos os números que atendem ao teorema.
   2. Prove este teorema por indução matemática SIMPLES (caso base e passo indutivo). Explicite o parâmetro de indução da sua prova.
   3. Mostre como a sua prova descreve uma forma de enumerar (listar) todos estes números.
   4. Escreva o algoritmo correspondente ao item anterior.
   5. Considere de novo K=2 e m=5 e siga os passos sugeridos pela sua prova. Liste os primeiros 20 números que seriam gerados para K=3 e m=5.
   
   
3. Seja um grafo G=(V,E), não-orientado, e um vértice s Î V. Seja o problema de determinar se o grafo G é conexo. Considere o teorema abaixo:
   
   
   Teorema 3  (K): Sabe-se encontrar todos os vértices que estão exatamente a uma distância K (em número de arestas) do vértice s.
   
   
   
   1. Prove este teorema por indução matemática SIMPLES (caso base e passo indutivo). Explicite o parâmetro de indução da sua prova.
   2. Mostre como a sua prova descreve uma forma de determinar se G é conexo.
   3. Escreva o algoritmo que determina se G é ou não conexo.
   4. Apresente grafos (2 ou 3) onde se possa mostrar que o seu algoritmo funciona.

This document was translated from L^AT_EX by H^EV^EA.