MO417 - Questão para a prova oral

Número:

Enunciado: Dadas as matrizes predecessoras gerada pela execução do algoritmo Floyd-Warshall sobre um grafo orientado, indique qual o caminho mais curto com origem no vértice 3 e destino no vértice 1.

a) 3->2->1
b) 3->2->4->1
c) 3->4->2->1
d)3->1
e) NDA 

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Um grafo bipartido é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos U e V tais que toda aresta conecta um vértice em U a um vértice em V. Sua bipartição pode ser definida pela paridade das distâncias de todos os vértices em relação a um vértice s escolhido arbitrariamente: o conjunto U consiste dos vértices a uma distância par de s e o conjunto V consiste dos vértices a uma distância ímpar de s. Para calcular as distâncias dos vértices em relação a s pode-se aplicar a busca em largura.

Dado o grafo abaixo determine quais vértices pertencem a U e quais pertencem a V.

a) U={2,4,6} e V={1,3,5}

b) U={1,3,6} e V={2,4,5}

c) U={1,4,5,6} e V={2,3}

d) U={1,3,4,5} e V={2,6}

e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Considere que um vértice s é descoberto na primeira vez em que é encontrado durante o procedimento de busca em largura ou em profundidade. Considere também que quando possível, vértices de numeração menor são descobertos primeiro, ou seja, numa dada interação onde 1 e 2 são vértices adjacentes a s, o vértice 1 é descoberto primeiro.

Dado o grafo abaixo, partindo do vértice 1, defina qual dos dois algoritmos descobre mais rápido os vértices 4, 7 e 8, respectivamente. Isto quer dizer que, o algoritmo X descobre o vértice s percorrendo menos vértices do que o algoritmo Y percorre.

a) busca em profundidade, profundidade e largura

b) busca em profundidade, largura e profundidade

c) busca em largura, profundidade e largura

d) busca em largura, largura e largura
e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo