MO417- QUESTÃO PARA A PROVA ORAL

Número: Enunciado: Assinale a afirmação incorreta sobre o Fluxo máximo:

a) É possível ter uma rede com varias origens e vários sorvedores

b) Num fluxo em rede antiparalelo G=(V,E) se a aresta (u,v) ∈ E então a aresta (v,u) ∉ E

c) Se f é um fluxo máximo então sua rede residual tem pelo menos um caminho aumentante
d) O Algoritmo básico de Ford-Fulkerson tem um tempo de execução total de O(E │f*│),      onde f* é o fluxo máximo

e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL
Número: 
Enunciado: 

Tem-se que conectar um conjunto de computadores entre eles com cabo de rede, só se pode conectar um computador diretamente com outro sem usar nenhum outro dispositivo, no seguinte grafo estão representados os computadores como vértices e as distancias mínimas em metros que um cabo pode recorrer entre cada dois computadores, como arestas. Indique qual seria o custo mínimo en reais para conecta-los, tomando em conta que cada metro de cabo custa 1.5 reais.

a) 84.0
b) 55.0
c) 82.5
d) 61.5
e) NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417- QUESTÃO PARA A PROVA ORAL
Número: 
Enunciado: 

Tomando em conta a seguinte versão do algoritmo de busca em largura:

 

BFS(G,s)

1   for each vertex u∈G.V\{s}

2         u.color = WHITE

3         u.d = ∞

4         u.π = NIL

5   s.color=GRAY

6   s.d=0

7   s.π=NIL

8   Q=∅

9   ENQUEUE(Q, s)

10 while Q̸=∅

11       u = DEQUEUE(Q)

12       for each v ∈ G.Adj[u]

13             if v.color == WHITE

14                   v.color = GRAY

15                   v.d = u.d + 1

16                   v.π = u

17                   ENQUEUE(Q, v)

18       u.color = BLACK

Faça a execução do algoritmo BFS com o grafo representado pela seguinte matriz de adjacência e iniciando a partir do vértice "a":

	a	b	c	d	e	f
a	0	1	0	1	1	0
b	1	0	1	0	0	0
c	0	1	0	1	0	0
d	1	0	1	0	1	1
e	1	0	0	1	0	0
f	0	0	0	1	0	0

Indique quais são os predecessores π de cada vértice.

a) a.π=NIL, b.π=a, c.π=d, d.π=f, e.π=a, f.π=d

b) a.π=NIL, b.π=c, c.π=b, d.π=f, e.π=a, f.π=a

c) a.π=NIL, b.π=a, c.π=d, d.π=a, e.π=a, f.π=a

d) a.π=NIL, b.π=a, c.π=b, d.π=a, e.π=a, f.π=d

e) NDA

Ideia original de: Sheila Katherine Venero Ferro