TAD de los grafos: Coloreado correcto de un mapa
Un mapa se puede representar mediante un grafo donde los vértices son las regiones del mapa y hay una arista entre dos vértices si las correspondientes regiones son vecinas. Por ejemplo, el mapa siguiente
|
1 2 3 4 5 6 7 8 9 |
+----------+----------+ | 1 | 2 | +----+-----+-----+----+ | | | | | 3 | 4 | 5 | | | | | +----+-----+-----+----+ | 6 | 7 | +----------+----------+ |
se pueden representar por
|
1 2 3 4 |
mapa :: Grafo Int Int mapa = creaGrafo' ND (1,7) [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4), (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)] |
Para colorear el mapa se dispone de 4 colores definidos por
|
1 2 |
data Color = A | B | C | D deriving (Eq, Show) |
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
correcta :: [(Int,Color)] -> Grafo Int Int -> Bool |
tal que correcta ncs m se verifica si ncs es una coloración del mapa m tal que todos las regiones vecinas tienen colores distintos. Por ejemplo,
|
1 2 |
correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa == True correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
module Grafo_Coloreado_correcto_de_un_mapa where import TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo') import Test.Hspec (Spec, hspec, it, shouldBe) mapa :: Grafo Int Int mapa = creaGrafo' ND (1,7) [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4), (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)] data Color = A | B | C | E deriving (Eq, Show) correcta :: [(Int,Color)] -> Grafo Int Int -> Bool correcta ncs g = and [color x /= color y | ((x,y),_) <- aristas g] where color x = head [c | (y,c) <- ncs, y == x] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa `shouldBe` True it "e2" $ correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa `shouldBe` False -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0004 seconds -- 2 examples, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
from enum import Enum from src.TAD.Grafo import Grafo, Orientacion, aristas, creaGrafo_ mapa: Grafo = creaGrafo_(Orientacion.ND, (1,7), [(1,2),(1,3),(1,4),(2,4),(2,5),(3,4), (3,6),(4,5),(4,6),(4,7),(5,7),(6,7)]) Color = Enum('Color', ['A', 'B', 'C', 'E']) def correcta(ncs: list[tuple[int, Color]], g: Grafo) -> bool: def color(x: int) -> Color: return [c for (y, c) in ncs if y == x][0] return all(color(x) != color(y) for ((x, y), _) in aristas(g)) # Verificación # ============ def test_correcta() -> None: assert correcta([(1,Color.A), (2,Color.B), (3,Color.B), (4,Color.C), (5,Color.A), (6,Color.A), (7,Color.B)], mapa) assert not correcta([(1,Color.A), (2,Color.B), (3,Color.A), (4,Color.C), (5,Color.A), (6,Color.A), (7,Color.B)], mapa) print("Verificado") # La verificación es # >>> test_correcta() # Verificado |