{"id":5419,"date":"2016-05-06T17:43:18","date_gmt":"2016-05-06T15:43:18","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5419"},"modified":"2017-02-07T19:25:57","modified_gmt":"2017-02-07T18:25:57","slug":"i1m2015-ejercicios-con-el-tad-de-grafos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-ejercicios-con-el-tad-de-grafos-en-haskell\/","title":{"rendered":"I1M2015: Ejercicios con el TAD de grafos en Haskell"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones de los ejercicios sobre grafos de la relaci\u00f3n 36.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n de ejercicios es definir funciones sobre \n-- el TAD de los grafos estudiado en el tema 22 \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\/temas\/tema-22.html\n-- \n-- Para realizar los ejercicios hay que tener instalada la librer\u00eda I1M\n-- que contiene la implementaci\u00f3n de TAD de los polinomios. Los pasos\n-- para instalarla son los siguientes:\n-- + Descargar el paquete I1M desde http:\/\/bit.ly\/1pbnDqm\n-- + Descomprimirlo (y se crea el directorio I1M-master.zip).\n-- + Cambiar al directorio I1M-master.\n-- + Ejecutar cabal install I1M.cabal\n-- \n-- Otra forma es descargar, en el directorio de ejercicios, la\n-- implementaci\u00f3n del TAD de grafos \n-- + GrafoConVectorDeAdyacencia que est\u00e1 en http:\/\/bit.ly\/1SQnG4S\n-- + GrafoConMatrizDeAdyacencia que est\u00e1 en http:\/\/bit.ly\/1SQnGlB\n-- \n-- Los m\u00f3dulos anteriores se encuentras en la p\u00e1gina de c\u00f3digos \n-- http:\/\/bit.ly\/1SQnAKO\n \n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas                                           --\n-- ---------------------------------------------------------------------\n\n{-# LANGUAGE FlexibleInstances, TypeSynonymInstances #-}\n\nimport Data.Array\nimport Data.List (nub)\nimport Test.QuickCheck\n\n-- Hay que elegir una librer\u00eda \nimport I1M.Grafo\n-- import GrafoConVectorDeAdyacencia \n-- import GrafoConMatrizDeAdyacencia \n\n-- ---------------------------------------------------------------------\n-- Ejemplos                                                           --\n-- ---------------------------------------------------------------------\n\n-- Para los ejemplos se usar\u00e1n los siguientes grafos.\ng1, g2, g3, g4, g5, g6, g7, g8, g9, g10, g11, g12 :: Grafo Int Int\ng1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                         (2,4,55),(2,5,32),\n                         (3,4,61),(3,5,44),\n                         (4,5,93)]\ng2 = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                        (2,4,55),(2,5,32),\n                        (4,3,61),(4,5,93)]\ng3 = creaGrafo D (1,3) [(1,2,0),(2,2,0),(3,1,0),(3,2,0)]\ng4 = creaGrafo D (1,4) [(1,2,3),(2,1,5)]\ng5 = creaGrafo D (1,1) [(1,1,0)]\ng6 = creaGrafo D (1,4) [(1,3,0),(3,1,0),(3,3,0),(4,2,0)]\ng7 = creaGrafo ND (1,4) [(1,3,0)]\ng8 = creaGrafo D (1,5) [(1,1,0),(1,2,0),(1,3,0),(2,4,0),(3,1,0),\n                        (4,1,0),(4,2,0),(4,4,0),(4,5,0)]\ng9 = creaGrafo D (1,5) [(4,1,1),(4,3,2),(5,1,0)]\ng10 = creaGrafo ND (1,3) [(1,2,1),(1,3,1),(2,3,1),(3,3,1)]\ng11 = creaGrafo D (1,3) [(1,2,1),(1,3,1),(2,3,1),(3,3,1)]\ng12 = creaGrafo ND (1,4) [(1,1,0),(1,2,0),(3,3,0)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. El grafo completo de orden n, K(n), es un grafo no\n-- dirigido cuyos conjunto de v\u00e9rtices es {1,..n} y tiene una arista\n-- entre cada par de v\u00e9rtices distintos. Definir la funci\u00f3n,\n--    completo :: Int -> Grafo Int Int\n-- tal que (completo n) es el grafo completo de orden n. Por ejemplo,\n--    ghci> completo 4\n--    G ND (array (1,4) [(1,[(2,0),(3,0),(4,0)]),\n--                       (2,[(1,0),(3,0),(4,0)]),\n--                       (3,[(1,0),(2,0),(4,0)]),\n--                       (4,[(1,0),(2,0),(3,0)])])\n-- ---------------------------------------------------------------------\n\ncompleto :: Int -> Grafo Int Int \ncompleto n = \n    creaGrafo ND (1,n) [(x,y,0) | x <- [1..n], y <- [x+1..n]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. El ciclo de orden n, C(n), es un grafo no dirigido\n-- cuyo conjunto de v\u00e9rtices es {1,...,n} y las aristas son\n--    (1,2), (2,3), ..., (n-1,n), (n,1)\n-- Definir la funci\u00f3n\n--    grafoCiclo :: Int -> Grafo Int Int\n-- tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,\n--    ghci> grafoCiclo 3\n--    G ND (array (1,3) [(1,[(3,0),(2,0)]),(2,[(1,0),(3,0)]),(3,[(2,0),(1,0)])])\n-- ---------------------------------------------------------------------\n\ngrafoCiclo :: Int -> Grafo Int Int\ngrafoCiclo n = \n    creaGrafo ND (1,n) ((n,1,0):[(x,x+1,0) | x <- [1..n-1]])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    nVertices :: (Ix v,Num p) => Grafo v p ->  Int\n-- tal que (nVertices g) es el n\u00famero de v\u00e9rtices del grafo g. Por\n-- ejemplo, \n--    nVertices (completo 4)  ==  4\n--    nVertices (completo 5)  ==  5\n-- ---------------------------------------------------------------------\n\nnVertices :: (Ix v,Num p) => Grafo v p ->  Int\nnVertices = length . nodos\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    noDirigido :: (Ix v,Num p) => Grafo v p ->  Bool\n-- tal que (noDirigido g) se verifica si el grafo g es no dirigido. Por\n-- ejemplo, \n--    noDirigido g1            ==  True\n--    noDirigido g2            ==  False\n--    noDirigido (completo 4)  ==  True\n-- ---------------------------------------------------------------------\n\nnoDirigido :: (Ix v,Num p) => Grafo v p ->  Bool\nnoDirigido = not . dirigido\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. En un un grafo g, los incidentes de un v\u00e9rtice v es el\n-- conjuntos de v\u00e9rtices x de g para los que hay un arco (o una arista)\n-- de x a v; es decir, que v es adyacente a x. Definir la funci\u00f3n\n--    incidentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]\n-- tal que (incidentes g v) es la lista de los v\u00e9rtices incidentes en el\n-- v\u00e9rtice v. Por ejemplo,\n--    incidentes g2 5  ==  [1,2,4]\n--    adyacentes g2 5  ==  []\n--    incidentes g1 5  ==  [1,2,3,4]\n--    adyacentes g1 5  ==  [1,2,3,4]\n-- --------------------------------------------------------------------- \n\nincidentes :: (Ix v,Num p) => Grafo v p -> v -> [v]\nincidentes g v = [x | x <- nodos g, v `elem` adyacentes g x]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. En un un grafo g, los contiguos de un v\u00e9rtice v es el\n-- conjuntos de v\u00e9rtices x de g tales que x es adyacente o incidente con\n-- v. Definir la funci\u00f3n\n--    contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v]\n-- tal que (contiguos g v) es el conjunto de los v\u00e9rtices de g contiguos\n-- con el v\u00e9rtice v. Por ejemplo,\n--    contiguos g2 5  ==  [1,2,4]\n--    contiguos g1 5  ==  [1,2,3,4]\n-- ---------------------------------------------------------------------\n\ncontiguos :: (Ix v,Num p) => Grafo v p -> v -> [v]\ncontiguos g v = nub (adyacentes g v ++ incidentes g v)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)]\n-- tal que (lazos g) es el conjunto de los lazos (es decir, aristas\n-- cuyos extremos son iguales) del grafo g. Por ejemplo, \n--    ghci> lazos g3\n--    [(2,2)]\n--    ghci> lazos g2\n--    []\n-- ---------------------------------------------------------------------\n\nlazos :: (Ix v,Num p) => Grafo v p -> [(v,v)]\nlazos g = [(x,x) | x <- nodos g, aristaEn g (x,x)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    nLazos :: (Ix v,Num p) => Grafo v p ->  Int\n-- tal que (nLazos g) es el n\u00famero de lazos del grafo g. Por\n-- ejemplo, \n--    nLazos g3  ==  1\n--    nLazos g2  ==  0\n-- ---------------------------------------------------------------------\n\nnLazos :: (Ix v,Num p) => Grafo v p ->  Int\nnLazos = length . lazos\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    nAristas :: (Ix v,Num p) => Grafo v p ->  Int\n-- tal que (nAristas g) es el n\u00famero de aristas del grafo g. Si g es no\n-- dirigido, las aristas de v1 a v2 y de v2 a v1 s\u00f3lo se cuentan una\n-- vez. Por ejemplo, \n--    nAristas g1            ==  8\n--    nAristas g2            ==  7\n--    nAristas g10           ==  4\n--    nAristas g12           ==  3\n--    nAristas (completo 4)  ==  6\n--    nAristas (completo 5)  ==  10\n-- ---------------------------------------------------------------------\n\nnAristas :: (Ix v,Num p) => Grafo v p ->  Int\nnAristas g | dirigido g = length (aristas g)\n           | otherwise  = (length (aristas g) + nLazos g) `div` 2\n\n-- 2\u00aa definici\u00f3n\nnAristas2 :: (Ix v,Num p) => Grafo v p ->  Int\nnAristas2 g | dirigido g = length (aristas g)\n            | otherwise  = length [(x,y) | (x,y,_) <- aristas g, x <= y]\n                          \n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    prop_nAristasCompleto :: Int -> Bool\n-- tal que (prop_nAristasCompleto n) se verifica si el n\u00famero de aristas\n-- del grafo completo de orden n es n*(n-1)\/2 y, usando la funci\u00f3n,\n-- comprobar que la propiedad se cumple para n de 1 a 20.\n-- ---------------------------------------------------------------------\n\nprop_nAristasCompleto :: Int -> Bool\nprop_nAristasCompleto n =\n    nAristas (completo n) == n*(n-1) `div` 2\n\n-- La comprobaci\u00f3n es\n--    ghci> and [prop_nAristasCompleto n | n <- [1..20]]\n--    True\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. El grado positivo de un v\u00e9rtice v de un grafo dirigido\n-- g, es el n\u00famero de v\u00e9rtices de g adyacentes con v. Definir la funci\u00f3n  \n--    gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int\n-- tal que (gradoPos g v) es el grado positivo del v\u00e9rtice v en el grafo\n-- g. Por ejemplo,\n--    gradoPos g1 5  ==  4\n--    gradoPos g2 5  ==  0\n--    gradoPos g2 1  ==  3\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\ngradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int\ngradoPos g v = length (adyacentes g v)\n\n-- 2\u00aa definici\u00f3n\ngradoPos2 :: (Ix v,Num p) => Grafo v p -> v -> Int\ngradoPos2 g = length .(adyacentes g)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. El grado negativo de un v\u00e9rtice v de un grafo dirigido\n-- g, es el n\u00famero de v\u00e9rtices de g incidentes con v. Definir la funci\u00f3n  \n--    gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int\n-- tal que (gradoNeg g v) es el grado negativo del v\u00e9rtice v en el grafo\n-- g. Por ejemplo,\n--    gradoNeg g1 5  ==  4\n--    gradoNeg g2 5  ==  3\n--    gradoNeg g2 1  ==  0\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\ngradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int\ngradoNeg g v = length (incidentes g v)\n\n-- 2\u00aa definici\u00f3n\ngradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int\ngradoNeg g = length (incidentes g)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. El grado de un v\u00e9rtice v de un grafo dirigido g, es el\n-- n\u00famero de aristas de g que contiene a v. Si g es no dirigido, el\n-- grado de un v\u00e9rtice v es el n\u00famero de aristas incidentes en v, teniendo\n-- en cuenta que los lazos se cuentan dos veces. Definir la funci\u00f3n    \n--    grado :: (Ix v,Num p) => Grafo v p -> v -> Int\n-- tal que (grado g v) es el grado del v\u00e9rtice v en el grafo g. Por\n-- ejemplo, \n--    grado g1 5  ==  4\n--    grado g2 5  ==  3\n--    grado g2 1  ==  3 \n--    grado g3 2  ==  4\n--    grado g3 1  ==  2\n--    grado g3 3  ==  2\n--    grado g5 1  ==  2\n--    grado g10 3 ==  4\n--    grado g11 3 ==  4\n-- ---------------------------------------------------------------------\n\ngrado :: (Ix v,Num p) => Grafo v p -> v -> Int\ngrado g v | dirigido g           = gradoNeg g v + gradoPos g v\n          | (v,v) `elem` lazos g = length (incidentes g v) + 1 \n          | otherwise            = length (incidentes g v)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Comprobar con QuickCheck que para cualquier grafo g, la\n-- suma de los grados positivos de los v\u00e9rtices de g es igual que la\n-- suma de los grados negativos de los v\u00e9rtices de g.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_sumaGrados:: Grafo Int Int -> Bool\nprop_sumaGrados g = \n    sum [gradoPos g v | v <- vs] == sum [gradoNeg g v | v <- vs] \n    where vs = nodos g\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_sumaGrados\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. En la teor\u00eda de grafos, se conoce como \"Lema del\n-- apret\u00f3n de manos\" la siguiente propiedad: la suma de los grados de\n-- los v\u00e9rtices de g es el doble del n\u00famero de aristas de g. \n-- Comprobar con QuickCheck que para cualquier grafo g, se verifica\n-- dicha propiedad.\n-- ---------------------------------------------------------------------\n\nprop_apretonManos:: Grafo Int Int -> Bool\nprop_apretonManos g = \n    sum [grado g v | v <- nodos g] == 2 * nAristas g \n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_apretonManos\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Comprobar con QuickCheck que en todo grafo, el n\u00famero\n-- de nodos de grado impar es par. \n-- ---------------------------------------------------------------------\n\nprop_numNodosGradoImpar :: Grafo Int Int -> Bool\nprop_numNodosGradoImpar g = even m\n    where vs = nodos g\n          m = length [v | v <- vs, odd (grado g v)]\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_numNodosGradoImpar\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Definir la propiedad\n--   prop_GradoCompleto :: Int -> Bool\n-- tal que (prop_GradoCompleto n) se verifica si todos los v\u00e9rtices del\n-- grafo completo K(n) tienen grado n-1. Usarla para comprobar que dicha\n-- propiedad se verifica para los grafos completos de grados 1 hasta 30.\n-- ---------------------------------------------------------------------\n\nprop_GradoCompleto :: Int -> Bool\nprop_GradoCompleto n = \n    and [grado g v == (n-1) | v <- nodos g]\n    where g = completo n\n\n-- La comprobaci\u00f3n es                       \n--    ghci> and [prop_GradoCompleto n | n <- [1..30]]\n--    True\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Un grafo es regular si todos sus v\u00e9rtices tienen el\n-- mismo grado. Definir la funci\u00f3n\n--    regular :: (Ix v,Num p) => Grafo v p -> Bool\n-- tal que (regular g) se verifica si todos los nodos de g tienen el\n-- mismo grado. \n--    regular g1            ==  False\n--    regular g2            ==  False\n--    regular (completo 4)  ==  True\n-- ---------------------------------------------------------------------\n\nregular :: (Ix v,Num p) => Grafo v p -> Bool\nregular g = and [grado g v == k | v <- vs]\n    where vs = nodos g\n          k  = grado g (head vs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Definir la propiedad\n--    prop_CompletoRegular :: Int -> Int -> Bool\n-- tal que (prop_CompletoRegular m n) se verifica si todos los grafos\n-- completos desde el de orden m hasta el de orden m son regulares y\n-- usarla para comprobar que todos los grafos completo desde el de orden\n-- 1 hasta el de orden 30 son regulares.\n-- --------------------------------------------------------------------- \n\nprop_CompletoRegular :: Int -> Int -> Bool\nprop_CompletoRegular m n = \n    and [regular (completo x) | x <- [m..n]]\n\n-- La comprobaci\u00f3n es\n--    ghci> prop_CompletoRegular 1 30\n--    True\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 20. Un grafo es k-regular si todos sus v\u00e9rtices son de\n-- grado k. Definir la funci\u00f3n\n--    regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int\n-- tal que (regularidad g) es la regularidad de g. Por ejemplo,\n--    regularidad g1              ==  Nothing\n--    regularidad (completo 4)    ==  Just 3\n--    regularidad (completo 5)    ==  Just 4\n--    regularidad (grafoCiclo 4)  ==  Just 2\n--    regularidad (grafoCiclo 5)  ==  Just 2\n-- ---------------------------------------------------------------------\n\nregularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int\nregularidad g \n    | regular g = Just (grado g (head (nodos g)))\n    | otherwise = Nothing    \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 21. Definir la propiedad\n--    prop_completoRegular :: Int -> Bool\n-- tal que (prop_completoRegular n) se verifica si el grafo completo de\n-- orden n es (n-1)-regular. Por ejemplo,\n--    prop_completoRegular 5  ==  True\n-- y usarla para comprobar que la cumplen todos los grafos completos\n-- desde orden 1 hasta 20.\n-- ---------------------------------------------------------------------\n\nprop_completoRegular :: Int -> Bool\nprop_completoRegular n = \n   regularidad (completo n) == Just (n-1)\n\n-- La comprobaci\u00f3n es                       \n--    ghci> and [prop_completoRegular n | n <- [1..20]]\n--    True\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 22. Definir la propiedad\n--    prop_cicloRegular :: Int -> Bool\n-- tal que (prop_cicloRegular n) se verifica si el grafo ciclo de orden\n-- n es 2-regular. Por ejemplo, \n--    prop_cicloRegular 2  ==  True\n-- y usarla para comprobar que la cumplen todos los grafos ciclos\n-- desde orden 3 hasta 20.\n-- ---------------------------------------------------------------------\n\nprop_cicloRegular :: Int -> Bool\nprop_cicloRegular n = \n   regularidad (grafoCiclo n) == Just 2\n\n-- La comprobaci\u00f3n es                       \n--    ghci> and [prop_cicloRegular n | n <- [3..20]]\n--    True\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Generador de grafos                                              --\n-- ---------------------------------------------------------------------\n\n-- (generaGND n ps) es el grafo completo de orden n tal que los pesos\n-- est\u00e1n determinados por ps. Por ejemplo,\n--    ghci> generaGND 3 [4,2,5]\n--    (ND,array (1,3) [(1,[(2,4),(3,2)]),\n--                     (2,[(1,4),(3,5)]),\n--                      3,[(1,2),(2,5)])])\n--    ghci> generaGND 3 [4,-2,5]\n--    (ND,array (1,3) [(1,[(2,4)]),(2,[(1,4),(3,5)]),(3,[(2,5)])])\ngeneraGND :: Int -> [Int] -> Grafo Int Int\ngeneraGND n ps  = creaGrafo ND (1,n) l3\n    where l1 = [(x,y) | x <- [1..n], y <- [1..n], x < y]\n          l2 = zip l1 ps\n          l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]\n\n-- (generaGD n ps) es el grafo completo de orden n tal que los pesos\n-- est\u00e1n determinados por ps. Por ejemplo,\n--    ghci> generaGD 3 [4,2,5]\n--    (D,array (1,3) [(1,[(1,4),(2,2),(3,5)]),\n--                    (2,[]),\n--                    (3,[])])\n--    ghci> generaGD 3 [4,2,5,3,7,9,8,6]\n--    (D,array (1,3) [(1,[(1,4),(2,2),(3,5)]),\n--                    (2,[(1,3),(2,7),(3,9)]),\n--                    (3,[(1,8),(2,6)])])\ngeneraGD :: Int -> [Int] -> Grafo Int Int\ngeneraGD n ps = creaGrafo D (1,n) l3\n    where l1 = [(x,y) | x <- [1..n], y <- [1..n]]\n          l2 = zip l1 ps\n          l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]\n\n-- genGD es un generador de grafos dirigidos. Por ejemplo,\n--    ghci> sample genGD\n--    (D,array (1,4) [(1,[(1,1)]),(2,[(3,1)]),(3,[(2,1),(4,1)]),(4,[(4,1)])])\n--    (D,array (1,2) [(1,[(1,6)]),(2,[])])\n--    ...\ngenGD :: Gen (Grafo Int Int)\ngenGD = do n <- choose (1,10)\n           xs <- vectorOf (n*n) arbitrary\n           return (generaGD n xs)\n\n-- genGND es un generador de grafos dirigidos. Por ejemplo,\n--    ghci> sample genGND\n--    (ND,array (1,1) [(1,[])])\n--    (ND,array (1,3) [(1,[(2,3),(3,13)]),(2,[(1,3)]),(3,[(1,13)])])\n--    ...\ngenGND :: Gen (Grafo Int Int)\ngenGND = do n <- choose (1,10)\n            xs <- vectorOf (n*n) arbitrary\n            return (generaGND n xs)\n\n-- genG es un generador de grafos. Por ejemplo,\n--    ghci> sample genG\n--    (D,array (1,3) [(1,[(2,1)]),(2,[(1,1),(2,1)]),(3,[(3,1)])])\n--    (ND,array (1,3) [(1,[(2,2)]),(2,[(1,2)]),(3,[])])\n--    ...\ngenG :: Gen (Grafo Int Int)\ngenG = do d <- choose (True,False)\n          n <- choose (1,10)\n          xs <- vectorOf (n*n) arbitrary\n          if d then return (generaGD n xs)\n               else return (generaGND n xs)\n\n-- Los grafos est\u00e1 contenido en la clase de los objetos generables\n-- aleatoriamente. \ninstance Arbitrary (Grafo Int Int) where\n    arbitrary = genG\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones de los ejercicios sobre grafos de la relaci\u00f3n 36. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[250],"tags":[244,270,310],"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\/5419"}],"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=5419"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5419\/revisions"}],"predecessor-version":[{"id":5683,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5419\/revisions\/5683"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5419"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}