{"id":1384,"date":"2011-05-16T16:34:26","date_gmt":"2011-05-16T16:34:26","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1384"},"modified":"2011-05-22T04:47:45","modified_gmt":"2011-05-22T04:47:45","slug":"i1m2010-ejercicios-sobre-el-tad-de-los-grafos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-ejercicios-sobre-el-tad-de-los-grafos-en-haskell\/","title":{"rendered":"I1M2010: Ejercicios sobre el TAD de los grafos en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios sobre el tipos abstracto de datos de los grafos en Haskell de la <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2010\/index.php5\/Relaci%C3%B3n_30\">30\u00aa relaci\u00f3n<\/a>.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Introducci\u00f3n                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El objetivo de esta relaci\u00f3n de ejercicios es definir funciones sobre \r\n-- el TAD de los grafos, utilizando las implementaciones estudiadas\r\n-- en el tema 22 que se pueden descargar desde \r\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/codigos.zip\r\n--\r\n-- Las transparencias del tema 22 se encuentran en\r\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/temas\/tema-22.pdf\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\n{-# LANGUAGE FlexibleInstances, TypeSynonymInstances #-}\r\n\r\nimport Data.Array\r\nimport Data.List (nub)\r\nimport Test.QuickCheck\r\n\r\n-- Hay que seleccionar una implementaci\u00f3n del TAD de los grafos\r\nimport GrafoConVectorDeAdyacencia \r\n-- import GrafoConMatrizDeAdyacencia \r\n-- import GrafoConListas\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejemplos                                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Para los ejemplos se usar\u00e1n los siguientes grafos.\r\ng1, g2, g3, g4, g5, g6, g7, g8 :: Grafo Int Int\r\ng1 = creaGrafo False (1,5) [(1,2,12),(1,3,34),(1,5,78),\r\n                            (2,4,55),(2,5,32),\r\n                            (3,4,61),(3,5,44),\r\n                            (4,5,93)]\r\ng2 = creaGrafo True (1,5) [(1,2,12),(1,3,34),(1,5,78),\r\n                           (2,4,55),(2,5,32),\r\n                           (4,3,61),(4,5,93)]\r\ng3 = creaGrafo True (1,3) [(1,2,0),(2,2,0),(3,1,0),(3,2,0)]\r\ng4 = creaGrafo True (1,4) [(1,2,3),(2,1,5)]\r\ng5 = creaGrafo True (1,1) [(1,1,0)]\r\ng6 = creaGrafo True (1,4) [(1,3,0),(3,1,0),(3,3,0),(4,2,0)]\r\ng7 = creaGrafo False (1,4) [(1,3,0)]\r\ng8 = creaGrafo True (1,5) [(1,1,0),(1,2,0),(1,3,0),(2,4,0),(3,1,0),\r\n                           (4,1,0),(4,2,0),(4,4,0),(4,5,0)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. El grafo completo de orden n, K(n), es un grafo no\r\n-- dirigido cuyos conjunto de v\u00e9rtices es {1,..n} y tiene una arista\r\n-- entre par de v\u00e9rtices distintos. Definir la funci\u00f3n,\r\n--    completo :: Int -> Grafo Int Int\r\n-- tal que (completo n) es el grafo completo de orden n. Por ejemplo,\r\n--    ghci> completo 4\r\n--    array (1,4) [(1,[(2,0),(3,0),(4,0)]),\r\n--                 (2,[(1,0),(3,0),(4,0)]),\r\n--                 (3,[(1,0),(2,0),(4,0)]),\r\n--                 (4,[(1,0),(2,0),(3,0)])]\r\n-- ---------------------------------------------------------------------\r\n\r\ncompleto :: Int -> Grafo Int Int\r\ncompleto n = creaGrafo False (1,n) xs\r\n    where xs = [(x,y,0) | x <- [1..n], y <- [1..n], x < y]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. El ciclo de orden n, C(n), es un grafo no dirigido\r\n-- cuyo conjunto de v\u00e9rtices es {1,...,n} y las aristas son\r\n--    (1,2), (2,3), ..., (n-1,n), (n,1)\r\n-- Definir la funci\u00f3n\r\n--    grafoCiclo :: Int -> Grafo Int Int\r\n-- tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,\r\n--    ghci> grafoCiclo 3\r\n--    array (1,3) [(1,[(3,0),(2,0)]),(2,[(1,0),(3,0)]),(3,[(2,0),(1,0)])]\r\n-- ---------------------------------------------------------------------\r\n\r\ngrafoCiclo :: Int -> Grafo Int Int\r\ngrafoCiclo n = creaGrafo False (1,n) xs\r\n    where xs = [(x,x+1,0) | x <- [1..n-1]] ++ [(n,1,0)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    nVertices :: (Ix v,Num p) => Grafo v p ->  Int\r\n-- tal que (nVertices g) es el n\u00famero de v\u00e9rtices del grafo g. Por\r\n-- ejemplo, \r\n--    nVertices (completo 4)  ==  4\r\n--    nVertices (completo 5)  ==  5\r\n-- ---------------------------------------------------------------------\r\n\r\nnVertices :: (Ix v,Num p) => Grafo v p ->  Int\r\nnVertices = length . nodos\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la funci\u00f3n\r\n--    dirigido :: (Ix v,Num p) => Grafo v p ->  Bool\r\n-- tal que (dirigido g) se verifica si el grafo g es dirigido; es decir,\r\n-- existe una arista (x,y) en g tal que que (y,x) no es una arista de\r\n-- g. Por ejemplo,  \r\n--    dirigido g1            ==  False\r\n--    dirigido g2            ==  True\r\n--    dirigido (completo 4)  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\ndirigido :: (Ix v,Num p) => Grafo v p ->  Bool\r\ndirigido g = or [not (aristaEn g (y,x)) | \r\n                 x <- vs, y <- vs, aristaEn g (x,y)]\r\n    where vs = nodos g\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Definir la funci\u00f3n\r\n--    noDirigido :: (Ix v,Num p) => Grafo v p ->  Bool\r\n-- tal que (noDirigido g) se verifica si el grafo g es no dirigido. Por\r\n-- ejemplo, \r\n--    noDirigido g1            ==  True\r\n--    noDirigido g2            ==  False\r\n--    noDirigido (completo 4)  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nnoDirigido :: (Ix v,Num p) => Grafo v p ->  Bool\r\nnoDirigido = not . dirigido\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. La funci\u00f3n aristasND definida en el TAD de los grafos\r\n-- se aplica a grafos no dirigidos sin lazos. Definir la funci\u00f3n\r\n--    aristasND' :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\n-- tal que (aristasND' g) es la lista de las aristas del grafo no\r\n-- dirigido g que puede tener lazos. Por ejemplo,\r\n--    g5             ==  array (1,1) [(1,[(1,0)])]\r\n--    aristasND g5   ==  []\r\n--    aristasND' g5  ==  [(1,1,0)]\r\n-- ---------------------------------------------------------------------\r\n\r\naristasND' :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]\r\naristasND' g = \r\n    [(v1,v2,peso v1 v2 g) | v1 <- nodos g, v2 <- contiguos g v1, v1 <= v2]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    aristas :: (Ix v,Num p) => Grafo v p ->  [(v,v)]\r\n-- tal que (aristas g) es el conjunto de las aristas del grafo g. Por\r\n-- ejemplo, \r\n--    ghci> aristas g1\r\n--    [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]\r\n--    ghci> aristas g2\r\n--    [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)]\r\n--    ghci> aristas (completo 4)\r\n--    [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]\r\n--    ghci> aristas (creaGrafo True (1,3) [(2,1,0),(3,3,0)])\r\n--    [(1,2),(3,3)]\r\n--    ghci> aristas (creaGrafo True (1,3) [(2,1,0),(3,3,0),(1,2,0)])\r\n--    [(1,2),(3,3)]\r\n-- ---------------------------------------------------------------------\r\n\r\naristas :: (Ix v,Num p) => Grafo v p -> [(v,v,p)]\r\naristas g | dirigido g = aristasD g\r\n          | otherwise  = aristasND' g\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n--    nAristas :: (Ix v,Num p) => Grafo v p ->  Int\r\n-- tal que (nAristas g) es el n\u00famero de aristas del grafo g. Por\r\n-- ejemplo, \r\n--    nAristas g1            ==  8\r\n--    nAristas g2            ==  7\r\n--    nAristas (completo 4)  ==  6\r\n--    nAristas (completo 5)  ==  10\r\n-- ---------------------------------------------------------------------\r\n\r\nnAristas :: (Ix v,Num p) => Grafo v p ->  Int\r\nnAristas = length . aristas\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    prop_nAristasCompleto :: Int -> Bool\r\n-- tal que (prop_nAristasCompleto n) se verifica si el n\u00famero de aristas\r\n-- del grafo completo de orden n es n*(n-1)\/2 y, usando la funci\u00f3n,\r\n-- comprobar que la propiedad se cumple para n de 1 a 20.\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_nAristasCompleto :: Int -> Bool\r\nprop_nAristasCompleto n =\r\n    nAristas (completo n) == n*(n-1) `div` 2\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> and [prop_nAristasCompleto n | n <- [1..20]]\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n--    lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)]\r\n-- tal que (lazos g) es el conjunto de los lazos (es decir, aristas\r\n-- cuyos extremos son iguales) del grafo g. Por ejemplo, \r\n--    ghci> lazos g3\r\n--    [(2,2)]\r\n--    ghci> lazos g2\r\n--    []\r\n-- ---------------------------------------------------------------------\r\n\r\nlazos :: (Ix v,Num p) => Grafo v p -> [(v,v)]\r\nlazos g = [(x,x) | x <- nodos g, aristaEn g (x,x)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    nLazos :: (Ix v,Num p) => Grafo v p ->  Int\r\n-- tal que (nLazos g) es el n\u00famero de lazos del grafo g. Por\r\n-- ejemplo, \r\n--    nLazos g3  ==  1\r\n--    nLazos g2  ==  0\r\n-- ---------------------------------------------------------------------\r\n\r\nnLazos :: (Ix v,Num p) => Grafo v p ->  Int\r\nnLazos = length . lazos\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. En un un grafo g, los incidentes de un v\u00e9rtice v es el\r\n-- conjuntos de v\u00e9rtices x de g para los que hay un arco (o una arista)\r\n-- de x a v; es decir, que v es adyacente a x. Definir la funci\u00f3n\r\n--    incidentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]\r\n-- tal que (incidentes g v) es la lista de los v\u00e9rtices incidentes en el\r\n-- v\u00e9rtice v. Por ejemplo,\r\n--    incidentes g2 5  ==  [1,2,4]\r\n--    adyacentes g2 5  ==  []\r\n--    incidentes g1 5  ==  [1,2,3,4]\r\n--    adyacentes g1 5  ==  [1,2,3,4]\r\n-- --------------------------------------------------------------------- \r\n\r\nincidentes :: (Ix v,Num p) => Grafo v p -> v -> [v]\r\nincidentes g v = [x | x <- nodos g, v `elem` adyacentes g x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. En un un grafo g, los contiguos de un v\u00e9rtice v es el\r\n-- conjuntos de v\u00e9rtices x de g tales que x es adyacente o incidente con\r\n-- v. Definir la funci\u00f3n\r\n--    contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v]\r\n-- tal que (contiguos g v) es el conjunto de los v\u00e9rtices de g contiguos\r\n-- con el v\u00e9rtice v. Por ejemplo,\r\n--    contiguos g2 5  ==  [1,2,4]\r\n--    contiguos g1 5  ==  [1,2,3,4]\r\n-- ---------------------------------------------------------------------\r\n\r\ncontiguos :: (Ix v,Num p) => Grafo v p -> v -> [v]\r\ncontiguos g v = nub (adyacentes g v ++ incidentes g v)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. El grado positivo de un v\u00e9rtice v de un grafo dirigido\r\n-- g, es el n\u00famero de v\u00e9rtices de g adyacentes con v. Definir la funci\u00f3n  \r\n--    gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int\r\n-- tal que (gradoPos g v) es el grado positivo del v\u00e9rtice v en el grafo\r\n-- g. Por ejemplo,\r\n--    gradoPos g1 5  ==  4\r\n--    gradoPos g2 5  ==  0\r\n--    gradoPos g2 1  ==  3\r\n-- ---------------------------------------------------------------------\r\n\r\ngradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int\r\ngradoPos g v = length (adyacentes g v)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. El grado negativo de un v\u00e9rtice v de un grafo dirigido\r\n-- g, es el n\u00famero de v\u00e9rtices de g incidentes con v. Definir la funci\u00f3n  \r\n--    gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int\r\n-- tal que (gradoNeg g v) es el grado negativo del v\u00e9rtice v en el grafo\r\n-- g. Por ejemplo,\r\n--    gradoNeg g1 5  ==  4\r\n--    gradoNeg g2 5  ==  3\r\n--    gradoNeg g2 1  ==  0\r\n-- ---------------------------------------------------------------------\r\n\r\ngradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int\r\ngradoNeg g v = length (incidentes g v)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. El grado de un v\u00e9rtice v de un grafo g, es el n\u00famero de\r\n-- aristas de g que contiene a v (los lazos se cuentan 2 veces). Definir\r\n-- la funci\u00f3n    \r\n--    grado :: (Ix v,Num p) => Grafo v p -> v -> Int\r\n-- tal que (grado g v) es el grado del v\u00e9rtice v en el grafo g. Por\r\n-- ejemplo, \r\n--    grado g1 5  ==  4\r\n--    grado g2 5  ==  3\r\n--    grado g2 1  ==  3\r\n--    grado g3 2  ==  4\r\n--    grado g5 1  ==  2\r\n-- ---------------------------------------------------------------------\r\n\r\ngrado :: (Ix v,Num p) => Grafo v p -> v -> Int\r\ngrado g v = sum [1 | (x,y,p) <- as, x == v] +\r\n            sum [1 | (x,y,p) <- as, y == v]\r\n    where as = aristas g\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 17. Comprobar con QuickCheck que si g es un grafo dirigido,\r\n-- entonces, para todo v\u00e9rtice v de g, el grado de v en g es la suma del \r\n-- grado positivo y del grado negativo de v en g.\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_grados :: Grafo Int Int -> Property\r\nprop_grados g =\r\n    dirigido g ==>\r\n    and [grado g v == gradoPos g v + gradoNeg g v | v <- nodos g]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_grados\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 18. Comprobar con QuickCheck que para cualquier grafo g, la\r\n-- suma de los grados positivos de los v\u00e9rtices de g es igual que la\r\n-- suma de los grados negativos de los v\u00e9rtices de g.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_sumaGrados:: Grafo Int Int -> Bool\r\nprop_sumaGrados g = \r\n    sum [gradoPos g v | v <- vs] == sum [gradoNeg g v | v <- vs] \r\n    where vs = nodos g\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_sumaGrados\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 19. Comprobar con QuickCheck que para cualquier grafo g, la\r\n-- suma de los grados de los v\u00e9rtices de g es el doble del n\u00famero de\r\n-- aristas de g. \r\n-- ---------------------------------------------------------------------\r\n\r\nprop_sumaGradosDoble:: Grafo Int Int -> Bool\r\nprop_sumaGradosDoble g = \r\n    sum [grado g v | v <- nodos g] == 2 * nAristas g \r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_sumaGradosDoble\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 20. Comprobar con QuickCheck que en todo grafo, el n\u00famero\r\n-- de nodos de grado impar es par. \r\n-- ---------------------------------------------------------------------\r\n\r\nprop_numNodosGradoImpar :: Grafo Int Int -> Bool\r\nprop_numNodosGradoImpar g = even m\r\n    where vs = nodos g\r\n          m = length [v | v <- vs, odd(grado g v)]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_numNodosGradoImpar\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 21. Un grafo es regular si todos sus v\u00e9rtices tienen el\r\n-- mismo grado. Definir la funci\u00f3n\r\n--    regular :: (Ix v,Num p) => Grafo v p -> Bool\r\n-- tal que (regular g) se verifica si todos los nodos de g tienen el\r\n-- mismo grado. \r\n--    regular g1            ==  False\r\n--    regular g2            ==  False\r\n--    regular (completo 4)  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nregular :: (Ix v,Num p) => Grafo v p -> Bool\r\nregular g = and [grado g v == k | v <- vs]\r\n    where vs = nodos g\r\n          k  = grado g (head vs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 22. Definir la propiedad\r\n--    prop_CompletoRegular :: Int -> Int -> Bool\r\n-- tal que (prop_CompletoRegular m n) se verifica si todos los grafos\r\n-- completos desde el de orden m hasta el de orden m son regulares y\r\n-- usarla para comprobar que todos los grafos completo desde el de orden\r\n-- 1 hasta el de orden 30 son regulares.\r\n-- --------------------------------------------------------------------- \r\n\r\nprop_CompletoRegular :: Int -> Int -> Bool\r\nprop_CompletoRegular m n = and [regular (completo x) | x <- [m..n]]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> prop_CompletoRegular 1 30\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 23. Un grafo es k-regular si todos sus v\u00e9rtices son de\r\n-- grado k. Definir la funci\u00f3n\r\n--    regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int\r\n-- tal que (regularidad g) es la regularidad de g. Por ejemplo,\r\n--    regularidad g1              ==  Nothing\r\n--    regularidad (completo 4)    ==  Just 3\r\n--    regularidad (completo 5)    ==  Just 4\r\n--    regularidad (grafoCiclo 4)  ==  Just 2\r\n--    regularidad (grafoCiclo 5)  ==  Just 2\r\n-- ---------------------------------------------------------------------\r\n\r\nregularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int\r\nregularidad g | regular g = Just (grado g (head (nodos g)))\r\n              | otherwise = Nothing    \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 24. Definir la propiedad\r\n--    prop_completoRegular :: Int -> Bool\r\n-- tal que (prop_completoRegular n) se verifica si el grafo completo de\r\n-- orden n es (n-1)-regular. Por ejemplo,\r\n--    prop_completoRegular 5  ==  True\r\n-- y usarla para comprobar que la cumplen todos los grafos completos\r\n-- desde orden 1 hasta 20.\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_completoRegular :: Int -> Bool\r\nprop_completoRegular n = \r\n   regularidad (completo n) == Just (n-1)\r\n\r\n-- La comprobaci\u00f3n es                       \r\n--    ghci> and [prop_completoRegular n | n <- [1..20]]\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 25. Definir la propiedad\r\n--    prop_cicloRegular :: Int -> Bool\r\n-- tal que (prop_cicloRegular n) se verifica si el grafo ciclo de orden\r\n-- n es 2-regular. Por ejemplo, \r\n--    prop_cicloRegular 2  ==  True\r\n-- y usarla para comprobar que la cumplen todos los grafos ciclos\r\n-- desde orden 3 hasta 20.\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_cicloRegular :: Int -> Bool\r\nprop_cicloRegular n = \r\n   regularidad (grafoCiclo n) == Just 2\r\n\r\n-- La comprobaci\u00f3n es                       \r\n--    ghci> and [prop_cicloRegular n | n <- [3..20]]\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Generador de grafos                                                --\r\n-- ---------------------------------------------------------------------\r\n\r\ninstance Arbitrary (Grafo Int Int) where\r\n    arbitrary = genG\r\n\r\ngenG :: Gen (Grafo Int Int)\r\ngenG = do d <- choose (True,False)\r\n          n <- choose (1,10)\r\n          xs <- vectorOf (n*n) arbitrary\r\n          if d then return (generaGD n xs)\r\n               else return (generaGND n xs)\r\n\r\ngeneraGND :: Int -> [Int] -> Grafo Int Int\r\ngeneraGND n ls  = creaGrafo False (1,n) l3\r\n    where l1 = [(x,y) | x <-[1..n], y <- [1..n], x < y]\r\n          l2 = zip l1 ls\r\n          l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]\r\n\r\ngeneraGD :: Int -> [Int] -> Grafo Int Int\r\ngeneraGD n ls = creaGrafo True (1,n) l3\r\n    where l1 = [(x,y) | x <-[1..n], y <- [1..n]]\r\n          l2 = zip l1 ls\r\n          l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]\r\n<\/pre>\n<p>Las soluciones de las relaciones anteriores se encuentran en el libro <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/ejercicios\/ejercicios-I1M-2010.pdf\">Ejercicios de &#8220;Inform\u00e1tica de 1\u00ba de Matem\u00e1ticas&#8221; (Curso 2010-11)<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios sobre el tipos abstracto de datos de los grafos en Haskell de la 30\u00aa relaci\u00f3n. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[133],"tags":[287],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1384"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=1384"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1384\/revisions"}],"predecessor-version":[{"id":1386,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1384\/revisions\/1386"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1384"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1384"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1384"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}