1)
Suponha que você tenha uma rede neural que é transcrita pelo seguinte grafo:

Imagem no anexo

Usando o algoritmo de Dijkstra, encontre o caminho mais curto entre o ponto 1 até o ponto 6. Qual é o valor do custo?

Assinale a alternativa correta.

Alternativas:

a) 10
b) 12
c) 20
d) 25
e) 30

2) Na teoria de grafos, temos um gráfico bem famoso que é o grafo de Euler. COm base na definição desse grafo, julgue as asserções a seguir.

I. Um trajeto que inclua todas as arestas de um dado grafo G(V,A) é chamado de trajeto euleriano.

PORQUE

II. Dado um grafo G conexo, ele será um grafo euleriano se possuir um trajeto euleriano fechado.

A respeito das asserções assinale a opção correta:

Alternativas:

a) A asserção I é uma proposição falsa e a II, verdadeira.
b) As asserções I e II são proposições verdadeiras, mas a II não justifica a I.
c) A asserção I é uma proposição verdadeira e a II, falsa.
d) As asserções I e II são proposições verdadeiras e a I justifica a II.
e) As asserções I e II são proposições falsas.

3)
Sabemos que todo grafo G conexo possui pelo menos uma árvore que contém todos os seus vértices. E isso define o que chamamos de árvore geradora. A respeito desse conceito, julgue as asserções a seguir:

I. Uma árvore geradora de um grafo G é um subgrafo conexo e acíclico que possui todos os vértices originais de G e um subconjunto das arestas originais de G.

PORQUE
II. Todo grafo convexo possui apenas uma árvore geradora.

A respeito das asserções assinale a opção correta:

Alternativas:

a) A asserção I é uma proposição falsa e a II, verdadeira.
b) As asserções I e II são proposições verdadeiras, mas a II não justifica a I.
c) A asserção I é uma proposição verdadeira e a II, falsa.
d) As asserções I e II são proposições verdadeiras e a II justifica a I.
e) As asserções I e II são proposições falsas.

4) Uma árvore geradora de um grafo G é um subgrafo conexo e acíclico que possui todos os vértices originais de G e um subconjunto das arestas originais de G. Com base nesse conceito, julgue as alternativas a seguir:

I. A árvore geradora de custo mínimo é a árvore geradora de maior custo dentre todas as possíveis em um grafo.

II. Arvore geradora de custo máximo é a árvore geradora de maior custo dentre todas as possíveis em um grafo.

III. A determinação de ambas as árvores descritas pode ser feita em tempo determinístico polinomial por algoritmos de busca em largura.

É correto o que se afirma em:

Alternativas:

a) I, apenas.
b) II, apenas.
c) III, apenas.
d) I e II, apenas.
e) I e III, apenas.

5)
O algoritmo de Prim é um dos principais algoritmos para trabalhar com árvores geradoras. Esse algoritmo tem por princípio, incluir, de forma gulosa, um a um, os vértices da árvore geradora mínima e, a cada passo, acrescenta a aresta de menor peso incidente ao conjunto de vértices que já foram selecionados. Uma implementação desse algoritmo é dada por:



1. Escolha qualquer vértice i ¿ V;

2. T ¿ {i};

3. N ¿ V \ i;

4. Tmin ¿ Ø;

5. Enquanto |T| é diferente de n faça:

6. Encontre a aresta {j, k} ¿ A tal que j ¿ T, k ¿ N e djk é mínimo;

7. T ¿ T ¿ {k};

8. N ¿ N \ {k};

9. Tmin ¿ Tmin ¿ {j, k};

10. fim

Qual seria a entrada desse algoritmo?
Assinale a alternativa correta.

Alternativas:

a) Entrada: Grafo G = (V, A) e matriz de balanço D={dij} para todas as arestas {i, j}.

b) Entrada: Grafo G = (V, A) e matriz de pesos D={dij} para todas as arestas {i, j}.

c) Entrada: Grafo G = (V, A) e matriz de arestas D={dij} para todos os pesos {i, j}.

d) Entrada: Grafo G = (V, D) em que D={dij} é a matriz de pesos para todas as arestas {i, j}.

e) Entrada: Grafo G = (V, D) em que D={dij} é a matriz de balanço para todas as arestas {i, j}.