Teoria dos Grafos_Questionario 2

Prévia do material em texto

• Pergunta 1 
0,5 em 0,5 pontos 
 
Considere as seguintes asserções sobre o algoritmo de Kruskal: 
 
I – Todas as arestas são ordenadas por peso. 
II – Verifica-se cada aresta da sequência ordenada para ver se pode ser considerada parte 
da árvore em construção. 
III – Uma aresta é adicionada à arvore se não aparece nenhum ciclo depois de sua inclusão. 
 
São asserções verdadeiras: 
 
Resposta Selecionada: a. 
I, II e III. 
Respostas: a. 
I, II e III. 
 
b. 
Apenas I e II. 
 
c. 
Apenas I e III. 
 
d. 
Apenas II e III. 
 
e. 
Apenas III. 
Comentário da 
resposta: 
Resposta: a) 
Comentário: as três asserções, na ordem I, II e III, apresentam o 
algoritmo popular idealizado por Joseph Kruskal. 
 
 
• Pergunta 2 
0,5 em 0,5 pontos 
 
O algoritmo que calcula o caminho mínimo de um nó particular a qualquer 
outro nó: 
 
Resposta Selecionada: e. 
Bellman-Ford. 
Respostas: a. 
Kruskal. 
 
b. 
Dijkstra. 
 c. 
 
Warshall. 
 
d. 
Floyd. 
 
e. 
Bellman-Ford. 
Comentário 
da resposta: 
Resposta: e) 
Comentário: o algoritmo de Bellman-Ford executa uma série 
de cálculos, procurando encontrar caminhos mínimos, 
sucessivamente, de comprimento 1, depois de comprimento 
2, e assim por diante, até o comprimento máximo n-1. Desta 
forma, o algoritmo de Bellman-Ford calcula o caminho mínimo 
de um nó específico para qualquer outro nó. 
 
• Pergunta 3 
0,5 em 0,5 pontos 
 
Considere as seguintes asserções: 
 
I – As arestas de um grafo podem estar associadas a certos pesos que 
representam, por exemplo, distâncias entre cidades. 
II – As arestas de um grafo podem estar associadas a certos pesos que 
representam, por exemplo, tempos que separam a execução de certas 
tarefas. 
III – As arestas de um grafo podem estar associadas a certos pesos que 
representam, por exemplo, custos de se transmitir informação entre 
localidades. 
 
São corretas as afirmações: 
 
Resposta Selecionada: d. 
I, II e III. 
Respostas: a. 
Apenas I. 
 
b. 
Apenas II. 
 c. 
 
Apenas III. 
 
d. 
I, II e III. 
 
e. 
Apenas I e II. 
Comentário da 
resposta: 
Resposta: d) 
Comentário: quando está se determinando o caminho mais 
curto de um vértice v para o vértice u, a informação sobre as 
distâncias entre vértices intermediários w tem que ser 
registrada. 
 
• Pergunta 4 
0,5 em 0,5 pontos 
 
A respeito do algoritmo concebido por Stephen Warshal e implementado 
por Robert Floyd, é incorreto afirmar: 
 
Resposta 
Selecionada: 
d. 
Seu desempenho em consumo de memória é 
combinatório. 
Respostas: a. 
Encontra todos os menores caminhos a partir de um 
vértice qualquer para qualquer outro. 
 
b. 
O grafo pode incluir pesos negativos. 
 
c. 
Trata-se de um algoritmo O(n3). 
 
d. 
Seu desempenho em consumo de memória é 
combinatório. 
 
e. 
Faz uso de matriz de adjacência modificada. 
Comentário Resposta: d) 
 
da resposta: Comentário: a afirmação d) é incorreta. O algoritmo faz uso 
apenas de 3 variáveis para indexar a matriz de adjacência 
modificada, de dimensão n x n, em três laços aninhados. 
Assim sendo, não apresenta desempenho combinatório em 
consumo de memória. 
 
