MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-065

Enunciado: A partir do grafo orientado G = (V, E), com V = {1,2,3,4,5,6} e E = {(1,3), (2,6), (3,2), (3,5), (5,1), (5,4), (6,2), (6,4)}, analise as seguintes afirmações:

I - Conseguimos tornar G um grafo fortemente conexo invertendo o sentido de apenas uma de suas arestas.
II - Para que G tenha exatamente dois componentes fortemente conexos, faz-se necessário inverter o sentido de mais de duas de suas arestas.
III - É possível obter uma ordenação topológica para o grafo G, caso sejam removidas duas de suas arestas.

Assinale a alternativa correta:

a. I, II e III estão corretas.
b. apenas II e III estão corretas.
c. apenas I e III estão corretas.
d. apenas I e II estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller