Un grafo G es un par donde
es el conjunto de los vértices (o nodos) y
el de las aristas.
Una arista del grafo es un par de vértices.
Un arco es una arista dirigida.
|V| es el número de vértices.
|A| es el número de aristas.
Un vértice es adjacente a
si
es una arista del grafo.
Un grafo ponderado es un grafo cuyas aristas tienen un peso.
Signatura del TAD de los grafos
creaGrafo :: (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] ->
Grafo v p
dirigido :: (Ix v,Num p) => (Grafo v p) -> Bool
adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
nodos :: (Ix v,Num p) => (Grafo v p) -> [v]
aristas :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
aristaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> pDescripción de la signatura del TAD de grafos
(creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso). Ver un ejemplo en la siguiente transparencia.
(dirigido g) se verifica si g es dirigido.
(nodos g) es la lista de todos los nodos del grafo g.
(aristas g) es la lista de las aristas del grafo g.
(adyacentes g v) es la lista de los vértices adyacentes al nodo v en el grafo g.
(aristaEn g a) se verifica si a es una arista del grafo g.
(peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2 en el grafo g.
Ejemplo de creación de grafos.
creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
(2,4,55),(2,5,32),
(3,4,61),(3,5,44),
(4,5,93)]crea el grafo
12
1 -------- 2
| \78 /|
| \ 32/ |
| \ / |
34| 5 |55
| / \ |
| /44 \ |
| / 93\|
3 -------- 4
61module GrafoConVectorDeAdyacencia
(Orientacion (..),
Grafo,
creaGrafo, -- (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] ->
-- Grafo v p
dirigido, -- (Ix v,Num p) => (Grafo v p) -> Bool
adyacentes, -- (Ix v,Num p) => (Grafo v p) -> v -> [v]
nodos, -- (Ix v,Num p) => (Grafo v p) -> [v]
aristas, -- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
aristaEn, -- (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
peso -- (Ix v,Num p) => v -> v -> (Grafo v p) -> p
) whereimport Data.ArrayOrientacion es D (dirigida) ó ND (no dirigida).data Orientacion = D | ND
deriving (Eq, Show)(Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.data Grafo v p = G Orientacion (Array v [(v,p)])
deriving (Eq, Show)(creaGrafo o cs as) es un grafo (dirigido o no según el valor de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso). Ver un ejemplo a continuación.creaGrafo :: (Ix v, Num p) =>
Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
creaGrafo o cs vs =
G o (accumArray
(\xs x -> xs++[x]) [] cs
((if o == D then []
else [(x2,(x1,p))|(x1,x2,p) <- vs, x1 /= x2]) ++
[(x1,(x2,p)) | (x1,x2,p) <- vs]))ejGrafoND es el grafo 12
1 -------- 2
| \78 /|
| \ 32/ |
| \ / |
34| 5 |55
| / \ |
| /44 \ |
| / 93\|
3 -------- 4
61ghci> ejGrafoND
G ND array (1,5) [(1,[(2,12),(3,34),(5,78)]),
(2,[(1,12),(4,55),(5,32)]),
(3,[(1,34),(4,61),(5,44)]),
(4,[(2,55),(3,61),(5,93)]),
(5,[(1,78),(2,32),(3,44),(4,93)])])ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
(2,4,55),(2,5,32),
(3,4,61),(3,5,44),
(4,5,93)]ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas de menor a mayor. Por ejemplo,ghci> ejGrafoD
G D array (1,5) [(1,[(2,12),(3,34),(5,78)]),
(2,[(4,55),(5,32)]),
(3,[(4,61),(5,44)]),
(4,[(5,93)]),
(5,[])])ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
(2,4,55),(2,5,32),
(3,4,61),(3,5,44),
(4,5,93)](dirigido g) se verifica si g es dirigido. Por ejemplo,dirigido ejGrafoD == True
dirigido ejGrafoND == Falsedirigido :: (Ix v,Num p) => (Grafo v p) -> Bool
dirigido (G o _) = o == D(adyacentes g v) es la lista de los vértices adyacentes al nodo v en el grafo g. Por ejemplo,adyacentes ejGrafoND 4 == [2,3,5]
adyacentes ejGrafoD 4 == [5]adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
adyacentes (G _ g) v = map fst (g!v)(nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,nodos ejGrafoND == [1,2,3,4,5]
nodos ejGrafoD == [1,2,3,4,5]nodos :: (Ix v,Num p) => (Grafo v p) -> [v]
nodos (G _ g) = indices g(peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2 en el grafo g. Por ejemplo,peso 1 5 ejGrafoND == 78
peso 1 5 ejGrafoD == 78peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p
peso x y (G _ g) = head [c | (a,c) <- g!x , a == y](aristaEn g a) se verifica si a es una arista del grafo g. Por ejemplo,aristaEn ejGrafoND (5,1) == True
aristaEn ejGrafoND (4,1) == False
aristaEn ejGrafoD (5,1) == False
aristaEn ejGrafoD (1,5) == TruearistaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
aristaEn g (x,y) = y `elem` adyacentes g x(aristas g) es la lista de las aristas del grafo g. Por ejemplo,ghci> aristas ejGrafoND
[(1,2,12),(1,3,34),(1,5,78),(2,1,12),(2,4,55),(2,5,32),
(3,1,34),(3,4,61),(3,5,44),(4,2,55),(4,3,61),(4,5,93),
(5,1,78),(5,2,32),(5,3,44),(5,4,93)]
ghci> aristas ejGrafoD
[(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),
(3,5,44),(4,5,93)] aristas :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
aristas (G o g) =
[(v1,v2,w) | v1 <- nodos (G o g) , (v2,w) <- g!v1] module GrafoConMatrizDeAdyacencia
(Orientacion (..),
Grafo,
creaGrafo, -- (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] ->
-- Grafo v p
dirigido, -- (Ix v,Num p) => (Grafo v p) -> Bool
adyacentes, -- (Ix v,Num p) => (Grafo v p) -> v -> [v]
nodos, -- (Ix v,Num p) => (Grafo v p) -> [v]
aristas, -- (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
aristaEn, -- (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
peso -- (Ix v,Num p) => v -> v -> (Grafo v p) -> p
) whereimport Data.ArrayOrientacion es D (dirigida) ó ND (no dirigida).data Orientacion = D | ND
deriving (Eq, Show)(Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.data Grafo v p = G Orientacion (Array (v,v) (Maybe p))
deriving (Eq, Show)(creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso). Ver un ejemplo a continuación.creaGrafo :: (Ix v, Num p) => Bool -> (v,v) -> [(v,v,p)]
-> Grafo v p
creaGrafo o cs@(l,u) as
= G o (matrizVacia //
([((x1,x2),Just w) | (x1,x2,w) <- as] ++
if o == D then []
else [((x2,x1),Just w) | (x1,x2,w) <- as, x1 /= x2]))
where
matrizVacia = array ((l,l),(u,u))
[((x1,x2),Nothing) | x1 <- range cs,
x2 <- range cs]ejGrafoND es el grafo 12
1 -------- 2
| \78 /|
| \ 32/ |
| \ / |
34| 5 |55
| / \ |
| /44 \ |
| / 93\|
3 -------- 4
61ghci> ejGrafoND
G ND array ((1,1),(5,5))
[((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),
((1,4),Nothing),((1,5),Just 78),((2,1),Just 12),
((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),
((2,5),Just 32),((3,1),Just 34),((3,2),Nothing),
((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),
((4,1),Nothing),((4,2),Just 55),((4,3),Just 61),
((4,4),Nothing),((4,5),Just 93),((5,1),Just 78),
((5,2),Just 32),((5,3),Just 44),((5,4),Just 93),
((5,5),Nothing)]ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
(2,4,55),(2,5,32),
(3,4,61),(3,5,44),
(4,5,93)]ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas de menor a mayor. Por ejemplo,ghci> ejGrafoD
G D (array ((1,1),(5,5))
[((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),
((1,4),Nothing),((1,5),Just 78),((2,1),Nothing),
((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),
((2,5),Just 32),((3,1),Nothing),((3,2),Nothing),
((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),
((4,1),Nothing),((4,2),Nothing),((4,3),Nothing),
((4,4),Nothing),((4,5),Just 93),((5,1),Nothing),
((5,2),Nothing),((5,3),Nothing),((5,4),Nothing),
((5,5),Nothing)])ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
(2,4,55),(2,5,32),
(3,4,61),(3,5,44),
(4,5,93)](dirigido g) se verifica si g es dirigido. Por ejemplo,dirigido ejGrafoD == True
dirigido ejGrafoND == Falsedirigido :: (Ix v,Num p) => (Grafo v p) -> Bool
dirigido (G o _) = o == D(adyacentes g v) es la lista de los vértices adyacentes al nodo v en el grafo g. Por ejemplo,adyacentes ejGrafoND 4 == [2,3,5]
adyacentes ejGrafoD 4 == [5]adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
adyacentes (G o g) v =
[v' | v' <- nodos (G o g), (g!(v,v')) /= Nothing](nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,nodos ejGrafoND == [1,2,3,4,5]
nodos ejGrafoD == [1,2,3,4,5]nodos :: (Ix v,Num p) => (Grafo v p) -> [v]
nodos (G _ g) = range (l,u)
where ((l,_),(u,_)) = bounds g(peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2 en el grafo g. Por ejemplo,peso 1 5 ejGrafoND == 78
peso 1 5 ejGrafoD == 78peso :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p
peso x y (G _ g) = w where (Just w) = g!(x,y)(aristaEn g a) se verifica si a es una arista del grafo g. Por ejemplo,aristaEn ejGrafoND (5,1) == True
aristaEn ejGrafoND (4,1) == FalsearistaEn :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
aristaEn (G _o g) (x,y)= (g!(x,y)) /= Nothing(aristas g) es la lista de las aristas del grafo g. Por ejemplo,ghci> aristas ejGrafoD
[(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),
(3,5,44),(4,5,93)]
ghci> aristas ejGrafoND
[(1,2,12),(1,3,34),(1,5,78),(2,1,12),(2,4,55),(2,5,32),
(3,1,34),(3,4,61),(3,5,44),(4,2,55),(4,3,61),(4,5,93),
(5,1,78),(5,2,32),(5,3,44),(5,4,93)]aristas :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
aristas g@(G o e) = [(v1,v2,extrae(e!(v1,v2)))
| v1 <- nodos g,
v2 <- nodos g,
aristaEn g (v1,v2)]
where extrae (Just w) = w-- Nota: Elegir una implementación de los grafos.
import GrafoConVectorDeAdyacencia
-- import GrafoConMatrizDeAdyacenciag+---> 2 <---+
| |
| |
1 --> 3 --> 6 --> 5
| |
| |
+---> 4 <---------+g = creaGrafo D (1,6)
[(1,2,0),(1,3,0),(1,4,0),(3,6,0),
(5,4,0),(6,2,0),(6,5,0)]Procedimiento elemental de recorrido en profundidad
(recorridoEnProfundidad i g) es el recorrido en profundidad del grafo g desde el vértice i. Por ejemplo,recorridoEnProfundidad 1 g == [1,2,3,6,5,4]recorridoEnProfundidad i g = rp [i] []
where
rp [] vis = vis
rp (c:cs) vis
| c `elem` vis = rp cs vis
| otherwise = rp ((adyacentes g c)++cs)
(vis++[c])(recorridoEnProfundidad 1 g)recorridoEnProfundidad 1 g
= rp [1] []
= rp [2,3,4] [1]
= rp [3,4] [1,2]
= rp [6,4] [1,2,3]
= rp [2,5,4] [1,2,3,6]
= rp [5,4] [1,2,3,6]
= rp [4,4] [1,2,3,6,5]
= rp [4] [1,2,3,6,5,4]
= rp [] [1,2,3,6,5,4]
= [1,2,3,6,5,4]Recorrido en profundidad con acumuladores
(recorridoEnProfundidad' i g) es el recorrido en profundidad del grafo, usando la lista de los visitados como acumulador. Por ejemplo,recorridoEnProfundidad' 1 g == [1,2,3,6,5,4]recorridoEnProfundidad' i g = reverse (rp [i] [])
where
rp [] vis = vis
rp (c:cs) vis
| c `elem` vis = rp cs vis
| otherwise = rp ((adyacentes g c)++cs)
(c:vis)(recorridoEnProfundidad' 1 g)recorridoEnProfundidad' 1 g
= reverse (rp [1] [])
= reverse (rp [2,3,4] [1])
= reverse (rp [3,4] [2,1])
= reverse (rp [6,4] [3,2,1])
= reverse (rp [2,5,4] [6,3,2,1])
= reverse (rp [5,4] [6,3,2,1])
= reverse (rp [4,4] [5,6,3,2,1])
= reverse (rp [4] [4,5,6,3,2,1])
= reverse (rp [] [4,5,6,3,2,1])
= reverse [4,5,6,3,2,1]
= [1,2,3,6,5,4]-- Nota: Elegir una implementación de los grafos.
import GrafoConVectorDeAdyacencia
-- import GrafoConMatrizDeAdyacenciaProcedimiento elemental de recorrido en anchura
(recorridoEnAnchura i g) es el recorrido en anchura del grafo g desde el vértice i. Por ejemplo,recorridoEnAnchura 1 g == [1,4,3,2,6,5]recorridoEnAnchura i g = reverse (ra [i] [])
where
ra [] vis = vis
ra (c:cs) vis
| c `elem` vis = ra cs vis
| otherwise = ra (cs ++ adyacentes g c)
(c:vis)(recorridoEnAnchura 1 g)RecorridoEnAnchura 1 g
= ra [1] []
= ra [2,3,4] [1]
= ra [3,4] [2,1]
= ra [4,6] [3,2,1]
= ra [6] [4,3,2,1]
= ra [2,5] [6,4,3,2,1]
= ra [5] [6,4,3,2,1]
= ra [4] [5,6,4,3,2,1]
= ra [] [5,6,4,3,2,1]
= [1,2,3,4,6,5]Sea G = (V,A) un grafo conexo no orientado en el que cada arista tiene un peso no negativo. Un árbol de expansión mínimo de G es un subgrafo G' = (V,A') que conecta todos los vértices de G y tal que la suma de sus pesos es mínima.
Aplicación: Si los vértices representan ciudades y el coste de una arista {a,b} es el construir una carretera de a a b, entonces un árbol de expansión mínimo representa el modo de enlazar todas las ciudades mediante una red de carreteras de coste mínimo.
Teorema: Sea G = (V,A) un grafo conexo no orientado cuyas aristas tienen un peso asociado. Sea B un subjconjunto propio del conjunto de vértices V y T un conjunto prometedor de aristas tal que ninguna arista de T toca a B. Sea e una arista de peso mínimo de entre todas las que tocan a B. Entonces, (T ∪ {e}) es prometedor.
Para los ejemplos se considera el siguiente grafo:
1 2
1 ----- 2 ----- 3
| /| /|
| / | / |
| / | / |
4| /6 |4 /5 |6
| / | / |
| / | / |
|/ |/ |
4 ----- 5 ----- 6
\ 3 | 8 /
\ | /
\ | /
4\ |7 /3
\ | /
\ | /
\|/
7Etapa Arista Componentes conexas
0 {1} {2} {3} {4} {5} {6} {7}
1 {1,2} {1,2} {3} {4} {5} {6} {7}
2 {2,3} {1,2,3} {4} {5} {6} {7}
3 {4,5} {1,2,3} {4,5} {6} {7}
4 {6,7} {1,2,3} {4,5} {6,7}
5 {1,4} {1,2,3,4,5} {6,7}
6 {2,5} arista rechazada
7 {4,7} {1,2,3,4,5,6,7}{1,2}, {2,3}, {4,5}, {6,7}, {1,4} y {4,7}. -- Nota: Seleccionar una implementación del TAD grafo.
import GrafoConVectorDeAdyacencia
-- import GrafoConMatrizDeAdyacencia
-- Nota: Seleccionar una implementación del TAD tabla.
-- import TablaConFunciones
import TablaConListasDeAsociacion
-- import TablaConMatrices
import Data.List
import Data.Ixg1 :: Grafo Int Int
g1 = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
(2,4,55),(2,5,32),
(3,4,61),(3,5,44),
(4,5,93)]
g2 :: Grafo Int Int
g2 = creaGrafo D (1,5) [(1,2,13),(1,3,11),(1,5,78),
(2,4,12),(2,5,32),
(3,4,14),(3,5,44),
(4,5,93)](kruskal g) es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Kruskal. Por ejemplo,kruskal g1 == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
kruskal g2 == [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
kruskal g = kruskal' cola -- Cola de prioridad
(tabla [(x,x) | x <- nodos g]) -- Tabla de raices
[] -- Árbol de expansión
((length (nodos g)) - 1) -- Aristas por
-- colocar
where cola = sort [(p,x,y) | (x,y,p) <- aristas g]
kruskal' ((p,x,y):as) t ae n
| n==0 = ae
| actualizado = kruskal' as t' ((p,x,y):ae) (n-1)
| otherwise = kruskal' as t ae n
where (actualizado,t') = buscaActualiza (x,y) t(raiz t n) es la raíz de n en la tabla t. Por ejemplo,> raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5
1
> raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2
6raiz:: Eq n => Tabla n n -> n -> n
raiz t x | v == x = v
| otherwise = raiz t v
where v = valor t x(buscaActualiza a t) es el par formado por False y la tabla t, si los dos vértices de la arista a tienen la misma raíz en t y el par formado por True y la tabla obtenida añadiéndole a t la arista formada por el vértice de a de mayor raíz y la raíz del vértice de a de menor raíz. Por ejemplo,ghci> let t = crea [(1,1),(2,2),(3,1),(4,1)]
ghci> buscaActualiza (2,3) t
(True,Tbl [(1,1),(2,1),(3,1),(4,1)])
ghci> buscaActualiza (3,4) t
(False,Tbl [(1,1),(2,2),(3,1),(4,1)])buscaActualiza :: (Eq n, Ord n) => (n,n) -> Tabla n n
-> (Bool,Tabla n n)
buscaActualiza (x,y) t
| x' == y' = (False, t)
| y' < x' = (True, modifica (x,y') t)
| otherwise = (True, modifica (y,x') t)
where x' = raiz t x
y' = raiz t y(prim g) es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim. Por ejemplo,prim g1 == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]
prim g2 == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]
prim g = prim' [n] -- Nodos colocados
ns -- Nodos por colocar
[] -- Árbol de expansión
(aristas g) -- Aristas del grafo
where (n:ns) = nodos g
prim' t [] ae as = ae
prim' t r ae as = prim' (v':t) (delete v' r) (e:ae) as
where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,
elem u t,
elem v r] 