• Pergunta 5 
0,5 em 0,5 pontos 
 
Considere o seguinte grafo e a matriz de adjacência modificada. Deseja-se o 
caminho mínimo entre os nós A e F, empregando-se o algoritmo de Dijkstra. 
 
Em uma etapa inicial, o algoritmo inicializa o conjunto de nós IN com: 
 
Resposta Selecionada: a. 
O nó A. 
Respostas: a. 
O nó A. 
 
b. 
O nó B. 
 
c. 
O nó F. 
 
d. 
O nó C. 
 
e. 
Conjunto vazio. 
Comentário da 
resposta: 
Resposta: a) 
Comentário: como o caminho mínimo estabelecido é entre 
o nó A e F, inicializa-se o conjunto de nós In com o nó A. 
 
 
• Pergunta 6 
0,5 em 0,5 pontos 
 
Na etapa inicial do algoritmo de Dijkstra, mencionado na questão 5, os 
vetores distância d e nó anterior s, podem ser representados pela tabela: 
 
Resposta Selecionada: a. 
 
Respostas: a. 
 
 
b. 
 
 
c. 
 
 
d. 
 
 
e. 
 
Comentário da 
resposta: 
Resposta: a) 
Comentário: na etapa inicial, os vetores d e s, são obtidos a 
partir da matriz de adjacência modificada do grafo. 
 
• Pergunta 7 
0,5 em 0,5 pontos 
 
Na segunda iteração do algoritmo de Dijkstra para o caminho mínimo entre 
os nós A e F, o nó selecionado para o conjunto IN é B, porque: 
 
Resposta Selecionada: d. 
É o de menor distância. 
Respostas: a. 
É adjacente a A. 
 
b. 
É lexicograficamente sucessor de A. 
 
c. 
É selecionado empiricamente. 
 
 
d. 
É o de menor distância. 
 
e. 
O nó B não é o selecionado. 
Comentário da 
resposta: 
Resposta: d) 
Comentário: o algoritmo seleciona para o conjunto de nós 
IN aquele de menor distância. 
 
• Pergunta 8 
0,5 em 0,5 pontos 
 
Na terceira iteração do algoritmo de Dijkstra para o caminho mínimo entre 
os nós A e F: 
 
I – O nó C é selecionado. 
 
PORQUE 
 
II – Comparam-se as distâncias entre o nó A e os demais C, D, E e F, 
passando-se por B, ou não. Os valores do vetor d e o vetor s podem ser 
reescritos segundo o menor valor resultante da comparação. Ao final 
obtém-se o nó C como aquele que apresenta o menor valor no vetor d. 
 
Pode-se afirmar que: 
 
Resposta Selecionada: a. 
I e II são verdadeiras e II justifica I. 
Respostas: a. 
I e II são verdadeiras e II justifica I. 
 
b. 
I e II são verdadeiras, mas II não justifica I. 
 
c. 
Apenas I é verdadeira. 
 
d. 
Apenas II é verdadeira. 
 
 
e. 
I e II são afirmações falsas. 
Comentário da 
resposta: 
Resposta: a) 
Comentário: Na terceira iteração, são realizados os 
seguintes cálculos: 
d[C] = min(4, 2 +A[B, C]) = min(4,3) = 3 
d[D] = min(∞, 2 +A[B, D]) = min(∞,2+4) = 6 
d[E] = min(∞, 2 +A[B, E]) = min(∞,2+2) = 4 
d[F] = min(∞, 2 +A[B, F]) = min(∞,2+ ∞) = ∞ 
Os vetores d e C são sobrescritos, conforme se segue: 
 
Seguidamente o nó C é selecionado para o conjunto IN. 
 
• Pergunta 9 
0,5 em 0,5 pontos 
 
Na quarta iteração do algoritmo de Dijkstra para o caminho mínimo entre 
os nós A e F: 
 
