TERCEIRA PROVA DE ALGORITMOS EM GRAFOS BCC, 1O. SEMESTRE DE 2004

1. [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}. O diâmetro diam(G) de um grafo conexo G é o máximo das distâncias entre dois vértices em G, isto é,

diam(G) = max{dist_{G}(x, y): x, y ∈ V (G)}.  (1)

Descreva cuidadosamente como podemos estimar computacionalmente o diâmetro médio de uma árvore T com n vértices, para n razoavelmente grande (digamos, n = 20). Isto é, como podemos estimar

n^{−(n−2)} ∑ diam(T),  (2)

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

2. [2 pontos] Considere o seguinte trecho de código, que implementa a essência do algoritmo de Warshall:

for (i = 0; i < V; i++)
  for (s = 0; s < V; s++)
    for (t = 0; t < V; t++)
      if (A[s][i] && A[i][t])
        A[s][t] = 1;

(i) Execute o trecho de código acima na matriz

A = [\begin{matrix}1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 \end{matrix}]  (3)

(Você deve dizer o estado da matriz A após cada iteração do for mais externo.)

(ii) Generalize (i): considere o grafo dirigido G_{n} com n vértices generalizando o grafo em (i). (Assim, G_{6} é o grafo do item (i).) Descreva a matriz A correspondente ao grafo G_{n} após a execução do corpo do for externo para um i genérico (0 ≤ i < n = V).

3. [2 pontos] (Nesta questão, os grafos são não-orientandos.) Suponha que temos G = (V, E) um grafo com função custo nas arestas c: E → ℝ. Seja ainda s um vértice fixo de G. Por simplicidade, suponha c(e) positivo para todo e ∈ E. Podemos definir uma árvore de caminhos mínimos com raiz s como sendo uma árvore geradora T de G que tem a propriedade de que, para todo t ∈ V, a distância dist_{G}(s, t) de s a t em G é igual à distância dist_{T} (s, t) em T. É verdade que uma tal árvore de caminhos mínimos com raiz s é necessariamente uma árvore geradora mínima? Prove ou dê um contra-exemplo. Se você for dar um contra-exemplo, ele deve ser tal que 0 < c(e) ≤ 1 para todo e, mas o custo das árvores em questão (árvore de caminhos mínimos e árvore geradora mínima) diferem de pelo menos 10^{10}.

4. [4 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.