{"id":3330,"date":"2017-05-24T05:49:13","date_gmt":"2017-05-24T03:49:13","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3330"},"modified":"2021-04-25T17:03:52","modified_gmt":"2021-04-25T15:03:52","slug":"representaciones-de-grafos-17","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/representaciones-de-grafos-17\/","title":{"rendered":"Representaciones de grafos"},"content":{"rendered":"

Los grafos no dirigidos puede representarse mediante matrices de adyacencia y tambi\u00e9n mediante listas de adyacencia. Por ejemplo, el grafo<\/p>\n

\n   1 ----- 2\n   | \\     |\n   |  3    |\n   | \/     |\n   4 ----- 5\n<\/pre>\n
se puede representar por la matriz de adyacencia<\/p>\n
\n   |0 1 1 1 0|\n   |1 0 0 0 1|\n   |1 0 0 1 0|\n   |1 0 1 0 1|\n   |0 1 0 1 0|\n<\/pre>\n
donde el elemento (i,j) es 1 si hay una arista entre los v\u00e9rtices i y j y es 0 si no la hay. Tambi\u00e9n se puede representar por la lista de adyacencia<\/p>\n
\n   [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]   \n<\/pre>\n
donde las primeras componentes son los v\u00e9rtices y las segundas la lista de los v\u00e9rtices conectados.<\/p>\n
Definir las funciones<\/p>\n
\n   matrizAlista :: Matrix Int -> [(Int,[Int])]\n   listaAmatriz :: [(Int,[Int])] -> Matrix Int\n<\/pre>\n
tales que<\/p>\n
    \n
  • (matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por <\/li>\n<\/ul>\n
    \n     ejMatriz :: Matrix Int\n     ejMatriz = fromLists [[0,1,1,1,0],\n                           [1,0,0,0,1],\n                           [1,0,0,1,0],\n                           [1,0,1,0,1],\n                           [0,1,0,1,0]]\n<\/pre>\n
    se tiene que<\/p>\n
    \n     \u03bb> matrizAlista ejMatriz\n     [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]\n<\/pre>\n
      \n
    • (listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo, <\/li>\n<\/ul>\n
      \n     \u03bb> listaAmatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]\n     ( 0 1 1 1 0 )\n     ( 1 0 0 0 1 )\n     ( 1 0 0 1 0 )\n     ( 1 0 1 0 1 )\n     ( 0 1 0 1 0 )\n     \u03bb> matrizAlista it\n     [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]\n<\/pre>\n
      Soluciones<\/h4>\n
      [schedule expon=’2017-05-31′ expat=\u00bb06:00″]<\/p>\n
        \n
      • Las soluciones se pueden escribir en los comentarios hasta el 31 de mayo.\n
      • El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang=\u00bbhaskell\u00bb> y otra con <\/pre>\n<\/ul>\n
        [\/schedule]<\/p>\n
        [schedule on=’2017-05-31′ at=\u00bb06:00″]<\/p>\n
        \r\nimport Data.List (sort)\r\nimport Data.Matrix\r\n\r\nejMatriz :: Matrix Int\r\nejMatriz = fromLists [[0,1,1,1,0],\r\n                      [1,0,0,0,1],\r\n                      [1,0,0,1,0],\r\n                      [1,0,1,0,1],\r\n                      [0,1,0,1,0]]\r\n\r\nmatrizAlista :: Matrix Int -> [(Int,[Int])]\r\nmatrizAlista a = \r\n  [(i,[j | j <- [1..n], a!(i,j) == 1]) | i <- [1..n]]\r\n  where n = nrows a\r\n\r\nlistaAmatriz :: [(Int,[Int])] -> Matrix Int\r\nlistaAmatriz ps = fromLists [fila n xs | (_,xs) <- sort ps]\r\n  where n = length ps\r\n        fila n xs = [f i | i <- [1..n]]\r\n          where f i | i `elem` xs = 1\r\n                    | otherwise   = 0\r\n<\/pre>\n
        [\/schedule]<\/p>\n","protected":false},"excerpt":{"rendered":"
        Los grafos no dirigidos puede representarse mediante matrices de adyacencia y tambi\u00e9n mediante listas de adyacencia. Por ejemplo, el grafo 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…<\/p>\n","protected":false},"author":1,"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":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3330"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=3330"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3330\/revisions"}],"predecessor-version":[{"id":3331,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3330\/revisions\/3331"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3330"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3330"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3330"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}