I – São realizados os seguintes cálculos. d[D]= min(6, 3 +A[C, D]) 
=min(6,3+4)=6 
d[E]= min(4, 3 +A[C, E]) =min(4,3+3)=4. d[F]= min(∞, 3 +A[C, F]) =min(∞,3+ ∞)= 
II – Os vetores d e s são reescritos. 
III – O nó E é selecionado. 
 
São corretas as afirmações: 
 
Resposta Selecionada: e. 
I, II e III. 
Respostas: a. 
Apenas I. 
 
b. 
Apenas I e II. 
 
c. 
Apenas I e III. 
 d. 
 
Apenas II e III. 
 
e. 
I, II e III. 
Comentário da 
resposta: 
Resposta: e) 
Comentário: a partir dos cálculos efetuados, os vetores d e s 
resultam iguais ao da iteração anterior e por isto o nó E é 
selecionado. 
 
• Pergunta 10 
0,5 em 0,5 pontos 
 
Na quinta iteração do algoritmo de Dijkstra para o caminho mínimo entre 
os nós A e F, o nó F é selecionado. O caminho mínimo obtido é: 
 
Resposta Selecionada: d. 
A, B, E, F. 
Respostas: a. 
A, B, C, D, F. 
 
b. 
A, B, C, E, F. 
 
c. 
B, A, C, F. 
 
d. 
A, B, E, F. 
 
e. 
F, E, B, C, A. 
Comentário da 
resposta: 
Resposta: d) 
Comentário: na quinta iteração os seguintes cálculos foram 
efetuados: d[D] = min(6, 4 +A[E, D]) = min(6,4+3)=6, d[F] = 
min(∞, 4 +A[E, F]) = min(∞,4+ 2)= 6 
Os vetores d e s, são reescritos. 
 
O nó F é selecionado. Tem-se que o antecessor de F é E, que 
por sua vez é antecedido por B, e este, antecedido por A. 
 
Confira-se no vetor s 
Logo o caminho mínimo é: A, B, E, F. 
 
• Pergunta 1 
0,5 em 0,5 pontos 
 
Considere as seguintes asserções sobre o algoritmo de Kruskal: 
 
I – Todas as arestas são ordenadas por peso. 
II – Verifica-se cada aresta da sequência ordenada para ver se pode ser considerada parte 
da árvore em construção. 
III – Uma aresta é adicionada à arvore se não aparece nenhum ciclo depois de sua inclusão. 
 
São asserções verdadeiras: 
 
Resposta Selecionada: a. 
I, II e III.Respostas: a. 
I, II e III. 
 
b. 
Apenas I e II. 
 
c. 
Apenas I e III. 
 
d. 
Apenas II e III. 
 
e. 
Apenas III. 
Comentário da 
resposta: 
Resposta: a) 
Comentário: as três asserções, na ordem I, II e III, apresentam o 
algoritmo popular idealizado por Joseph Kruskal. 
 
 
• Pergunta 2 
0,5 em 0,5 pontos 
 
O algoritmo que calcula o caminho mínimo de um nó particular a qualquer 
outro nó: 
 
Resposta Selecionada: e. 
Bellman-Ford. 
Respostas: a. 
Kruskal. 
 b. 
 
Dijkstra. 
 
c. 
Warshall. 
 
d. 
Floyd. 
 
e. 
Bellman-Ford. 
Comentário 
da resposta: 
Resposta: e) 
Comentário: o algoritmo de Bellman-Ford executa uma série 
de cálculos, procurando encontrar caminhos mínimos, 
sucessivamente, de comprimento 1, depois de comprimento 
2, e assim por diante, até o comprimento máximo n-1. Desta 
forma, o algoritmo de Bellman-Ford calcula o caminho mínimo 
de um nó específico para qualquer outro nó. 
 
• Pergunta 3 
0,5 em 0,5 pontos 
 
Considere as seguintes asserções: 
 
