MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: A matriz de peso abaixo, representa o grafo G=( V, E) acíclico orientado ponderado. Em cada célula dessa matriz, representada pela linha u e coluna v, é armazenado o peso w da aresta (u,v).

\	R	S	T	U	V
R	∞	1	2	∞	-1
S	∞	∞	∞	-3	-1
T	∞	-2	∞	-1	∞
U	∞	∞	∞	∞	1
V	∞	∞	∞	∞	∞

OBS: w = ∞, significa que  (u,v) ∉ E.

Denotamos por δ(u, v) o caminho mais curto a partir do vértice u até o vértice v no grafo.
Assinale a alternativa correta:

a) δ( R, V) = -2
b) δ( R, S) = 1
c) δ( T, V) = 0
d) δ( R, U) = 1
e) NDA


Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Considere o grafo abaixo, execute uma busca em profundidade. Suponha que as listas de adjacências estejam em ordem alfabética. Toda vez que for reiniciá-lo, pegue o primeiro vértice em ordem alfabética que ainda não foi visitado.
Com base na classificação das arestas da busca em profundidade, pode-se dizer que o algoritmo encontrará durante o percurso:

Lembrete: 

I) Arestas de Árvore: faz parte de uma árvore de busca em profundidade;

II) Aresta de Retorno: liga um descendente a um ancestral;

III) Arestas Diretas: liga um ancestral a um descendentes;

IV) Arestas Cruzadas: as demais.

a) 7 Arestas de Árvore e 2 Arestas de Retorno
b) 2 Arestas de Diretas e 2 Arestas de Cruzadas
c) 8 Arestas de Árvore e 1 Arestas de Retorno
d) 2 Arestas de Diretas e 3 Arestas de Cruzadas
e) NDA 

Ideia original de: Ademar Takeo Akabane