{"id":3663,"date":"2013-06-06T13:29:08","date_gmt":"2013-06-06T11:29:08","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3663"},"modified":"2013-09-21T13:30:01","modified_gmt":"2013-09-21T11:30:01","slug":"i1m20102-problemas-basicos-con-el-tad-de-los-grafos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m20102-problemas-basicos-con-el-tad-de-los-grafos\/","title":{"rendered":"I1M20102: Problemas b\u00e1sicos con el TAD de los grafos"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones de los ejercicios sobre grafos de la 30\u00aa relaci\u00f3n.<\/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-12\/codigos.zip\r\n--\r\n-- Las transparencias del tema 22 se encuentran en\r\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\/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 Rel_29_sol\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, g9, g10, g11 :: Grafo Int Int\r\ng1 = creaGrafo ND (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 D (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 D (1,3) [(1,2,0),(2,2,0),(3,1,0),(3,2,0)]\r\ng4 = creaGrafo D (1,4) [(1,2,3),(2,1,5)]\r\ng5 = creaGrafo D (1,1) [(1,1,0)]\r\ng6 = creaGrafo D (1,4) [(1,3,0),(3,1,0),(3,3,0),(4,2,0)]\r\ng7 = creaGrafo ND (1,4) [(1,3,0)]\r\ng8 = creaGrafo D (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\ng9 = creaGrafo D (1,5) [(4,1,1),(4,3,2),(5,1,0)]\r\ng10 = creaGrafo ND (1,3) [(1,2,1),(1,3,1),(2,3,1),(3,3,1)]\r\ng11 = creaGrafo D (1,3) [(1,2,1),(1,3,1),(2,3,1),(3,3,1)]\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--    G ND (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 ND (1,n) xs\r\n    where xs = [(x,y,0) | x <- [1..n], y <- [1..n], x < y]\r\n\r\ncompleto' :: Int -> Grafo Int Int\r\ncompleto' n = creaGrafo ND (1,n) [(a,b,0)|a<-[1..n],b<-[1..a-1]]\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--    G ND (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 ND (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 4. 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 5. 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 6. 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 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. 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. Si g es no\r\n-- dirigido, las aristas de v1 a v2 y de v2 a v1 s\u00f3lo se cuentan una\r\n-- vez y los lazos se cuentan dos veces. Por ejemplo, \r\n--    nAristas g1            ==  8\r\n--    nAristas g2            ==  7\r\n--    nAristas g10           ==  4\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 g \r\n    | dirigido g = length (aristas g)\r\n    | otherwise  = (length (aristas g) `div` 2) + nLazos g\r\n                          \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. 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 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 13. El grado de un v\u00e9rtice v de un grafo dirigido g, es el\r\n-- n\u00famero de aristas de g que contiene a v. Si g es no dirigido, el\r\n-- grado de un v\u00e9rtice v es el n\u00famero de aristas incidentes en v, teniendo\r\n-- en cuenta que los lazos se cuentan dos veces. Definir 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 g3 1  ==  2\r\n--    grado g3 3  ==  2\r\n--    grado g5 1  ==  3\r\n--    grado g10 3 == 4\r\n--    grado g11 3 == 4\r\n-- ---------------------------------------------------------------------\r\n\r\ngrado :: (Ix v,Num p) => Grafo v p -> v -> Int\r\ngrado g v | dirigido g           = gradoNeg g v + gradoPos g v\r\n          | (v,v) `elem` lazos g = length (incidentes g v) + 1 \r\n          | otherwise            = length (incidentes g v)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. 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 15. En la teor\u00eda de grafos, se conoce como \"Lema del\r\n-- apret\u00f3n de manos\" la siguiente propiedad: la suma de los grados de\r\n-- los v\u00e9rtices de g es el doble del n\u00famero de aristas de g. \r\n-- Comprobar con QuickCheck que para cualquier grafo g, se verifica\r\n-- dicha propiedad.\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_apretonManos:: Grafo Int Int -> Bool\r\nprop_apretonManos 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_apretonManos\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. 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 17. Definir la propiedad\r\n--   prop_GradoCompleto :: Int -> Bool\r\n-- tal que (prop_GradoCompleto n) se verifica si todos los v\u00e9rtices del\r\n-- grafo completo K(n) tienen grado n-1. Usarla para comprobar que dicha\r\n-- propiedad se verifica para los grafos completos de grados 1 hasta 30.\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_GradoCompleto :: Int -> Bool\r\nprop_GradoCompleto n = \r\n    and [grado g v == (n-1) | v <- nodos g]\r\n        where g = completo n\r\n\r\n-- La comprobaci\u00f3n es                       \r\n--    ghci> and [prop_GradoCompleto n | n <- [1..30]]\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 18. 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 19. 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 20. 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 21. 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 22. 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-- \u00a7 Generador de grafos                                              --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (generaGND n ps) es el grafo completo de orden n tal que los pesos\r\n-- est\u00e1n determinados por ps. Por ejemplo,\r\n--    ghci> generaGND 3 [4,2,5]\r\n--    (ND,array (1,3) [(1,[(2,4),(3,2)]),\r\n--                     (2,[(1,4),(3,5)]),\r\n--                      3,[(1,2),(2,5)])])\r\n--    ghci> generaGND 3 [4,-2,5]\r\n--    (ND,array (1,3) [(1,[(2,4)]),(2,[(1,4),(3,5)]),(3,[(2,5)])])\r\ngeneraGND :: Int -> [Int] -> Grafo Int Int\r\ngeneraGND n ps  = creaGrafo ND (1,n) l3\r\n    where l1 = [(x,y) | x <- [1..n], y <- [1..n], x < y]\r\n          l2 = zip l1 ps\r\n          l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]\r\n\r\n-- (generaGD n ps) es el grafo completo de orden n tal que los pesos\r\n-- est\u00e1n determinados por ps. Por ejemplo,\r\n--    ghci> generaGD 3 [4,2,5]\r\n--    (D,array (1,3) [(1,[(1,4),(2,2),(3,5)]),\r\n--                    (2,[]),\r\n--                    (3,[])])\r\n--    ghci> generaGD 3 [4,2,5,3,7,9,8,6]\r\n--    (D,array (1,3) [(1,[(1,4),(2,2),(3,5)]),\r\n--                    (2,[(1,3),(2,7),(3,9)]),\r\n--                    (3,[(1,8),(2,6)])])\r\ngeneraGD :: Int -> [Int] -> Grafo Int Int\r\ngeneraGD n ps = creaGrafo D (1,n) l3\r\n    where l1 = [(x,y) | x <- [1..n], y <- [1..n]]\r\n          l2 = zip l1 ps\r\n          l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]\r\n\r\n-- genGD es un generador de grafos dirigidos. Por ejemplo,\r\n--    ghci> sample genGD\r\n--    (D,array (1,4) [(1,[(1,1)]),(2,[(3,1)]),(3,[(2,1),(4,1)]),(4,[(4,1)])])\r\n--    (D,array (1,2) [(1,[(1,6)]),(2,[])])\r\n--    ...\r\ngenGD :: Gen (Grafo Int Int)\r\ngenGD = do n <- choose (1,10)\r\n           xs <- vectorOf (n*n) arbitrary\r\n           return (generaGD n xs)\r\n\r\n-- genGND es un generador de grafos dirigidos. Por ejemplo,\r\n--    ghci> sample genGND\r\n--    (ND,array (1,1) [(1,[])])\r\n--    (ND,array (1,3) [(1,[(2,3),(3,13)]),(2,[(1,3)]),(3,[(1,13)])])\r\n--    ...\r\ngenGND :: Gen (Grafo Int Int)\r\ngenGND = do n <- choose (1,10)\r\n            xs <- vectorOf (n*n) arbitrary\r\n            return (generaGND n xs)\r\n\r\n-- genG es un generador de grafos. Por ejemplo,\r\n--    ghci> sample genG\r\n--    (D,array (1,3) [(1,[(2,1)]),(2,[(1,1),(2,1)]),(3,[(3,1)])])\r\n--    (ND,array (1,3) [(1,[(2,2)]),(2,[(1,2)]),(3,[])])\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\n-- Los grafos est\u00e1 contenido en la clase de los objetos generables\r\n-- aleatoriamente. \r\ninstance Arbitrary (Grafo Int Int) where\r\n    arbitrary = genG\r\n<\/pre>\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 de los ejercicios sobre grafos 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":[1],"tags":[298],"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\/3663"}],"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=3663"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3663\/revisions"}],"predecessor-version":[{"id":3664,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3663\/revisions\/3664"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3663"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3663"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3663"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}