{"id":8214,"date":"2023-06-19T06:00:59","date_gmt":"2023-06-19T04:00:59","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8214"},"modified":"2023-06-12T12:54:23","modified_gmt":"2023-06-12T10:54:23","slug":"19-jun-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/19-jun-23\/","title":{"rendered":"TAD de los grafos: Coloreado correcto de un mapa"},"content":{"rendered":"

Un mapa se puede representar mediante un grafo donde los v\u00e9rtices son las regiones del mapa y hay una arista entre dos v\u00e9rtices si las correspondientes regiones son vecinas. Por ejemplo, el mapa siguiente<\/p>\n

\n   +----------+----------+\n   |    1     |     2    |\n   +----+-----+-----+----+\n   |    |           |    |\n   | 3  |     4     | 5  |\n   |    |           |    |\n   +----+-----+-----+----+\n   |    6     |     7    |\n   +----------+----------+\n<\/pre>\n
se pueden representar por<\/p>\n
\n   mapa :: Grafo Int Int\n   mapa = creaGrafo' ND (1,7)\n                     [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),\n                      (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)]\n<\/pre>\n
Para colorear el mapa se dispone de 4 colores definidos por<\/p>\n
\n   data Color = A | B | C | D\n     deriving (Eq, Show)\n<\/pre>\n
Usando el tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n
\n   correcta :: [(Int,Color)] -> Grafo Int Int -> Bool\n<\/pre>\n
tal que correcta ncs m<\/code> se verifica si ncs<\/code> es una coloraci\u00f3n del mapa m<\/code> tal que todos las regiones vecinas tienen colores distintos. Por ejemplo,<\/p>\n
\n   correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa == True\n   correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa == False\n<\/pre>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nmodule Grafo_Coloreado_correcto_de_un_mapa where\n\nimport TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo')\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\nmapa :: Grafo Int Int\nmapa = creaGrafo' ND (1,7)\n                  [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),\n                   (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)]\n\ndata Color = A | B | C | E\n  deriving (Eq, Show)\n\ncorrecta :: [(Int,Color)] -> Grafo Int Int -> Bool\ncorrecta ncs g =\n  and [color x \/= color y | ((x,y),_) <- aristas g]\n  where color x = head [c | (y,c) <- ncs, y == x]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa `shouldBe` True\n  it \"e2\" $\n    correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa `shouldBe` False\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.0004 seconds\n--    2 examples, 0 failures\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom enum import Enum\n\nfrom src.TAD.Grafo import Grafo, Orientacion, aristas, creaGrafo_\n\nmapa: Grafo = creaGrafo_(Orientacion.ND,\n                         (1,7),\n                         [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),\n                          (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)])\n\nColor = Enum('Color', ['A', 'B', 'C', 'E'])\n\ndef correcta(ncs: list[tuple[int, Color]], g: Grafo) -> bool:\n    def color(x: int) -> Color:\n        return [c for (y, c) in ncs if y == x][0]\n    return all(color(x) != color(y) for ((x, y), _) in aristas(g))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_correcta() -> None:\n    assert correcta([(1,Color.A),\n                     (2,Color.B),\n                     (3,Color.B),\n                     (4,Color.C),\n                     (5,Color.A),\n                     (6,Color.A),\n                     (7,Color.B)],\n                    mapa)\n    assert not correcta([(1,Color.A),\n                         (2,Color.B),\n                         (3,Color.A),\n                         (4,Color.C),\n                         (5,Color.A),\n                         (6,Color.A),\n                         (7,Color.B)],\n                        mapa)\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_correcta()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Un mapa se puede representar mediante un grafo donde los v\u00e9rtices son las regiones del mapa y hay una arista entre dos v\u00e9rtices si las correspondientes regiones son vecinas. Por ejemplo, el mapa siguiente +———-+———-+ | 1 | 2 | +—-+—–+—–+—-+ | | | | | 3 | 4 | 5 | | | |…<\/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":[581],"tags":[453],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8214"}],"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=8214"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8214\/revisions"}],"predecessor-version":[{"id":8215,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8214\/revisions\/8215"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8214"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8214"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}