{"id":3297,"date":"2017-05-11T06:38:15","date_gmt":"2017-05-11T04:38:15","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3297"},"modified":"2022-03-26T14:27:19","modified_gmt":"2022-03-26T12:27:19","slug":"grafo-de-divisibilidad-17","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/grafo-de-divisibilidad-17\/","title":{"rendered":"Grafo de divisibilidad"},"content":{"rendered":"<p>El grafo de divisibilidad de orden n es el grafo cuyos nodos son los n\u00fameros naturales entre 1 y n, cuyas aristas son los pares (x,y) tales que x divide a y o y divide a x y el coste de cada arista es el cociente entre su mayos y menor elemento.<\/p>\n<p>Definir las siguientes funciones:<\/p>\n<pre lang=\"text\">\n   grafoDivisibilidad :: Int -> Grafo Int Int\n   coste :: Int -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(grafoDivisibilidad n) es el grafo de divisibilidad de orden n. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n      \u03bb> grafoDivisibilidad 12\n      G ND (array (1,12)\n                  [(1,[(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),\n                       (8,8),(9,9),(10,10),(11,11),(12,12)]),\n                   (2,[(1,2),(4,2),(6,3),(8,4),(10,5),(12,6)]),\n                   (3,[(1,3),(6,2),(9,3),(12,4)]),\n                   (4,[(1,4),(2,2),(8,2),(12,3)]),\n                   (5,[(1,5),(10,2)]),\n                   (6,[(1,6),(2,3),(3,2),(12,2)]),\n                   (7,[(1,7)]),\n                   (8,[(1,8),(2,4),(4,2)]),\n                   (9,[(1,9),(3,3)]),\n                   (10,[(1,10),(2,5),(5,2)]),\n                   (11,[(1,11)]),\n                   (12,[(1,12),(2,6),(3,4),(4,3),(6,2)])])\n<\/pre>\n<ul>\n<li>(coste n) es el coste del \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo de divisibilidad de orden n. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n      coste 12    ==  41\n      coste 3000  ==  605305\n<\/pre>\n<h4>Soluciones<\/h4>\n<p>[schedule expon=&#8217;2017-05-18&#8242; expat=\u00bb06:00&#8243;]<\/p>\n<ul>\n<li>Las soluciones se pueden escribir en los comentarios hasta el 18 de mayo.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=\u00bbhaskell\u00bb&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<p>[\/schedule]<\/p>\n<p>[schedule on=&#8217;2017-05-18&#8242; at=\u00bb06:00&#8243;]<\/p>\n<pre lang=\"haskell\">\r\nimport Data.Ix\r\nimport Data.List (delete, sort)\r\nimport qualified Data.Set as S\r\nimport I1M.Grafo\r\nimport I1M.Tabla\r\n\r\ngrafoDivisibilidad :: Int -> Grafo Int Int\r\ngrafoDivisibilidad n =\r\n  creaGrafo ND (1,n) [(x,y,y `div` x) | y <- [1..n]\r\n                                      , x <- [1..y-1]\r\n                                      , y `mod` x == 0]\r\n\r\n\r\n-- 1\u00aa soluci\u00f3n (con el algoritmo de Kruskal)\r\n-- =========================================\r\n\r\ncoste1 :: Int -> Int\r\ncoste1 n = sum [p | (p,x,y) <- kruskal (grafoDivisibilidad n)]\r\n\r\n-- (kruskal g) es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo g calculado\r\n-- mediante el algoritmo de Kruskal. Por ejemplo,\r\n--    \u03bb> kruskal (grafoDivisibilidad 12)\r\n--    [(11,1,11),(7,1,7),(5,1,5),(3,3,9),(3,1,3),(2,6,12),(2,5,10),\r\n--     (2,4,8),(2,3,6),(2,2,4),(2,1,2)]\r\nkruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\r\nkruskal g = kruskal' cola                           -- Cola ordenada\r\n                     (tabla [(x,x) | x <- nodos g]) -- Tabla de raices\r\n                     []                             -- \u00c1rbol de expansi\u00f3n\r\n                     ((length (nodos g)) - 1)       -- Aristas por\r\n                                                    -- colocar\r\n    where cola = sort [(p,x,y) | (x,y,p) <- aristas g]\r\n\r\nkruskal' ((p,x,y):as) t ae n \r\n  | n==0        = ae\r\n  | actualizado = kruskal' as t' ((p,x,y):ae) (n-1)\r\n  | otherwise   = kruskal' as t  ae           n\r\n  where (actualizado,t') = buscaActualiza (x,y) t\r\n\r\n-- (raiz t n) es la ra\u00edz de n en la tabla t. Por ejemplo,\r\n--    raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5  == 1\r\n--    raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2  == 6\r\nraiz:: Eq n => Tabla n n -> n -> n\r\nraiz t x | v == x    = v\r\n         | otherwise = raiz t v\r\n         where v = valor t x\r\n\r\n-- (buscaActualiza a t) es el par formado por False y la tabla t, si los\r\n-- dos v\u00e9rtices de la arista a tienen la misma ra\u00edz en t y el par\r\n-- formado por True y la tabla obtenida a\u00f1adi\u00e9ndole a t la arista\r\n-- formada por el v\u00e9rtice de a de mayor ra\u00edz y la ra\u00edz del v\u00e9rtice de\r\n-- a de menor ra\u00edz. Por ejemplo,\r\n--    ghci> let t = crea [(1,1),(2,2),(3,1),(4,1)]\r\n--    ghci> buscaActualiza (2,3) t\r\n--    (True,Tbl [(1,1),(2,1),(3,1),(4,1)])\r\n--    ghci> buscaActualiza (3,4) t\r\n--    (False,Tbl [(1,1),(2,2),(3,1),(4,1)])\r\nbuscaActualiza :: (Eq n, Ord n) => (n,n) -> Tabla n n -> (Bool,Tabla n n)\r\nbuscaActualiza (x,y) t \r\n  | x' == y'  = (False, t) \r\n  | y' <  x'  = (True, modifica (x,y') t)\r\n  | otherwise = (True, modifica (y,x') t)\r\n  where x' = raiz t x \r\n        y' = raiz t y\r\n\r\n-- 2\u00aa soluci\u00f3n (con el algoritmo de Prim)\r\n-- ======================================\r\n\r\ncoste2 :: Int -> Int\r\ncoste2 n = sum [p | (p,x,y) <- prim (grafoDivisibilidad n)]\r\n\r\n-- (prim g) es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo g calculado\r\n-- mediante el algoritmo de Prim. Por ejemplo,\r\n--    \u03bb> prim (grafoDivisibilidad 12)\r\n--    [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6),\r\n--     (3,1,3),(2,4,8),(2,2,4),(2,1,2)]\r\nprim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\r\nprim g = prim' [n]              -- Nodos colocados\r\n               ns               -- Nodos por colocar \r\n               []               -- \u00c1rbol de expansi\u00f3n\r\n               (aristas g)      -- Aristas del grafo\r\n         where (n:ns) = nodos g\r\n\r\nprim' t [] ae as = ae\r\nprim' t r  ae as = prim' (v':t) (delete v' r) (e:ae) as\r\n  where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,\r\n                                         elem u t, \r\n                                         elem v r]\r\n\r\n-- 3\u00aa soluci\u00f3n (con el algoritmo de Prim con conjuntos)\r\n-- ====================================================\r\n\r\ncoste3 :: Int -> Int\r\ncoste3 n = sum [p | (p,x,y) <- prim2 (grafoDivisibilidad n)]\r\n\r\n-- (prim2 g) es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo g calculado\r\n-- mediante el algoritmo de Prim. Por ejemplo,\r\n--    \u03bb> prim2 (grafoDivisibilidad 12)\r\n--    [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6),\r\n--     (3,1,3),(2,4,8),(2,2,4),(2,1,2)]\r\nprim2 :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\r\nprim2 g = prim2' (S.singleton n)  -- Nodos colocados\r\n                 (S.fromList ns)  -- Nodos por colocar \r\n                 []               -- \u00c1rbol de expansi\u00f3n\r\n                 (aristas g)      -- Aristas del grafo\r\n  where (n:ns) = nodos g\r\n\r\nprim2' t r ae as\r\n  | S.null r  = ae\r\n  | otherwise = prim2' (S.insert v' t)\r\n                       (S.delete v' r)\r\n                       (e:ae)\r\n                       as\r\n  where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as,\r\n                                         S.member u t, \r\n                                         S.member v r]\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n--    \u03bb> coste1 400\r\n--    14923\r\n--    (0.08 secs, 31,336,440 bytes)\r\n--    \u03bb> coste2 400\r\n--    14923\r\n--    (4.54 secs, 220,745,608 bytes)\r\n--    \u03bb> coste3 400\r\n--    14923\r\n--    (0.69 secs, 217,031,144 bytes)\r\n<\/pre>\n<p>[\/schedule]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>El grafo de divisibilidad de orden n es el grafo cuyos nodos son los n\u00fameros naturales entre 1 y n, cuyas aristas son los pares (x,y) tales que x divide a y o y divide a x y el coste de cada arista es el cociente entre su mayos y menor elemento. Definir las siguientes&#8230;<\/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":[498,506,453,517],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3297"}],"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=3297"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3297\/revisions"}],"predecessor-version":[{"id":3299,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3297\/revisions\/3299"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3297"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3297"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}