PRIMEIRA PROVA DE ALGORITMOS EM GRAFOS BCC, 1O. SEMESTRE DE 2007

Instruções:

1. Não destaque as folhas do caderno de soluções.

2. A prova pode ser feita a lápis. Cuidado com a legibilidade.

3. Não é permitido o uso de folhas avulsas para rascunho.

4. Não é necessário apagar rascunhos no caderno de soluções.

5. Asserções imprecisas valem pouco. Justifique suas asserções (dentro do razoável!).

1. [3 pontos] Um (n, m)-digrafo é um grafo dirigido com n vértices e m arcos. Desenhe, a menos de isomorfismo, todos os (2, 2)-digrafos (são quatro) e todos os (3, 3)-digrafos. (Dê seus diagramas de forma organizada.)

2. [4 pontos] Considere a função recursiva

void dfsR(Graph G, Edge e)
  { link t; int w = e.w;
    pre[w] = cnt++; st[e.w] = e.v;
    for (t = G->adj[w]; t != NULL; t = t->next)
      if (pre[t->v] == -1)
        dfsR(G, EDGE(w, t->v));
  }

Seja G o grafo de 10 vértices e 13 arestas dado por

0: 3            |    5: 4 3 1
1: 6 2 3 5      |    6: 2 1 7
2: 3 6 1        |    7: 6
3: 2 0 5 1      |    8: 9 4
4: 9 5 8        |    9: 4 8

(i) Desenhe G. (ii) Simule a execução de dfsR(G, {0,0}) (busca em profundidade (BeP) a partir do vértice 0). (iii) Desenhe a árvore de BeP obtida. (iv) Caracterize as arestas de corte de G em termos de sua árvore de BeP; esta caracterização deve ser aquela em que se baseia o algoritmo de tempo linear que vimos nas aulas para a identificação de tais areastas (fale, necessariamente, do vetor low[] etc).

3. [3 pontos] Suponha que executamos uma busca em profundidade (BeP) em um grafo conexo G a partir de um vértice r. Suponha que orientamos todas as arestas da árvore de BeP ‘para baixo’ (desenhando a árvore ‘com a raiz r para cima’) e orientamos todas as arestas fora da árvore de BeP ‘para cima’. Obtemos assim um grafo dirigido G⃗. (i) Mostre que todo vértice de G é acessível a partir de r por um caminho dirigido. (ii) Suponha agora que G não tem arestas de corte. Mostre que r é acessível a partir de todo vértice de G por um caminho dirigido. Argumente cuidadosamente; em particular, diga exatamente onde em seu argumento você usa o fato de G não ter arestas de corte. O resultado valeria sem essa hipótese? Justifique.