Algoritmia - Algoritmos de grafos

   
Vista:

Algoritmos de grafos

Publicado por stratford (3 intervenciones) el 25/03/2013 18:56:15
Hola, agradecería mucho si me pudieseis decir una solución a estos 3 problemas de algoritmos de grafos.

BFS/DFS
Let G = (V, E) be a directed graph and s ∈ V a selected vertex. Develop an O(|V | + |E|) algorithm to check whether there is at most one simple path from s to any other vertex u ∈ V . A path is simple if each node on the path is visited at most once. Use this algorithm to develop a O(|V ||E|) algorithm to check whether there is at most one simple path between any two vertices u and v.

Ordenación Topológica
Let t be a node with out-degree 0 in a dag G = (V, E). Give a O(|V | + |E|) algorithm to determine the number of paths from each vertex u ∈ V − {t} to t.

Let s and t be two vertices in a dag G such that the in-degree of s and the out-degree of t is 0. Use the result of the previous exercise to determine, for each edge (u, v) ∈ E, the number of paths from s to t that run through (u, v) and this in O(|V | + |E|) time.


Componente fuertemente conexos
Let G = (V, E) be a directed graph, develop a O(|V ||E|) algorithm to check whether for any two vertices u, v ∈ V there is either a path from u to v in G or a path from v to u in G.

Muchas gracias!! :D
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder