SEGUNDA 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!).

Faça no máximo 3 questões.

1. [4 pontos] Considere a implementação do algoritmo de Kosaraju vista em sala:

static int post[maxV], postR[maxV];
static int cnt0, cnt1;
void SCdfsR(Graph G, int w)
{ link t;
G->sc[w] = cnt1;
for (t = G->adj[w]; t != NULL; t = t->next)
  if (G->sc[t->v] == -1) SCdfsR(G, t->v);
post[cnt0++] = w;
}
int GRAPHsc(Graph G)
{ int v; Graph R = GRAPHreverse(G);
cnt0 = 0; cnt1 = 0;
for (v = 0; v < G->V; v++) R->sc[v] = -1;
for (v = 0; v < G->V; v++) if (R->sc[v] == -1) SCdfsR(R, v);
cnt0 = 0; cnt1 = 0;
for (v = 0; v < G->V; v++) G->sc[v] = -1;
for (v = 0; v < G->V; v++) postR[v] = post[v];
for (v = G->V-1; v >= 0; v--)
  if (G->sc[postR[v]] == -1)
    { SCdfsR(G, postR[v]); cnt1++; }
GRAPHdestroy(R);
return cnt1;
}

Seja G o grafo dirigido com 10 vértices e 20 arcos dado por

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

(i) Desenhe G. (ii) Simule a execução de GRAPHsc(G), ilustrando as etapas principais desta simulação. Idealmente, diga conceitualmente o que está acontecendo em cada fase do algoritmo.

2. [3 pontos] Sejam G = (V, E) um grafo e c: E → ℝ uma função custo nas arestas de G. Por simplicidade, suponha que c é injetora. Suponha que E = {e_{1}, …, e_{m}} e c(e_{1}) < c(e_{2}) < ⋯ < c(e_{m}).

(i) Sejam T uma árvore geradora de G e T_{0} a árvore geradora mínima (AGM) obtida executando-se o algoritmo de Kruskal sobre G. Suponha que T ≠ T_{0}. Dizemos que uma aresta e ∈ E distingue T de T_{0} se e pertence a uma das árvores mas não pertence a outra, isto é, e ∈ (E(T) \ E(T_{0})) ∪ (E(T_{0}) \ E(T)). Seja i_{0} o menor inteiro i tal que e_{i} distingue T e T_{0}. Prove que e_{i_{0}} ∈ E(T_{0}) \ E(T).

(ii) Seja i_{0} como em (i) e ponha f = e_{i_{0}}. Prove que existe e ∈ E \ {f} que distingue T e T_{0}

tal que T′ = T + f − e é uma árvore geradora de G. (iii) Prove que c(T′) < c(T), onde T′ é a árvore geradora em (ii) acima. (iv) Suponha que T é uma árvore geradora de (G, c) que não tem custo mínimo. Prove que

existem arestas e e f em G tais que T′ = T − e + f tem custo menor que T.

3. [3 pontos] Considere a rede a seguir, com as capacidades indicadas:

0: 1(6) 2(6) 3(4) 4(4)
1: 5(5)
2: 1(4) 6(6)
3: 6(5) 7(8)
4: 3(5)
5: 6(4) 9(4)
6: 9(8)
7: 8(5) 9(4)
8: 4(4) 9(3)
9:

Na notação acima, por exemplo, 0: 1(6) significa que há um arco de 0 para 1 com capacidade 6. Suponha que s = 0 e t = 9.

(i) Desenhe a rede, com as capacidades indicadas. (ii) Encontre um fluxo máximo de s para t nesta rede. (iii) Prove que o fluxo que você deu em (ii) é de fato máximo.

4. [3 pontos]

(i) Enuncie o teorema de Hall, que dá uma condição necessária e suficiente para a existência de certos emparelhamentos em grafos.

(ii) Seja B um grafo bipartido com bipartição V = U ∪ W. Suponha que |U| = |W | = m e que todos os vértices de B têm grau maior que m/2. Prove que B tem um emparelhamento de tamanho m.