Representaciones de grafos

PorJosé A. Alonso 24-mayo-201725-abril-2021

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

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|

|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])]

1	[(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

1 2	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]]

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])]

1 2	λ> 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])]

λ> 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

[schedule expon=’2017-05-31′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 31 de mayo.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2017-05-31′ at=»06:00″]

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

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

[/schedule]

6 Comentarios

import Data.Matrix

matrizAlista :: Matrix Int -> [(Int,[Int])]
matrizAlista m = [(i, [ j | j <- [1..c], (m ! (i,j)) == 1]) | i <- [1..r]]
               where
                c = ncols m
                r = nrows m

listaAmatriz :: [(Int,[Int])] -> Matrix Int
listaAmatriz xs  = (foldr (setElem 1) (zero r r) . concatMap (\(y,ys) -> [(y,x) | x <- ys])) xs
              where
               r = length xs

import Data.Matrix

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

matrizAlista m = [(i, [ j | j <- [1..c], (m ! (i,j)) == 1]) | i <- [1..r]]

where

c = ncols m

r = nrows m

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

listaAmatriz xs = (foldr (setElem 1) (zero r r) . concatMap (\(y,ys) -> [(y,x) | x <- ys])) xs

where

r = length xs

Responder

listaAmatriz2 :: [(Int,[Int])] -> Matrix Int
listaAmatriz2 xs = matrix r r (\(i,j) -> if j `elem` (s !! (i-1)) then 1 else 0) 
                 where
                  r = length xs
                  s = map snd xs

listaAmatriz2 :: [(Int,[Int])] -> Matrix Int

listaAmatriz2 xs = matrix r r (\(i,j) -> if j `elem` (s !! (i-1)) then 1 else 0)

where

r = length xs

s = map snd xs

Responder

import Data.Matrix
import Data.List

matrizAlista :: Matrix Int -> [(Int,[Int])]
matrizAlista p = [(i,t i) | i <- [1..f]]
     where f = nrows p
           t a = [ x | x <- [1..f], p!(a,x) == 1]

listaAmatriz ::  [(Int,[Int])] -> Matrix Int
listaAmatriz xs = aux (concatMap (\(a,b) -> [(a,x) | x <- b]) xs) (zero a a)
      where a = fst $ last xs
            aux [] p = p
            aux ((x,y):xs) p = aux xs (setElem 1 (x,y) p)

import Data.Matrix

import Data.List

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

matrizAlista p = [(i,t i) | i <- [1..f]]

where f = nrows p

t a = [ x | x <- [1..f], p!(a,x) == 1]

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

listaAmatriz xs = aux (concatMap (\(a,b) -> [(a,x) | x <- b]) xs) (zero a a)

where a = fst $ last xs

aux [] p = p

aux ((x,y):xs) p = aux xs (setElem 1 (x,y) p)

Responder

import qualified Data.Vector as V
import Data.Matrix as M
import Data.List

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 m = aux 1 nf m
  where
    nf = nrows m
    aux k nf m
      | k > nf   = []
      | otherwise =
        (k,(fun m)) : aux (k+1) nf m
        where fun = V.toList
                  . V.map (+1)
                  . V.elemIndices 1
                  . getRow k

listaAmatriz :: [(Int,[Int])] -> Matrix Int
listaAmatriz xs = foldl1 (<->) (map f (sort xs))
  where
    f (_,zs) = rowVector $ v V.// (map (\x -> (x-1,1)) zs)
      where nc = fst $ last xs
            v  = V.replicate nc 0

import qualified Data.Vector as V

import Data.Matrix as M

import Data.List

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 m = aux 1 nf m

where

nf = nrows m

aux k nf m

| k > nf = []

| otherwise =

(k,(fun m)) : aux (k+1) nf m

where fun = V.toList

. V.map (+1)

. V.elemIndices 1

. getRow k

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

listaAmatriz xs = foldl1 (<->) (map f (sort xs))

where

f (_,zs) = rowVector $ v V.// (map (\x -> (x-1,1)) zs)

where nc = fst $ last xs

v = V.replicate nc 0

Responder

import Data.Matrix

matrizAlista :: Matrix Int -> [(Int,[Int])]
matrizAlista m = [(i,[x | x <- [1..ncols m], m!(i,x) ==1]) | i <-[1..ncols m]]

listaAmatriz :: [(Int,[Int])] -> Matrix Int
listaAmatriz xs = fromLists $ map (\a -> aux n a) xs
             where n = [1..length xs]
                   aux [] _ = []
                   aux (y:ys) (a,b) | y `elem` b = 1 : aux ys (a,b)
                                    | otherwise  = 0 : aux ys (a,b)

import Data.Matrix

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

matrizAlista m = [(i,[x | x <- [1..ncols m], m!(i,x) ==1]) | i <-[1..ncols m]]

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

listaAmatriz xs = fromLists $ map (\a -> aux n a) xs

where n = [1..length xs]

aux [] _ = []

aux (y:ys) (a,b) | y `elem` b = 1 : aux ys (a,b)

| otherwise = 0 : aux ys (a,b)

Responder

matrizAlista :: Matrix Int -> [(Int,[Int])]
matrizAlista m = [ (a,aux m a) | a <- [1..ncols m]]
      where aux m a = [ x | x <- [1..nrows m], m ! (a,x) == 1]

listaAmatriz :: [(Int,[Int])] -> Matrix Int
listaAmatriz ps = matrix l l (\(i,j) -> f(i,j))
    where l = length ps
          f(i,j) | j `elem` (aux i ps) = 1
                 | otherwise = 0
          aux a ((x,xs):ys) | a == x = xs
                            | otherwise = aux a ys

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

matrizAlista m = [ (a,aux m a) | a <- [1..ncols m]]

where aux m a = [ x | x <- [1..nrows m], m ! (a,x) == 1]

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

listaAmatriz ps = matrix l l (\(i,j) -> f(i,j))

where l = length ps

f(i,j) | j `elem` (aux i ps) = 1

| otherwise = 0

aux a ((x,xs):ys) | a == x = xs

| otherwise = aux a ys

Responder

Representaciones de grafos

Soluciones

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico