tha

MO417 - Questão para a prova oral

Número:

Enunciado: Considere um grafo não orientado G com vértices pertencentes ao conjunto {40, 98, 7, 105, 20, 13, 10, 3, 49, 402} e arestas entre x e y quando x mod y = 0. Considere também a operação CONNECTED-COMPONENTS com o seguinte código abaixo:

CONNECTED-COMPONENTS(G)
para cada vertice v pertencente a V[G]
     MAKE-SET(v)
para cada aresta (u,v) pertencente a E[G]
     if (FIND-SET(u) != FIND-SET(v))
            UNION(u,v)

Com relação às quatro afirmações abaixo, assinale a alternativa correta:
I. O grafo G possui um total de 6 arestas.
II. Durante a execução de CONNECTED-COMPONENTS sobre G, FIND-SET e UNION são chamados respectivamente16 e 6 vezes.
III. O grafo G possui 3 componentes conexas.
IV. Um componente conexo do grafo G é {40, 20, 10}.

A) As afirmações II e IV são corretas
B) As afirmações I, II e IV são corretas
C) As afirmações I e III são corretas
D) Apenas a afirmação I é correta
E) N.D.A

Ideia original de: Thaís Harumi Ussami