MO405 - Exercícios - Propostos em 2002-08-07

Nos exercícios que perguntam "verdadeiro ou falso", deve-se justificar a resposta da seguinte forma: se for verdadeiro, com uma prova; se for falso, com um contra-exemplo.

1. Verdadeiro ou falso: se todo vértice de um grafo tem grau 2, então o grafo é um ciclo.
2. Verdadeiro ou falso: o complemento de um grafo simples desconexo é necessariamente conexo.
3. Considere as seguintes famílias de grafos: A = {caminhos}, B = {ciclos}, C = {grafos completos}, D = {grafos bipartidos}. Descreva as intersecções entre duas destas famílias (são 6 intersecções: A com B, A com C, etc.)
4. Ache o menor par de grafos simples, não isomorfos, mas com o mesmo número de vértices e com a mesma lista de graus dos vértices.

Soluções - Disucitdas em classe em 2002-08-12

1. Falso. O grafo pode ter duas ou mais componentes.
2. Verdadeiro. Para quaisquer 'u' e 'v' pertencentes ao conjunto de vértices de um grafo desconexo 'G' existe um caminho entre 'u' e 'v' no grafo complemento de 'G'.

   Temos dois casos: - não existe uma aresta no grafo 'G' entre os vértices 'u' e 'v' - existe uma aresta no grafo 'G' entre os vértices 'u' e 'v', logo, eles pertencem ao mesmo componente conexo.

   Para o primeiro caso, quando se fizer o complemento do grafo 'G', por definição, haverá uma aresta que ligará 'u' e 'v'.

   Quando existir uma aresta ligando os vértices 'u' e 'v' no grafo 'G', precisa-se do auxílio de um vértice 'x' pertencente a um outro componente conexo, o que significa que não existe uma aresta entre 'u' e 'x' nem entre 'v' e 'x'. Desta forma, no grafo complemento de 'G', existirá uma aresta de 'u' a x' e outra de 'v' a 'x', fazendo que exista um caminho entre 'u' e 'v'.

   Assim consegue-se que, qualquer que seja o caso, haverá um caminho entre quaisquer dois vértices do complemento de um grafo 'G'.

   Uma outra linha de argumentaçao consiste em pensar que o pior caso ocorre quando tem-se dois grafos completos como componentes conexas do grafo 'G'. Se o complemento deste tipo de grafo for conexo, com mais razao serao conexos os complementos de outros grafos desconexos.

   Neste pior caso, o complemento é um grafo bipartido completo, que é conexo.

3. A e B = vazio
   A e C = {K1, K2}
   A e D = A
   B e C = {K3}
   B e D = {C_2n, n >= 2}
   C e D = {K1, K2}
   

4. 
    *----*  *
     \   |  |
      \  |  |
       \ |  |
        \|  |
         *  *
   
    *----*----*
     \
      \
       \
        \
         *----*