MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Uma empresa tem sua fábrica (onde os produtos são produzidos) localizada na cidade S e seu centro de distribuição (onde os produtos são armazenados para serem distribuídos) localizado na cidade T. Segundo o grafo abaixo, que mostra as rodovias que conectam as diversas cidades (vértices) e o número máximo de caminhões que podem trafegar por cada rodovia (arestas e seus pesos), qual é o número máximo de caminhões que a empresa pode enviar para o seu centro de distribuição?

A) 13

B) 22

C) 12

D) 11

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado o grafo dirigido G = (V, E), a função de pesos das areas w e os algoritmos abaixo:

Assinale a alternativa que contém o valor d correto de cada um dos vértices do grafo G, após a execução do algoritmo DIJKSTRA-MODIFIED(G, w, z).

DIJKSTRA-MODIFIED(G, w, s)
  INITIALIZE-SINGLE-SOURCE-MODIFIED(G, s)
  Q = G.V
  while Q != ∅
    u = EXTRACT-MAX(Q)
    for each vertex v ∈ G.adj[u]
      RELAX-MODIFIED(u, v, w)

INITIALIZE-SINGLE-SOURCE-MODIFIED(G, s)
  for each vertex v ∈ G.V
    v.d = -∞
  s.d = 0

RELAX-MODIFIED(u, v, w)
  if v.d < u.d + w(u, v)
    v.d = u.d + w(u, v)

A) s.d = 3, t.d = 6, y.d = 8, x.d = 7, z.d = 0

B) s.d = 3, t.d = 6, y.d = 8, x.d = 12, z.d = 0

C) s.d = 3, t.d = 9, y.d = 11, x.d = 15, z.d = 14

D) s.d = 3, t.d = 9, y.d = 11, x.d = 12, z.d = 17

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sobre os grafos, seus algoritmos e seus tipos de representações, podemos afirmar:

I - O custo total de execução tanto do BFS quanto do DFS independe do tipo de representação (lista ou matriz) do grafo.
II - O DFS é usado, entre outras coisas, para ordenação topológica e para achar as componentes fortemente conectadas.
III - O custo total do BFS e do DFS é theta(V + E) somente quando o grafo é representado por uma lista de adjacências.
IV - Um grafo pode ser representado ou por uma lista de adjacência ou por uma matriz de adjacência dependendo de qual otimização é necessária.

Dentre as afirmações acima, qual ou quais NÃO são verdadeiras:

A) I, somente

B) I, II e IV, somente

C) III, somente

D) I e III, somente

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade