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

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 num grafo orientado todo vertice tem uma aresta saindo entao este grafo contem um ciclo orientado
  2. VERDADEIRO OU FALSO: o grafo orientado D* obtido pela contracao das componentes fortemente conexas de um grafo orientado D e' aciclico
  3. VERDADEIRO OU FALSO: Se um grafo orientado G e' aciclico, da' para ordanar seus vertices como v1, v2, ..., vn de modo que todas as arestas vIvJ vao "pra frente", ou seja, I < J.

Soluções - Discutidas em classe em 2002-08-19

  1. Resposta 1:
        fato: O grafo é finito.
        hipótese: não há ciclos.

       0 ------> 0 ------> 0 ------> 0 ------> ...
      v1        v2        v3        v4
    Sai do vértice v1 uma aresta orientada. Como não há ciclos, deve ser para um outro vértice v2. O mesmo ocorre para v2: sai uma aresta orientada, não pode ser para v1 por não haver ciclos, logo há um v3. De v3, igualmente, para um v4. Porém, como o grafo é finito, temos uma contradição.

    Resposta 2:
    Considere um caminho de comprimento máximo em

       0 ------> 0 ------> ... ------> 0
      v1        v2                    vk
    Como todo vértice tem uma aresta saindo, então ou vk teria que voltar e ligar a alguém, formando um ciclo, ou não seria máximo.
  2. Sugestão para resolução:
    Suponha que D* tenha um ciclo. Então há vértices vi e vs com arestas orientadas em D* entrando e saindo de um vértice vc que representa uma contração e com o qual forma um ciclo. Porém então vc estaria fortemente conectado com os vértices deste ciclo e o ciclo teria sido contraído junto com vc.
  3. Resposta:
    Escolhe-se um vértice que tem nao uma aresta que entra. Este recebe um número, digamos 1, e é retirado do grafo. O processo então se repete, dando-se números consecutivos 1, 2, etc. aos vértices retirados. Ao final temos a ordem desejada ( v(1), ..., v(n-1), v(n) ).

    Obs1: Imagine que os vértices representam tarefas de um projeto, com as arestas representando tarefas que necessariamente têm que preceder outras. A ordem final garante que as tarefas serão realizadas numa ordem adequada.

    Obs2: Este processo é chamado de ordenação topológica.