PROVA DE RECUPERAÇÃO DE ALGORITMOS EM

GRAFOS BCC, 1O. SEMESTRE DE 2004

1. [2 pontos] Descreva o que ocorre quando executamos o algoritmo de Tarjan para componentes fortemente conexas em um DAG.

2. [2 pontos] Lembre que um vertebrado é uma tripla (T, x, y), onde T é uma árvore e x e y são vértices de T (x é a cabeça do vertebrado e y é a cauda do vertebrado). Lembre que existe uma bijeção entre vertebrados com n vértices e funções f: [n] → [n], onde, como de usual, [n] = {1, …, n}. Lembre que uma folha em uma árvore é um vértice de grau 1. Descreva cuidadosamente como podemos estimar computacionalmente o número médio de folhas em uma árvore T com conjunto de vértices [n], para n razoavelmente grande (digamos, n = 20). Isto é, como podemos estimar

n^{−(n−2)} ∑(número de folhas em T),  (1)

onde a soma é sobre toda árvore T com conjunto de vértices [n]? (Nesta questão, não é necessário escrever código; basta você esboçar um procedimento, e dizer por que ele funciona.)

3. [2 pontos] Seja G = (V, E) um grafo. Podemos definir um grafo dirigido G⃗ = (V, E⃗) a partir de G, atribuindo a 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.

4. [2 pontos] Seja G um grafo e c: E(G) → ℝ uma função custo definida nas arestas de G. Seja T uma árvore geradora de G. Lembre que se e ∈ E(G) \ E(T), então o grafo T + e contém um único circuito, chamado de circuito fundamental de e em relação a T, freqüentemente denotado por C(e, T). Prove que são equivalentes:

(i) T é uma árvore geradora de custo mínimo em G. (ii) Toda e ∈ E(G) \ E(T) tem peso máximo dentre as arestas em

C(e, T).

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

(i) Seja A ⊂ E um conjunto de arestas de G que está contida em alguma árvore geradora mínima de G. Seja U ⊂ V tal que A ∩ E(U, V \ U) = ∅, onde E(U, V \ U) = {{u, w} ∈ E: u ∈ U, w ∈ V \ U} é o corte definido por U. Suponha que e ∈ E(U, V \ U) tem custo mínimo dentre as arestas em E(U, V \ U). Mostre que A ∪ {e} está contida em alguma árvore geradora mínima de G.

(ii) Descreva o algoritmo de Kruskal precisamente e prove sua corre-

ção. (iii) Descreva o algoritmo de Prim precisamente e prove sua correção.