Resumêra

Qual das alternativas abaixo descreve corretamente a atualização feita pelo algoritmo de Warshall no passo k?

1.50 pontos Média

A) M[i,j] ← M[i,j] ∧ (M[i,k] ∨ M[k,j]) B) M[i,j] ← M[i,j] ∨ (M[i,k] ∧ M[k,j]) C) M[i,j] ← M[i,j] ∧ (M[i,k] ∧ M[k,j]) D) M[i,j] ← M[i,j] ∨ (M[i,k] ∨ M[k,j]) E) M[i,j] ← M[i,j] ∧ (M[i,k] ∨ M[j,k])

Resposta correta: B) M[i,j] ← M[i,j] ∨ (M[i,k] ∧ M[k,j])

Warshall adiciona um caminho indireto via k usando AND para verificar a existência de ambos os trechos e OR para manter caminhos já conhecidos.

Em um grafo não‑ponderado conectado, qual algoritmo garante encontrar o caminho mais curto entre um vértice origem e todos os demais?

2.50 pontos Difícil

A) Algoritmo de Prim B) Busca em profundidade (DFS) C) Busca em amplitude (BFS) D) Algoritmo de Floyd‑Warshall E) Algoritmo de Kruskal

Resposta correta: C) Busca em amplitude (BFS)

Em grafos não‑ponderados, BFS visita vértices por níveis, produzindo o menor número de arestas entre a origem e cada vértice.

Considere um grafo dirigido G com 5 vértices e a seguinte matriz de adjacência A. Qual é o valor de R[2,1] na matriz de acessibilidade R obtida pelo algoritmo de Warshall?

2.50 pontos Difícil

A) 0 B) 1, porque existe caminho 2 → 3 → 1 C) 1, porque há arco direto 2 → 1 D) 0, pois 2 não alcança 1 em nenhum caminho E) 1, porque o grafo é fortemente conexo

Resposta correta: B) 1, porque existe caminho 2 → 3 → 1

Na Figura 7.2 (exemplo do texto) há caminho de comprimento 2 de 2 para 1, portanto R[2,1]=1.

Um grafo simples conexo possui exatamente dois vértices de grau ímpar. Qual afirmação é verdadeira?

3.50 pontos Extrema

A) O grafo tem um caminho euleriano que começa em um dos vértices ímpares e termina no outro. B) O grafo tem um ciclo euleriano que inclui todos os vértices. C) O grafo não pode ter caminho euleriano. D) O grafo tem exatamente duas árvores geradoras mínimas. E) O grafo possui um ponto de articulação obrigatório.

Resposta correta: A) O grafo tem um caminho euleriano que começa em um dos vértices ímpares e termina no outro.

Teorema de Euler: existência de caminho euleriano ⇔ grafo conectado e 0 ou 2 vértices de grau ímpar.

Algoritmos de Grafos: Acessibilidade, Warshall e Caminhos Ótimos

Questões sobre o assunto