MO417 - Questão para a prova oral

Número: 

Enunciado: Dado o seguinte grafo dirigido G=(V,E):
 

  

Seja w e W a função de peso e a matriz de pesos do grafo G respetivamente. Suponha que seu vetor de listas de adjacência como seus lista de adjacência de cada vértice estam armazenados em orden alfabética. Assinale alternativa correta sobre os caminhos mais curtos entre todos os pares de vértices do grafo G: 

1.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em Θ( 5³), também o caminho mais longo dos caminhos mais cortos é  d_ea= 16. 

2.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em Θ( 5² lg 5 + 45), também o caminho mais longo dos caminhos mais cortos é  d_ed= 15.

3.)Johnson(G,w) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em O( 5³), também o caminho mais longo dos caminhos mais cortos é  d_ea= 16.
4.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em O( 5² lg 5 + 45), também o caminho mais longo dos caminhos mais cortos é  d_ed= 15.
5.)NDA

Ideia original de: Jhon Anthony Campos Arteaga

MO417 - Questão para a prova oral

Número: 

Enunciado: Dado o seguinte grafo dirigido A=(V,E)  :

  

Y os seguintes algoritmos:

DFS(G)                                                      

1 for each vertex u ∈ G.V                         

2       u.color = WHITE                            

3       u.π = NIL                                        

4 time = 0                                                 

5 for each vertex u ∈ G.V                          

6       if u.color == WHITE                       

7           DFS-VISIT(G,u)                        

                                                                                                                         
DFS-VISIT(G,u)  

1 time = time + 1
2 u.d = time
3 u.color = GRAY 
4 for each v ∈ G.Adj[u] 
5       if v.color = = WHITE 
6             v.π = u  
7             DFS-VISIT(G,v) 
8 u.color = BLACK 
9 time = time + 1 
10 u.f = time
  
Suponha que seu vetor de listas de listas de adjacência como seus lista de adjacência de cada vértice estam armazenados em orden alfabética. Assinale alternativa que contém o valor π correto de cada um dos vertices do grafo A, após da execução do algoritmo DFS(A): 

1.)a.π = f, b.π = a, c.π = d, d.π = b, e.π = NIL, f.π = b, g.π = NIL
2.)a.π = NIL, b.π = a, c.π = d, d.π = b, e.π = NIL, f.π = b, g.π = NIL
3.)a.π = NIL, b.π = a, c.π = b, d.π = d, e.π = NIL, f.π = b, g.π = NIL
4.)a.π = NIL, b.π = a, c.π = d, d.π = b, e.π = NIL, f.π = NIL, g.π =b
5.)NDA

Ideia original de: Jhon Anthony Campos Arteaga