{"id":4268,"date":"2014-04-22T18:21:22","date_gmt":"2014-04-22T16:21:22","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4268"},"modified":"2014-04-27T10:35:19","modified_gmt":"2014-04-27T08:35:19","slug":"i1m2013-ejercicios-con-el-tad-de-grafos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-ejercicios-con-el-tad-de-grafos-en-haskell\/","title":{"rendered":"I1M2013: Ejercicios con el TAD de grafos en Haskell"},"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 4 primeros ejercicios sobre grafos de la 28\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\">\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, utilizando las implementaciones estudiadas\n-- en el tema 22 que se pueden descargar desde \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\/codigos.zip\n--\n-- Las transparencias del tema 22 se encuentran en\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\/temas\/tema-22.pdf\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 seleccionar una implementaci\u00f3n del TAD de los grafos\nimport GrafoConVectorDeAdyacencia \n-- import GrafoConMatrizDeAdyacencia \n-- import Rel_29_sol\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 :: 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)]\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 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 = creaGrafo ND (1,n) xs\n    where xs = [(x,y,0) | x <- [1..n], y <- [1..n], x < y]\n\ncompleto' :: Int -> Grafo Int Int\ncompleto' n = creaGrafo ND (1,n) [(a,b,0)|a<-[1..n],b<-[1..a-1]]\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 = creaGrafo ND (1,n) xs\n    where xs = [(x,x+1,0) | x <- [1..n-1]] ++ [(n,1,0)]\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<\/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 4 primeros ejercicios sobre grafos de la 28\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":[222],"tags":[270,300],"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\/4268"}],"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=4268"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4268\/revisions"}],"predecessor-version":[{"id":4283,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4268\/revisions\/4283"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4268"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4268"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4268"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}