Ir al contenido principal

Representaciones de grafos

Los grafos no dirigidos puede representarse mediante matrices de adyacencia y también mediante listas de adyacencia. Por ejemplo, el grafo

1 ----- 2
| \     |
|  3    |
| /     |
4 ----- 5

se puede representar por la matriz de adyacencia

|0 1 1 1 0|
|1 0 0 0 1|
|1 0 0 1 0|
|1 0 1 0 1|
|0 1 0 1 0|

donde el elemento (i,j) es 1 si hay una arista entre los vértices i y j y es 0 si no la hay. También se puede representar por la lista de adyacencia

[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

donde las primeras componentes son los vértices y las segundas la lista de los vértices conectados.

Definir las funciones

matrizAlista :: Matrix Int -> [(Int,[Int])]
listaAmatriz :: [(Int,[Int])] -> Matrix Int

tales que

  • (matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por
ejMatriz :: Matrix Int
ejMatriz = fromLists [[0,1,1,1,0],
[1,0,0,0,1],
[1,0,0,1,0],
[1,0,1,0,1],
[0,1,0,1,0]]

se tiene que

λ> matrizAlista ejMatriz
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
  • (listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo,
λ> listaAmatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
( 0 1 1 1 0 )
( 1 0 0 0 1 )
( 1 0 0 1 0 )
( 1 0 1 0 1 )
( 0 1 0 1 0 )
λ> matrizAlista it
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

Soluciones

import Data.List (sort)
import Data.Matrix

ejMatriz :: Matrix Int
ejMatriz = fromLists [[0,1,1,1,0],
                      [1,0,0,0,1],
                      [1,0,0,1,0],
                      [1,0,1,0,1],
                      [0,1,0,1,0]]

matrizAlista :: Matrix Int -> [(Int,[Int])]
matrizAlista a =
  [(i,[j | j <- [1..n], a!(i,j) == 1]) | i <- [1..n]]
  where n = nrows a

listaAmatriz :: [(Int,[Int])] -> Matrix Int
listaAmatriz ps = fromLists [fila n xs | (_,xs) <- sort ps]
  where n = length ps
        fila n xs = [f i | i <- [1..n]]
          where f i | i `elem` xs = 1
                    | otherwise   = 0