I – As arestas de um grafo podem estar associadas a certos pesos que 
representam, por exemplo, distâncias entre cidades. 
II – As arestas de um grafo podem estar associadas a certos pesos que 
representam, por exemplo, tempos que separam a execução de certas 
tarefas. 
III – As arestas de um grafo podem estar associadas a certos pesos que 
representam, por exemplo, custos de se transmitir informação entre 
localidades. 
 
São corretas as afirmações: 
 
Resposta Selecionada: d. 
I, II e III. 
Respostas: a. 
Apenas I. 
 b. 
 
Apenas II. 
 
c. 
Apenas III. 
 
d. 
I, II e III. 
 
e. 
Apenas I e II. 
Comentário da 
resposta: 
Resposta: d) 
Comentário: quando está se determinando o caminho mais 
curto de um vértice v para o vértice u, a informação sobre as 
distâncias entre vértices intermediários w tem que ser 
registrada. 
 
• Pergunta 4 
0,5 em 0,5 pontos 
 
A respeito do algoritmo concebido por Stephen Warshal e implementado 
por Robert Floyd, é incorreto afirmar: 
 
Resposta 
Selecionada: 
d. 
Seu desempenho em consumo de memória é 
combinatório. 
Respostas: a. 
Encontra todos os menores caminhos a partir de um 
vértice qualquer para qualquer outro. 
 
b. 
O grafo pode incluir pesos negativos. 
 
c. 
Trata-se de um algoritmo O(n3). 
 
d. 
Seu desempenho em consumo de memória é 
combinatório. 
 e. 
 
Faz uso de matriz de adjacência modificada. 
Comentário 
da resposta: 
Resposta: d) 
Comentário: a afirmação d) é incorreta. O algoritmo faz uso 
apenas de 3 variáveis para indexar a matriz de adjacência 
modificada, de dimensão n x n, em três laços aninhados. 
Assim sendo, não apresenta desempenho combinatório em 
consumo de memória. 
 
• Pergunta 5 
0,5 em 0,5 pontos 
 
Considere o seguinte grafo e a matriz de adjacência modificada. Deseja-se o 
caminho mínimo entre os nós A e F, empregando-se o algoritmo de Dijkstra. 
 
Em uma etapa inicial, o algoritmo inicializa o conjunto de nós IN com: 
 
Resposta Selecionada: a. 
O nó A. 
Respostas: a. 
O nó A. 
 
b. 
O nó B. 
 
c. 
O nó F. 
 
d. 
O nó C. 
 
e. 
Conjunto vazio. 
Comentário da 
resposta: 
Resposta: a) 
Comentário: como o caminho mínimo estabelecido é entre 
o nó A e F, inicializa-se o conjunto de nós In com o nó A. 
 
 
• Pergunta 6 
0,5 em 0,5 pontos 
 
Na etapa inicial do algoritmo de Dijkstra, mencionado na questão 5, os 
vetores distância d e nó anterior s, podem ser representados pela tabela: 
Resposta Selecionada: a. 
 
Respostas: a. 
 
 
b. 
 
 
c. 
 
 
d. 
 
 
e. 
 
Comentário da 
resposta: 
Resposta: a) 
Comentário: na etapa inicial, os vetores d e s, são obtidos a 
partir da matriz de adjacência modificada do grafo. 
 
 
• Pergunta 7 
0,5 em 0,5 pontos 
 
Na segunda iteração do algoritmo de Dijkstra para o caminho mínimo entre 
os nós A e F, o nó selecionado para o conjunto IN é B, porque: 
 
Resposta Selecionada: d. 
É o de menor distância. 
Respostas: a. 
É adjacente a A. 
 
b. 
É lexicograficamente sucessor de A. 
 
 
c. 
É selecionado empiricamente. 
 
d. 
É o de menor distância. 
 
e. 
O nó B não é o selecionado. 
Comentário da 
resposta: 
Resposta: d) 
Comentário: o algoritmo seleciona para o conjunto de nós 
IN aquele de menor distância. 
 
