Single-Source Shortest Paths

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: O mapa abaixo apresenta uma parte do Backbone de Internet no Brasil e ao lado é apresentada a lista de adjacências entre os roteadores, com os seus respectivos custos de envio em um determinado momento.
Assumindo que roteamento dos dados é feito apenas através do protocolo OSPF (Open Shortest Path First), que é uma implementação do algoritmo de Dijkstra, qual seria o caminho percorrido pelos dados enviados do Rio Grande do Sul (RS) para a Bahia (BA)?


a. RS, PR, SP, MG, BA
b. RS, PR, SP, RJ, ES, BA
c. RS, SC, SP, MG, DF, RJ, ES, BA
d. RS, SC, SP, RJ, DF, MG, BA
e. NDA

Ideia original de: Anderson Coelho Weller

Graph algorithms

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

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 conectado (conexo) invertendo o sentido de apenas uma de suas arestas.
II - Para que G tenha apenas dois componentes fortemente conectados, faz-se necessário inverter o sentido de, no mínimo, 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 e II estão corretas.
b. I e III estão corretas.
c. II e III estão corretas.
d. I, II e III estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller