1. Prove que regiões definidas apenas por círculos podem ser coloridas (de modo que regiões vizinhas tenham cores diferentes) com 2 cores.
   
   Enuncie o teorema de que sabe-se colorir estas regiões com 2 cores, prove este teorema por indução simples e apresente o algoritmo correspondente.
   
   
2. Prove por indução matemática que o número de números inteiros de K dígitos diferentes 1,2,...,m é m.(m-1). .... . (m-k+1).
   
   Enuncie o teorema de que sabe-se enumerar todos estes números, prove este teorema por indução simples e apresente o algoritmo que enumera (imprime) todos eles correspondente à sua prova.
   
   
3. Considere um conjunto de inteiros I={i₁, i₂, ..., i_n }.
   1. Seja o problema de encontrar o máximo e o mínimo de I.
      Teorema 1  (K): Sabe-se encontrar o máximo e o mínimo de I^K={i₁, i₂, ..., i_K }.
      Prove este teorema por indução simples e apresente o algoritmo correspondente. Em seguida, prove este mesmo teorema por indução forte e derive o novo algoritmo.
      
      
   2. Seja o problema de ordenar o conjunto I.
      Teorema 2  (K): Sabe-se ordenar I^K={i₁, i₂, ..., i_K }.
      Prove este teorema por indução simples e apresente o algoritmo correspondente.
   
   
4. Seja um grafo conexo G=(V,E), não-orientado, e w_e, para e Î E os pesos, onde V={1, 2, ..., n } associados às arestas de G.
   1. Seja o problema de encontrar a árvore geradora de peso máximo de G.
      Teorema 3  (K): Sabe-se encontrar uma árvore de G=(V,E), que contém o vértice 1 (1 Î V), que possui K vértice e possui peso máximo.
      Prove este teorema por indução simples e apresente o algoritmo correspondente.
      
      
      Teorema 4  (K): Sabe-se encontrar a floresta F=(V,E^K) de peso máximo de G=(V,E) que possui K arestas, isto é |E^K|=K.
      Prove este teorema por indução simples e apresente o algoritmo correspondente.
      
      
   2. Seja o problema de encontrar um conjunto DOMINANTE minimal. Um conjunto dominante D Í V, é um conjunto de vértices tal que qualquer vértice v ou está em D ou possui uma aresta que o liga a um vértice em D.
      Teorema 5  (K): Sabe-se obter um conjunto dominante minimal de G^K=(V^K,E^K), onde V^K={1, 2, ..., K } e E^K={ (u,w) | u Î V^K Ù w Î V^K }.
      Prove este teorema por indução simples e apresente o algoritmo correspondente.
      
      Analise na sua prova como você garante que o conjunto é minimal.
   
   
5. Seja um grafo orientado G=(V,A) e o problema de encontrar o caminho mais curto entre um par de vértices s e t.
   Teorema 6  (K): Sabe-se obter a distância mínima de s a todos os vértices de V onde os caminhos podem ter no máximo K arcos.
   Prove este teorema por indução simples e apresente o algoritmo correspondente.

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