Resumêra

Questão 1 – Média

1.50 pontos Média

Qual das alternativas abaixo representa corretamente a matriz de adjacência do grafo com vértices {1,2,3} e arcos (1,2), (2,3) e (3,3)?

A)

0 1 0
0 0 1
0 0 1

B)

0 1 0
0 0 0
0 0 1

C)

0 1 0
0 0 1
0 0 0

D)

1 0 0
0 1 0
0 0 1

E)

0 0 1
1 0 0
0 1 0

Resposta correta: A)

Os 1 nas posições (1,2), (2,3) e (3,3) indicam exatamente os arcos solicitados.

Questão 2 – Difícil

2.50 pontos Difícil

Dada a matriz de adjacência \(M=\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}\), qual é a entrada \(M^{2}_{13}\) (produto booleano)?

Resposta correta: B)

Para \(M^{2}_{13}\) calculamos \(\bigvee_{k=1}^{3}(M_{1k}\land M_{k3}) = (0\land0)\lor(1\land1)\lor(0\land0)=1\).

Questão 3 – Difícil

2.50 pontos Difícil

Qual das afirmações abaixo está correta sobre a relação de acessibilidade em um grafo dirigido?

A) É sempre simétrica. B) Coincide com a relação de adjacência. C) É o fecho transitivo da relação de adjacência. D) Não inclui laços reflexivos. E) Depende do peso dos arcos.

Resposta correta: C)

O fecho transitivo contém todas as pares (v_i , v_j) para os quais existe algum caminho, ou seja, a definição de acessibilidade.

Questão 4 – Extrema

3.50 pontos Extrema

Considere o grafo com matriz de adjacência \(M=\begin{pmatrix} 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0 \end{pmatrix}\). Qual é a matriz de acessibilidade \(R\) (fecho transitivo) desse grafo?

A)

B)

C)

D)

E)

Resposta correta: A)

O grafo forma um ciclo que permite alcançar qualquer vértice a partir de qualquer outro; portanto, todas as entradas são 1.

Grafos direcionados, relações binárias e acessibilidade

Questões sobre o assunto