proyecto de bombeo mecanico12345

PROGRAMACIÓN PARALELA
EN
ALGORITMOS SOBRE
GRAFOS

Contenidos



Introducción y representación de grafos
Algoritmos para grafos “densos”


Árboles de expansión




Algoritmo de Prim

Problemas de caminos mínimos


Con un solo origen




Entre todos los pares de nodos






Algoritmo de Dijkstra
Algoritmo de Dijkstra

Formulación de origen divido
Formulación de origen paralelo
Algoritmo de Floyd

Algoritmos para grafos “esparcidos”

Contenidos



Introducción y representación de grafos
Algoritmos para grafos “densos”


Árboles de expansión




Algoritmo de Prim

Problemas de caminos mínimos


Con un solo origen




Entre todos los pares de nodos






Algoritmo de Dijkstra
Algoritmo deDijkstra

Formulación de origen divido

Formulación de origen paralelo
Algoritmo de Floyd

Algoritmos para grafos “esparcidos”

Introducción y
representación de grafos
(I)





Un grafo G es una tupla G=(V,A), donde V es un conjunto de vértices
y A es un conjunto de aristas o arcos.
Cada arista es un par (v,w) donde v,w pertenecen a V.
TERMINOLOGÍA











Grafo no dirigido: las aristas no están ordenadas.
Grafo dirigido: los pares están ordenados.
Un vértice w es adyacente a otro v si y sólo si (v,w) pertenece a A.
Camino de un vértice w1 a wq: es una secuencia w1, w2 … wq є V, tal que
todas las aristas (w1,w2), …, (wq-1, wq) є A.
Longitud de un camino: nº aristas del camino.
Ciclo: es un camino cuyo primer y último vértice soniguales.
Un grafo es conexo si hay un camino entre cualquier par de vértices.
Un grafo es completo si existe una arista entre cualquier par de vértices.
Un grafo está etiquetado si asociamos a cada arista un peso o un valor.
Un subgrafo de G = (V, A) es un grafo G’ = (V’, A’) tal que V’ es un
subconjunto de V y A’ es un subconjunto de A.

Introducción y
representación de grafos
(II)
REPRESENTACIONES


Matrices de adyacencia.







Las aristas se representan con una matriz M[nodo,nodo]
de booleanos, donde M[v,w]=1 si y sólo si (v,w) є A.
Si el grafo esta etiquetado, la matriz será de elementos
de ese tipo. Tomará un valor nulo si no existe ese arco.
Si el grafo es no dirigido, la matriz es simétrica.
Útil para grafos densos (|A| ≈ |V|2).

Introducción yrepresentación de grafos
(y III)


Listas de adyacencia.








Para cada nodo de V tendremos una lista de aristas que
parten de ese nodo. Estas listas se guardan en un array de
nodos cabecera.
Si el grafo esta etiquetado, se añade un nuevo campo a los
elementos de la lista.
Si el grafo es no dirigido, entonces cada arista (v,w) se
representará dos veces, en la lista de v yen la de w.
Útil para grafos esparcidos (|A| ‹‹ |V|2)

Contenidos



Introducción y representación de grafos
Algoritmos para grafos “densos”


Árboles de expansión




Algoritmo de Prim

Problemas de caminos mínimos


Con un solo origen




Entre todos los pares de nodos






Algoritmo de Dijkstra
Algoritmo de Dijkstra

Formulación de origen divido
Formulación de origen paralelo
Algoritmo de Floyd

Algoritmos para grafos “esparcidos”

Árboles de expansión:
Algoritmo de Prim (I)




Un árbol de expansión de un grafo no
dirigido G=(V,A) y conexo, es un subgrafo
G’=(V,A’) no dirigido, conexo y sin ciclos.
Importante: contiene todos los vértices de G.
El algoritmo de Prim intenta encontrar un
árbol de expansión de ungrafo, cuyas aristas
sumen el peso mínimo.

Árboles de expansión:
Algoritmo de Prim (II)

Árboles de expansión:
Algoritmo de Prim (III)


Método de paralelización.


Supongamos p procesos y n
vertices. El conjunto V se
divide en p subconjuntos
usando el “mapping” de
bloques de 1 dimensión.
Cada subconjunto tiene n/p
vertices consecutivos, y el
trabajo de cada
subconjunto...