• Pergunta 8 
0,5 em 0,5 pontos 
 
Na terceira iteração do algoritmo de Dijkstra para o caminho mínimo entre 
os nós A e F: 
 
I – O nó C é selecionado. 
 
PORQUE 
 
II – Comparam-se as distâncias entre o nó A e os demais C, D, E e F, 
passando-se por B, ou não. Os valores do vetor d e o vetor s podem ser 
reescritos segundo o menor valor resultante da comparação. Ao final 
obtém-se o nó C como aquele que apresenta o menor valor no vetor d. 
 
Pode-se afirmar que: 
 
Resposta Selecionada: a. 
I e II são verdadeiras e II justifica I. 
Respostas: a. 
I e II são verdadeiras e II justifica I. 
 
b. 
I e II são verdadeiras, mas II não justifica I. 
 
c. 
Apenas I é verdadeira. 
 
 
d. 
Apenas II é verdadeira. 
 
e. 
I e II são afirmações falsas. 
Comentário da 
resposta: 
Resposta: a) 
Comentário: Na terceira iteração, são realizados os 
seguintes cálculos: 
d[C] = min(4, 2 +A[B, C]) = min(4,3) = 3 
d[D] = min(∞, 2 +A[B, D]) = min(∞,2+4) = 6 
d[E] = min(∞, 2 +A[B, E]) = min(∞,2+2) = 4 
d[F] = min(∞, 2 +A[B, F]) = min(∞,2+ ∞) = ∞ 
Os vetores d e C são sobrescritos, conforme se segue: 
 
Seguidamente o nó C é selecionado para o conjunto IN. 
 
• Pergunta 9 
0,5 em 0,5 pontos 
 
Na quarta iteração do algoritmo de Dijkstra para o caminho mínimo entre 
os nós A e F: 
 
I – São realizados os seguintes cálculos. d[D]= min(6, 3 +A[C, D]) 
=min(6,3+4)=6 
d[E]= min(4, 3 +A[C, E]) =min(4,3+3)=4. d[F]= min(∞, 3 +A[C, F]) =min(∞,3+ ∞)= 
II – Os vetores d e s são reescritos. 
III – O nó E é selecionado. 
 
São corretas as afirmações: 
 
Resposta Selecionada: e. 
I, II e III. 
Respostas: a. 
Apenas I. 
 
b. 
Apenas I e II. 
 c. 
 
Apenas I e III. 
 
d. 
Apenas II e III. 
 
e. 
I, II e III. 
Comentário da 
resposta: 
Resposta: e) 
Comentário: a partir dos cálculos efetuados, os vetores d e s 
resultam iguais ao da iteração anterior e por isto o nó E é 
selecionado. 
 
• Pergunta 10 
0,5 em 0,5 pontos 
 
Na quinta iteração do algoritmo de Dijkstra para o caminho mínimo entre 
os nós A e F, o nó F é selecionado. O caminho mínimo obtido é: 
 
Resposta Selecionada: d. 
A, B, E, F. 
Respostas: a. 
A, B, C, D, F. 
 
b. 
A, B, C, E, F. 
 
c. 
B, A, C, F. 
 
d. 
A, B, E, F. 
 
e. 
F, E, B, C, A. 
Comentário da 
resposta: 
Resposta: d) 
Comentário: na quinta iteração os seguintes cálculos foram 
efetuados: d[D] = min(6, 4 +A[E, D]) = min(6,4+3)=6, d[F] = 
min(∞, 4 +A[E, F]) = min(∞,4+ 2)= 6 
Os vetores d e s, são reescritos. 
 
 
O nó F é selecionado. Tem-se que o antecessor de F é E, que 
por sua vez é antecedido por B, e este, antecedido por A. 
Confira-se no vetor s 
Logo o caminho mínimo é: A, B, E, F. 
 
•