PROVA DE RECUPERAÇÃO DE ALGORITMOS EM GRAFOS BCC, 1O. SEMESTRE DE 2005

Instruções: faça três questões no total, distribuídas da seguinte forma:

(A) Faça uma questão dentre A1 e A2. (B) Faça uma questão dentre B1 e B2. (C) Faça uma questão dentre C1 e C2.

Seja muito cuidadoso na redação de suas respostas. Respostas implícitas ou sem justificativas claras valem pouco. A duração da prova é de duas horas.

A1. [3 pontos] Seja G = (V, E) um grafo. Podemos definir um grafo dirigido G⃗ = (V, E⃗) a partir de G, atribuindo para cada aresta e = {x, y} de G uma de suas duas possíveis orientações (formalmente, temos (x, y) ∈ E⃗ ou (y, x) ∈ E⃗, mas não ambos). Podemos chamar um tal G⃗ de uma orientação de G. Prove que existe uma orientação fortemente conexa de G se e só se G é conexo e não tem arestas de corte.

A2. [3 pontos] Seja G = (V, E) um grafo conexo e c: E → ℝ uma função custo definida nas arestas de G.

(i) Seja A ⊂ E um conjunto de arestas contida em alguma árvore geradora mínima (AGM) de (G, c). Seja S ⊂ V tal que o corte E(S, V \ S) é disjunto de A. Seja e ∈ E(S, V \ S) tal que c(e) = min{c(f): f ∈ E(S, V \ S)}, isto é, a aresta e tem custo mínimo dentre as arestas do corte E(S, V \ S). Prove que A ∪ {e} está contida em uma AGM de (G, c).

(ii) Considere o algoritmo abaixo:

(1) A ← ∅

(2) Enquanto |A| < |V | − 1, faça: (2.1) C ← uma componente conexa arbitrária de G[A] = (V, A) (2.2) e ← uma aresta de custo mínimo que liga C a alguma outra componente de G[A] (2.3) A ← A ∪ {e}

(3) Devolva A

Prove que, ao término da execução do algoritmo acima, G[A] é uma AGM de (G, c).

B1. [3.5 pontos] Seja G um grafo dirigido e c: E(G) → ℝ um função custo definida nos arcos de G. Por simplicidade, suponha que o custo de todo arco é não-negativo. Fixe s ∈ V (G), e suponha que todo vértice de G é acessível a partir de s. Para todo x ∈ V (G), escrevemos d_{c}(s, x) para o custo mínimo dos caminhos dirigidos de s a x. Um potencial p para (G, c) é uma função p: V (G) → ℝ tal que

p(v) ≤ p(u) + c(u, v) para todo (u, v) ∈ E(G).  (1)

Ademais, dizemos que um arco (u, v) é justo se vale a igualdade em (1). Suponha que um potencial p satisfaz as seguintes duas propriedades:

(a) p(s) = 0,

(b) todo vértice x ∈ V (G) é acessível a partir de s por um caminho que só contém arcos justos.

Prove os seguintes fatos:

(i) Para todo x ∈ V (G), vale que p(x) ≤ d_{c}(s, x). [Observação. Para este item, a única hipótese necessária sobre o potencial p é que p(s) ≤ 0.] (ii) Para todo x ∈ V (G), vale que d_{c}(s, x) ≤ p(x). [Sugestão. Seja (P_{k}) a seguinte asserção:

se x é acessível a partir de s através de um caminho com k arcos, todos eles justos, então d_{c}(s, x) ≤ p(x). Prove que (P_{k}) vale para todo k por indução em k.]

Conclua que d_{c}(s, x) = p(x) para todo vértice x de G. B2. [3.5 pontos] Esta questão trata de fluxos em redes.

(i) O que é uma rede (G, c)? (Lembre-se de mencionar os vértices especiais s e t.) (ii) O que é um fluxo de s a t em (G, c)? O que é o valor de um tal fluxo? (iii) O que é um corte que separa s de t? O que é a capacidade de um tal corte? (iv) Enuncie o teorema do fluxo máximo/corte mínimo.

(v) Prove o teorema do fluxo máximo/corte mínimo. C1. [3.5 pontos] Considere a implementação do algoritmo de Dijkstra visto em sala (Programa 21.1):

#define GRAPHpfs GRAPHspt
#define P (wt[v] + t->wt)
void GRAPHpfs(Graph G, int s, int st[], double wt[])
{ int v, w;  link t;
PQinit(); priority = wt;
for (v = 0; v < G->V; v++)
  { st[v] = -1; wt[v] = maxWT; PQinsert(v); }
wt[s] = 0.0; PQdec(s);
while (!PQempty())
  if (wt[v = PQdelmin()] != maxWT)
    for (t = G->adj[v]; t != NULL; t = t->next)
      if (P < wt[w = t->v])
        { wt[w] = P; PQdec(w); st[w] = v; }
}

Seja G o grafo de 5 vértices e 10 arcos com custos nos arcos dado por

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

Na notação acima, por exemplo, 0: 1(5) significa que há um arco de 0 para 1 de custo 5.

(i) Execute o Programa 21.1 no grafo G dado acima, com s = 0, ilustrando a evolução do algoritmo através de diagramas convenientes (uns 6 diagramas bastam).

(ii) Determine um potencial p: V (G) → ℝ para certificar que você encontrou as distâncias de 0 a todos os outros vértices em G em (i) acima corretamente (veja a Questão B1). Você deve dizer explicitamente por que sua função p é um potencial e por que ela de fato certifica as distâncias encontradas.

(iii) Descreva um algoritmo de complexidade O(n + m) que poderia ser executado após o Programa 21.1 para verificar que de fato as distâncias a partir de s foram determinadas corretamente. Por simplicidade, suponha que todos os vértices de G são acessíveis a partir de s. (Como você pode se livrar dessa hipótese?)

C2. [3.5 pontos] Seja G o grafo dirigido com 6 vértices e 10 arcos, com capacidades nos arcos, dado abaixo:

0: 1(16) 2(13)
1: 2(10) 3(12)
2: 1(4) 4(14)
3: 2(9) 5(20)
4: 3(7) 5(4)
5:

Na notação acima, por exemplo, “0: 1(16)” significa que há um arco de 0 para 1 de capacidade 16. No que segue, consideramos fluxos de s = 0 para t = 5 no grafo G acima.

(i) Desenhe o grafo dirigido G. (ii) Considere o fluxo de s para t em G dado por:

0: 1(11) 2(8)
1: 2(0) 3(12)
2: 1(1) 4(11)
3: 2(4) 5(15)
4: 3(7) 5(4)
5:

Acima, por exemplo, “0: 1(11)” significa que o fluxo no arco de 0 para 1 é 11. Encontre um caminho aumentador para o fluxo acima.

(iii) Encontre um fluxo de valor maior que o fluxo dado em (ii), usando o caminho aumen-

tador que você encontrou em (ii) para aumentar aquele fluxo. (iv) Encontre um fluxo máximo de s para t no G dado acima. Encontre um corte mínimo

que separa s de t em G. Dê um argumento para provar que seu fluxo é de fato máximo e seu corte é de fato mínimo.

(v) Um arco é vital se a redução de sua capacidade (por menor que seja essa redução) reduz o valor do fluxo máximo. Determine todos os arcos vitais em G dado acima. Justifique sua resposta.