pau

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-

Enunciado: Dado um grafo simples e não-orientado G = (V, E), cujo número de componentes conexos é 1, o algoritmo abaixo retorna um grafo caminho G_p = (V_p, E_p), tal que V_p = V. Considere que o algoritmo usa a representação por lista de adjacência; que a expressão G.V[i] retorna o i-ésimo vértice em V; que a expressão G.Adj[v][i] retorna o i-ésimo vértice da lista de adjacência do vértice v; que o grau mínimo dos vértices de G é 2.

1 toPathGraph(G)

2     Let G_p be a new Graph

3     for each v Є G.V

4         v.color = WHITE

5     G_p.V = G.V

6     v = G.V[1]

7     v.color = BLACK

8     For i = 1 to |V|-1

9          j = 1

10        do

11            u = G.Adj[v][j]

12            j = j + 1

13        while u.color == BLACK

14        G_p.Adj[v] ← u

15        G_p.Adj[u] ← v

16        v = u

17        v.color = BLACK

18    return G_p

É incorreto afirmar que:

1. Seu tempo de execução é Ω(|V|), onde |V| é o número de vértices de G.
2. O grafo G_p resultante possui |V| arestas.
3. O algoritmo não estaria mais correto se o grau mínimo dos vértices fosse 1.
4. Dado as restrições, é impossível que j, na linha 11, seja maior que |G.Adj[v]|, ou seja, maior que o grau do vértice v.
5. N.D.A.

Ideia original de: Paulo Henrique Hack de Jesus