{"id":7952,"date":"2023-06-24T11:46:25","date_gmt":"2023-06-24T09:46:25","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7952"},"modified":"2023-06-24T11:46:25","modified_gmt":"2023-06-24T09:46:25","slug":"24-jun-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/24-jun-23\/","title":{"rendered":"La semana en Exercitium (24 de junio de 2023)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas sobre el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a><\/p>\n<ul>\n<li><a href=\"#ej1\">1. Coloreado correcto de un mapa<\/a><\/li>\n<li><a href=\"#ej2\">2. Nodos aislados de un grafo<\/a><\/li>\n<li><a href=\"#ej3\">3. Nodos conectados en un grafo<\/a><\/li>\n<li><a href=\"#ej4\">4. Algoritmo de Kruskal<\/a><\/li>\n<li><a href=\"#ej5\">5. Algoritmo de Prim<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. Coloreado correcto de un mapa<\/h3>\n<p>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<pre lang=\"text\">\n   +----------+----------+\n   |    1     |     2    |\n   +----+-----+-----+----+\n   |    |           |    |\n   | 3  |     4     | 5  |\n   |    |           |    |\n   +----+-----+-----+----+\n   |    6     |     7    |\n   +----------+----------+\n<\/pre>\n<p>se pueden representar por<\/p>\n<pre lang=\"text\">\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<p>Para colorear el mapa se dispone de 4 colores definidos por<\/p>\n<pre lang=\"text\">\n   data Color = A | B | C | D\n     deriving (Eq, Show)\n<\/pre>\n<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n<pre lang=\"text\">\n   correcta :: [(Int,Color)] -> Grafo Int Int -> Bool\n<\/pre>\n<p>tal que <code>correcta ncs m<\/code> se verifica si <code>ncs<\/code> es una coloraci\u00f3n del mapa <code>m<\/code> tal que todos las regiones vecinas tienen colores distintos. Por ejemplo,<\/p>\n<pre lang=\"text\">\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<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\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<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\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<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Nodos aislados de un grafo<\/h3>\n<p>Dado un grafo dirigido G, diremos que un nodo est\u00e1 aislado si o bien de dicho nodo no sale ninguna arista o bien no llega al nodo ninguna arista. Por ejemplo, en el siguiente grafo<\/p>\n<pre lang=\"text\">\n   grafo1 :: Grafo Int Int\n   grafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),\n                                (5,4),(6,2),(6,5)]\n<\/pre>\n<p>podemos ver que del nodo 1 salen 3 aristas pero no llega ninguna, por lo que lo consideramos aislado. As\u00ed mismo, a los nodos 2 y 4 llegan aristas pero no sale ninguna, por tanto tambi\u00e9n estar\u00e1n aislados.<\/p>\n<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n<pre lang=\"text\">\n   aislados :: (Ix v, Num p) => Grafo v p -> [v]\n<\/pre>\n<p>tal que <code>aislados g<\/code> es la lista de nodos aislados del grafo <code>g<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   aislados grafo1 == [1,2,4]\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Grafo_Nodos_aislados_de_un_grafo where\n\nimport TAD.Grafo (Grafo, Orientacion (D), adyacentes, nodos, creaGrafo')\nimport Data.Ix (Ix)\nimport Grafo_Incidentes_de_un_vertice (incidentes)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ngrafo1 :: Grafo Int Int\ngrafo1 = creaGrafo' D (1,6) [(1,2),(1,3),(1,4),(3,6),\n                             (5,4),(6,2),(6,5)]\n\naislados :: (Ix v, Num p) => Grafo v p -> [v]\naislados g =\n  [n | n <- nodos g, null (adyacentes g n) || null (incidentes g n)]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    aislados grafo1 `shouldBe` [1,2,4]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--\n--    Finished in 0.0008 seconds\n--    1 example, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.Grafo_Incidentes_de_un_vertice import incidentes\nfrom src.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, creaGrafo_,\n                           nodos)\n\ngrafo1: Grafo = creaGrafo_(Orientacion.D,\n                           (1,6),\n                           [(1,2),(1,3),(1,4),(3,6),(5,4),(6,2),(6,5)])\n\ndef aislados(g: Grafo) -> list[Vertice]:\n    return [n for n in nodos(g)\n            if not adyacentes(g, n) or not incidentes(g, n)]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_aislados() -> None:\n    assert aislados(grafo1) == [1, 2, 4]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_aislados()\n#    Verificado\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Nodos conectados en un grafo<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n<pre lang=\"text\">\n   conectados :: Grafo Int Int -> Int -> Int -> Bool\n<\/pre>\n<p>tal que <code>conectados g v1 v2<\/code> se verifica si los v\u00e9rtices <code>v1<\/code> y <code>v2<\/code> est\u00e1n conectados en el grafo <code>g<\/code>. Por ejemplo, si grafo1 es el grafo definido por<\/p>\n<pre lang=\"text\">\n   grafo1 :: Grafo Int Int\n   grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50),\n                                (2,4),(2,6),(4,6),(4,4),(6,4)]\n<\/pre>\n<p>entonces,<\/p>\n<pre lang=\"text\">\n   conectados grafo1 1 3  ==  True\n   conectados grafo1 1 4  ==  False\n   conectados grafo1 6 2  ==  False\n   conectados grafo1 3 1  ==  True\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Grafo_Nodos_conectados_en_un_grafo where\n\nimport TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo')\nimport Data.List (union)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\nconectados :: Grafo Int Int -> Int -> Int -> Bool\nconectados g v1 v2 = v2 `elem` conectadosAux g [] [v1]\n\nconectadosAux :: Grafo Int Int -> [Int] -> [Int] -> [Int]\nconectadosAux _ vs [] = vs\nconectadosAux g vs (w:ws)\n  | w `elem` vs = conectadosAux g vs ws\n  | otherwise = conectadosAux g ([w] `union` vs) (ws `union` adyacentes g w)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    conectados grafo1 1 3  `shouldBe`  True\n  it \"e2\" $\n    conectados grafo1 1 4  `shouldBe`  False\n  it \"e3\" $\n    conectados grafo1 6 2  `shouldBe`  False\n  it \"e4\" $\n    conectados grafo1 3 1  `shouldBe`  True\n  it \"e5\" $\n    conectados grafo2 1 3  `shouldBe`  True\n  it \"e6\" $\n    conectados grafo2 1 4  `shouldBe`  False\n  it \"e7\" $\n    conectados grafo2 6 2  `shouldBe`  True\n  it \"e8\" $\n    conectados grafo2 3 1  `shouldBe`  True\n  where\n    grafo1, grafo2 :: Grafo Int Int\n    grafo1 = creaGrafo' D (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50),\n                                 (2,4),(2,6),(4,6),(4,4),(6,4)]\n\n    grafo2 = creaGrafo' ND (1,6) [(1,3),(1,5),(3,5),(5,1),(5,50),\n                                  (2,4),(2,6),(4,6),(4,4),(6,4)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--    e5\n--    e6\n--    e7\n--    e8\n--\n--    Finished in 0.0032 seconds\n--    8 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_\n\n\ndef unionV(xs: list[Vertice], ys: list[Vertice]) -> list[Vertice]:\n    return list(set(xs) | set(ys))\n\ndef conectadosAux(g: Grafo, vs: list[Vertice], ws: list[Vertice]) -> list[Vertice]:\n    if not ws:\n        return vs\n    w, *ws = ws\n    if w in vs:\n        return conectadosAux(g, vs, ws)\n    return conectadosAux(g, unionV([w], vs), unionV(ws, adyacentes(g, w)))\n\ndef conectados(g: Grafo, v1: Vertice, v2: Vertice) -> bool:\n    return v2 in conectadosAux(g, [], [v1])\n\n\n# Verificaci\u00f3n\n# ============\n\ndef test_conectados() -> None:\n    grafo1 = creaGrafo_(Orientacion.D,\n                        (1,6),\n                        [(1,3),(1,5),(3,5),(5,1),(5,50),\n                         (2,4),(2,6),(4,6),(4,4),(6,4)])\n    grafo2 = creaGrafo_(Orientacion.ND,\n                        (1,6),\n                        [(1,3),(1,5),(3,5),(5,1),(5,50),\n                         (2,4),(2,6),(4,6),(4,4),(6,4)])\n    assert conectados(grafo1, 1, 3)\n    assert not conectados(grafo1, 1, 4)\n    assert not conectados(grafo1, 6, 2)\n    assert conectados(grafo1, 3, 1)\n    assert conectados(grafo2, 1, 3)\n    assert not conectados(grafo2, 1, 4)\n    assert conectados(grafo2, 6, 2)\n    assert conectados(grafo2, 3, 1)\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_conectados()\n#    Verificado\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Algoritmo de Kruskal<\/h3>\n<p>El <a href=\"https:\/\/bit.ly\/3N8bOOg\">algoritmo de Kruskal<\/a> calcula un \u00e1rbol recubridor m\u00ednimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un \u00e1rbol, incluyen todos los v\u00e9rtices y donde el valor de la suma de todas las aristas del \u00e1rbol es el m\u00ednimo.<\/p>\n<p>El algoritmo de Kruskal funciona de la siguiente manera:<\/p>\n<ul>\n<li>se crea un bosque B (un conjunto de \u00e1rboles), donde cada v\u00e9rtice del grafo es un \u00e1rbol separado<\/li>\n<li>se crea un conjunto C que contenga a todas las aristas del grafo<\/li>\n<li>mientras C es no vac\u00edo,\n<ul>\n<li>eliminar una arista de peso m\u00ednimo de C<\/li>\n<li>si esa arista conecta dos \u00e1rboles diferentes se a\u00f1ade al bosque, combinando los dos \u00e1rboles en un solo \u00e1rbol<\/li>\n<li>en caso contrario, se desecha la arista<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo.<\/p>\n<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n<pre lang=\"text\">\n   kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\n<\/pre>\n<p>tal que <code>kruskal g<\/code> es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo <code>g<\/code> calculado mediante el algoritmo de Kruskal. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por<\/p>\n<pre lang=\"text\">\n   g1, g2, g3, g4 :: Grafo Int Int\n   g1 = 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)]\n   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                            (2,4,12),(2,5,32),\n                            (3,4,14),(3,5,44),\n                            (4,5,93)]\n   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                            (2,3,7),\n                            (3,4,8),(3,5,7),\n                            (4,5,5),\n                            (5,6,3),(5,7,9),\n                            (6,7,11)]\n   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                            (2,3,7),\n                            (3,4,8),(3,5,1),\n                            (4,5,5),\n                            (5,6,3),(5,7,9),\n                            (6,7,11)]\n<\/pre>\n<p>entonces<\/p>\n<pre lang=\"text\">\n   kruskal g1  ==  [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n   kruskal g2  ==  [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]\n   kruskal g3  ==  [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]\n   kruskal g4  ==  [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Grafo_Algoritmo_de_Kruskal where\n\nimport TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo, nodos)\nimport Data.Ix (Ix)\nimport qualified Data.Map as M (Map, (!), fromList, keys, update)\nimport Data.List (sort)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ng1, g2, g3, g4 :: 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 ND (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                         (2,4,12),(2,5,32),\n                         (3,4,14),(3,5,44),\n                         (4,5,93)]\ng3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                         (2,3,7),\n                         (3,4,8),(3,5,7),\n                         (4,5,5),\n                         (5,6,3),(5,7,9),\n                         (6,7,11)]\ng4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                         (2,3,7),\n                         (3,4,8),(3,5,1),\n                         (4,5,5),\n                         (5,6,3),(5,7,9),\n                         (6,7,11)]\n\nkruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\nkruskal g = aux (sort [(p,x,y) | ((x,y),p) <- aristas g])\n                (M.fromList [(x,x) | x <- nodos g])\n                []\n                (length (nodos g) - 1)\n  where aux _  _ ae 0 = ae\n        aux [] _ _  _ = error \"Imposible\"\n        aux ((p,x,y):as) d ae n\n          | actualizado = aux as d' ((p,x,y):ae) (n-1)\n          | otherwise   = aux as d ae n\n          where (actualizado,d') = buscaActualiza (x,y) d\n\n-- (raiz d n) es la ra\u00edz de n en el diccionario. Por ejemplo,\n--    raiz (M.fromList [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5  == 1\n--    raiz (M.fromList [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2  == 6\nraiz :: (Eq n, Ord n) => M.Map n n -> n -> n\nraiz d x | v == x    = v\n         | otherwise = raiz d v\n  where v = d M.! x\n\n-- (buscaActualiza a d) es el par formado por False y el diccionario d,\n-- si los dos v\u00e9rtices de la arista a tienen la misma ra\u00edz en d y el par\n-- formado por True y la tabla obtenida a\u00f1adi\u00e9ndole a d la arista\n-- formada por el v\u00e9rtice de a de mayor ra\u00edz y la ra\u00edz del v\u00e9rtice de a\n-- de menor ra\u00edz. Y actualizando las raices de todos los elementos\n-- afectados por la ra\u00edz a\u00f1adida. Por ejemplo,\n--   \u03bb> d = M.fromList [(1,1),(2,1),(3,3),(4,4),(5,5),(6,5),(7,7)]\n--   \u03bb> buscaActualiza (5,4) d\n--   (True,fromList [(1,1),(2,1),(3,3),(4,4),(5,4),(6,4),(7,7)])\n--   \u03bb> d' = snd it\n--   \u03bb> buscaActualiza (6,1) d'\n--   (True,fromList [(1,1),(2,1),(3,3),(4,1),(5,1),(6,1),(7,7)])\nbuscaActualiza :: (Eq n, Ord n) => (n,n) -> M.Map n n -> (Bool,M.Map n n)\nbuscaActualiza (x,y) d\n  | x' == y'  = (False, d)\n  | y' <  x'  = (True, modificaR x (d M.! x) y' d)\n  | otherwise = (True, modificaR y (d M.! y) x' d)\n  where x' = raiz d x\n        y' = raiz d y\n\n-- (modificaR x y y' d) actualiza d como sigue:\n-- + el valor de todas las claves z con valor y es y'\n-- + el valor de todas las claves z con (z > x) con valor x es y'\nmodificaR :: (Eq n, Ord n) => n -> n -> n -> M.Map n n -> M.Map n n\nmodificaR x y y' d = aux2 ds (aux1 cs d)\n  where cs = M.keys d\n        ds = filter (>x) cs\n        aux1 [] tb = tb\n        aux1 (a:as) tb | tb M.! a == y = aux1 as (M.update (\\_ -> Just y') a tb)\n                       | otherwise     = aux1 as tb\n        aux2 [] tb = tb\n        aux2 (b:bs) tb | tb M.! b == x = aux2 bs (M.update (\\_ -> Just y') b tb)\n                       | otherwise     = aux2 bs tb\n\n-- Traza del diccionario correspondiente al grafo g3\n-- =================================================\n\n-- Lista de aristas, ordenadas seg\u00fan su peso:\n-- [(3,5,6),(5,1,2),(5,4,5),(6,1,6),(7,2,3),(7,3,5),(8,3,4),(9,1,3),(9,5,7),(11,6,7),(15,1,5)]\n--\n-- Inicial\n--   fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)]\n--\n-- Despu\u00e9s de a\u00f1adir la arista (5,6) de peso 3\n--   fromList [(1,1),(2,2),(3,3),(4,4),(5,5),(6,5),(7,7)]\n--\n-- Despu\u00e9s de a\u00f1adir la arista (1,2) de peso 5\n--   fromList [(1,1),(2,1),(3,3),(4,4),(5,5),(6,5),(7,7)]\n--\n-- Despu\u00e9s de a\u00f1adir la arista (4,5) de peso 5\n--   fromList [(1,1),(2,1),(3,3),(4,4),(5,4),(6,4),(7,7)]\n--\n-- Despu\u00e9s de a\u00f1adir la arista (1,6) de peso 6\n--   fromList [(1,1),(2,1),(3,3),(4,1),(5,1),(6,1),(7,7)]\n--\n-- Despu\u00e9s de a\u00f1adir la arista (2,3) de peso 7\n--   fromList [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,7)]\n--\n-- Las posibles aristas a a\u00f1adir son:\n-- + la (3,5) con peso 7, que no es posible pues la ra\u00edz de 3\n--   coincide con la ra\u00edz de 5, por lo que formar\u00eda un ciclo\n-- + la (3,4) con peso 8, que no es posible pues la ra\u00edz de 3\n--   coincide con la ra\u00edz de 4, por lo que formar\u00eda un ciclo\n-- + la (1,3) con peso 9, que no es posible pues la ra\u00edz de 3\n--   coincide con la ra\u00edz de 1, por lo que formar\u00eda un ciclo\n-- + la (5,7) con peso 9, que no forma ciclo\n--\n-- Despu\u00e9s de a\u00f1adir la arista (5,7) con peso 9\n--    fromList [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1)]\n--\n-- No es posible a\u00f1adir m\u00e1s aristas, pues formar\u00edan ciclos.\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    kruskal g1 `shouldBe` [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n  it \"e2\" $\n    kruskal g2 `shouldBe` [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]\n  it \"e3\" $\n    kruskal g3 `shouldBe` [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]\n  it \"e4\" $\n    kruskal g4 `shouldBe` [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--\n--    Finished in 0.0044 seconds\n--    4 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristas,\n                           creaGrafo, nodos)\n\ng1 = creaGrafo (Orientacion.ND,\n                (1,5),\n                [((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 (Orientacion.ND,\n                (1,5),\n                [((1,2),13),((1,3),11),((1,5),78),\n                 ((2,4),12),((2,5),32),\n                 ((3,4),14),((3,5),44),\n                 ((4,5),93)])\ng3 = creaGrafo (Orientacion.ND,\n                (1,7),\n                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),\n                 ((2,3),7),\n                 ((3,4),8),((3,5),7),\n                 ((4,5),5),\n                 ((5,6),3),((5,7),9),\n                 ((6,7),11)])\ng4 = creaGrafo (Orientacion.ND,\n                (1,7),\n                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),\n                 ((2,3),7),\n                 ((3,4),8),((3,5),1),\n                 ((4,5),5),\n                 ((5,6),3),((5,7),9),\n                 ((6,7),11)])\n\n# raiz(d, n) es la ra\u00edz de n en el diccionario. Por ejemplo,\n#    raiz({1:1, 3:1, 4:3, 5:4, 2:6, 6:6}, 5)  == 1\n#    raiz({1:1, 3:1, 4:3, 5:4, 2:6, 6:6}, 2)  == 6\ndef raiz(d: dict[Vertice, Vertice], x: Vertice) -> Vertice:\n    v = d[x]\n    if v == x:\n        return v\n    return raiz(d, v)\n\n# modificaR(x, y, y_, d) actualiza d como sigue:\n# + el valor de todas las claves z con valor y es y_\n# + el valor de todas las claves z con (z > x) con valor x es y_\ndef modificaR(x: Vertice,\n              y: Vertice,\n              y_: Vertice,\n              d: dict[Vertice, Vertice]) -> dict[Vertice, Vertice]:\n    def aux1(vs: list[Vertice],\n             tb: dict[Vertice, Vertice],\n             y: Vertice) -> dict[Vertice, Vertice]:\n        for a in vs:\n            if tb[a] == y:\n                tb[a] = y_\n        return tb\n\n    def aux2(vs: list[Vertice],\n             tb: dict[Vertice, Vertice],\n             y_: Vertice) -> dict[Vertice, Vertice]:\n        for b in vs:\n            if tb[b] == x:\n                tb[b] = y_\n        return tb\n\n    cs = list(d.keys())\n    ds = [c for c in cs if c > x]\n\n    tb = aux1(cs, d, y)\n    tb = aux2(ds, tb, y_)\n\n    return tb\n\n# buscaActualiza(a, d) es el par formado por False y el diccionario d,\n# si los dos v\u00e9rtices de la arista a tienen la misma ra\u00edz en d y el par\n# formado por True y la tabla obtenida a\u00f1adi\u00e9ndole a d la arista\n# formada por el v\u00e9rtice de a de mayor ra\u00edz y la ra\u00edz del v\u00e9rtice de a\n# de menor ra\u00edz. Y actualizando las raices de todos los elementos\n# afectados por la ra\u00edz a\u00f1adida. Por ejemplo,\n#    >>> buscaActualiza((5,4), {1:1, 2:1, 3:3, 4:4, 5:5, 6:5, 7:7})\n#    (True, {1: 1, 2: 1, 3: 3, 4: 4, 5: 4, 6: 4, 7: 7})\n#    >>> buscaActualiza((6,1), {1:1, 2:1, 3:3, 4:4, 5:4, 6:4, 7:7})\n#    (True, {1: 1, 2: 1, 3: 3, 4: 1, 5: 1, 6: 1, 7: 7})\n#    >>> buscaActualiza((6,2), {1:1, 2:1, 3:3, 4:1, 5:4, 6:5, 7:7})\n#    (False, {1: 1, 2: 1, 3: 3, 4: 1, 5: 4, 6: 5, 7: 7})\ndef buscaActualiza(a: tuple[Vertice, Vertice],\n                   d: dict[Vertice, Vertice]) -> tuple[bool,\n                                                       dict[Vertice, Vertice]]:\n    x, y = a\n    x_ = raiz(d, x)\n    y_ = raiz(d, y)\n\n    if x_ == y_:\n        return False, d\n    if y_ < x_:\n        return True, modificaR(x, d[x], y_, d)\n    return True, modificaR(y, d[y], x_, d)\n\ndef kruskal(g: Grafo) -> list[tuple[Peso, Vertice, Vertice]]:\n    def aux(as_: list[tuple[Peso, Vertice, Vertice]],\n            d: dict[Vertice, Vertice],\n            ae: list[tuple[Peso, Vertice, Vertice]],\n            n: int) -> list[tuple[Peso, Vertice, Vertice]]:\n        if n == 0:\n            return ae\n        p, x, y = as_[0]\n        actualizado, d = buscaActualiza((x, y), d)\n        if actualizado:\n            return aux(as_[1:], d, [(p, x, y)] + ae, n - 1)\n        return aux(as_[1:], d, ae, n)\n    return aux(list(sorted([(p, x, y) for ((x, y), p) in aristas(g)])),\n               {x: x for x in nodos(g)},\n               [],\n               len(nodos(g)) - 1)\n\n# Traza del diccionario correspondiente al grafo g3\n# =================================================\n\n# Lista de aristas, ordenadas seg\u00fan su peso:\n# [(3,5,6),(5,1,2),(5,4,5),(6,1,6),(7,2,3),(7,3,5),(8,3,4),(9,1,3),(9,5,7),(11,6,7),(15,1,5)]\n#\n# Inicial\n#   {1:1, 2:2, 3:3, 4:4, 5:5, 6:6, 7:7}\n#\n# Despu\u00e9s de a\u00f1adir la arista (5,6) de peso 3\n#   {1:1, 2:2, 3:3, 4:4, 5:5, 6:5, 7:7}\n#\n# Despu\u00e9s de a\u00f1adir la arista (1,2) de peso 5\n#   {1:1, 2:1, 3:3, 4:4, 5:5, 6:5, 7:7}\n#\n# Despu\u00e9s de a\u00f1adir la arista (4,5) de peso 5\n#   {1:1, 2:1, 3:3, 4:4, 5:4, 6:4, 7:7}\n#\n# Despu\u00e9s de a\u00f1adir la arista (1,6) de peso 6\n#   {1:1, 2:1, 3:3, 4:1, 5:1, 6:1, 7:7}\n#\n# Despu\u00e9s de a\u00f1adir la arista (2,3) de peso 7\n#   {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:7}\n#\n# Las posibles aristas a a\u00f1adir son:\n# + la (3,5) con peso 7, que no es posible pues la ra\u00edz de 3\n#   coincide con la ra\u00edz de 5, por lo que formar\u00eda un ciclo\n# + la (3,4) con peso 8, que no es posible pues la ra\u00edz de 3\n#   coincide con la ra\u00edz de 4, por lo que formar\u00eda un ciclo\n# + la (1,3) con peso 9, que no es posible pues la ra\u00edz de 3\n#   coincide con la ra\u00edz de 1, por lo que formar\u00eda un ciclo\n# + la (5,7) con peso 9, que no forma ciclo\n#\n# Despu\u00e9s de a\u00f1adir la arista (5,7) con peso 9\n#    {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1}\n#\n# No es posible a\u00f1adir m\u00e1s aristas, pues formar\u00edan ciclos.\n\n# Verificaci\u00f3n\n# ============\n\ndef test_kruskal() -> None:\n    assert kruskal(g1) == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n    assert kruskal(g2) == [(32,2,5),(13,1,2),(12,2,4),(11,1,3)]\n    assert kruskal(g3) == [(9,5,7),(7,2,3),(6,1,6),(5,4,5),(5,1,2),(3,5,6)]\n    assert kruskal(g4) == [(9,5,7),(6,1,6),(5,4,5),(5,1,2),(3,5,6),(1,3,5)]\n    print(\"Vefificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_kruskal()\n#    Vefificado\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Algoritmo de Prim<\/h3>\n<p>El <a href=\"https:\/\/bit.ly\/466fwRe\">algoritmo de Prim<\/a> calcula un \u00e1rbol recubridor m\u00ednimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un \u00e1rbol, incluyen todos los v\u00e9rtices y donde el valor de la suma de todas las aristas del \u00e1rbol es el m\u00ednimo.<\/p>\n<p>El algoritmo de Prim funciona de la siguiente manera:<\/p>\n<ul>\n<li>Inicializar un \u00e1rbol con un \u00fanico v\u00e9rtice, elegido arbitrariamente, del grafo.<\/li>\n<li>Aumentar el \u00e1rbol por un lado. Llamamos lado a la uni\u00f3n entre dos v\u00e9rtices: de las posibles uniones que pueden conectar el \u00e1rbol a los v\u00e9rtices que no est\u00e1n a\u00fan en el \u00e1rbol, encontrar el lado de menor distancia y unirlo al \u00e1rbol.<\/li>\n<li>Repetir el paso 2 (hasta que todos los v\u00e9rtices pertenezcan al \u00e1rbol)<\/li>\n<\/ul>\n<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a>, definir la funci\u00f3n,<\/p>\n<pre lang=\"text\">\n   prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\n<\/pre>\n<p>tal que <code>prim g<\/code> es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo <code>g<\/code> calculado mediante el algoritmo de Prim. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por<\/p>\n<pre lang=\"text\">\n   g1, g2, g3, g4 :: Grafo Int Int\n   g1 = 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)]\n   g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                            (2,4,12),(2,5,32),\n                            (3,4,14),(3,5,44),\n                            (4,5,93)]\n   g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                            (2,3,7),\n                            (3,4,8),(3,5,7),\n                            (4,5,5),\n                            (5,6,3),(5,7,9),\n                            (6,7,11)]\n   g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                            (2,3,7),\n                            (3,4,8),(3,5,1),\n                            (4,5,5),\n                            (5,6,3),(5,7,9),\n                            (6,7,11)]\n<\/pre>\n<p>entonces<\/p>\n<pre lang=\"text\">\n   prim g1  == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n   prim g2  == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]\n   prim g3  == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Grafo_Algoritmo_de_Prim where\n\nimport TAD.Grafo (Grafo, Orientacion (ND), aristas, creaGrafo, nodos)\nimport Data.Ix (Ix)\nimport Data.List (delete)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ng1, g2, g3, g4 :: 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 ND (1,5) [(1,2,13),(1,3,11),(1,5,78),\n                         (2,4,12),(2,5,32),\n                         (3,4,14),(3,5,44),\n                         (4,5,93)]\ng3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                         (2,3,7),\n                         (3,4,8),(3,5,7),\n                         (4,5,5),\n                         (5,6,3),(5,7,9),\n                         (6,7,11)]\ng4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6),\n                         (2,3,7),\n                         (3,4,8),(3,5,1),\n                         (4,5,5),\n                         (5,6,3),(5,7,9),\n                         (6,7,11)]\n\nprim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)]\nprim g = prim' [n]              -- Nodos colocados\n               ns               -- Nodos por colocar\n               []               -- \u00c1rbol de expansi\u00f3n\n               (aristas g)      -- Aristas del grafo\n  where\n    (n:ns) = nodos g\n    prim' _ _ _  []  = []\n    prim' _ [] ae _  = ae\n    prim' t r  ae as = prim' (v':t) (delete v' r) (e:ae) as\n      where e@(_,_, v') = minimum [(c,u,v)| ((u,v),c) <- as,\n                                             u `elem` t,\n                                             v `elem` r]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    prim g1 `shouldBe` [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n  it \"e2\" $\n    prim g2 `shouldBe` [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]\n  it \"e3\" $\n    prim g3 `shouldBe` [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--\n--    Finished in 0.0026 seconds\n--    3 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristas,\n                           creaGrafo, nodos)\n\ng1 = creaGrafo (Orientacion.ND,\n                (1,5),\n                [((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 (Orientacion.ND,\n                (1,5),\n                [((1,2),13),((1,3),11),((1,5),78),\n                 ((2,4),12),((2,5),32),\n                 ((3,4),14),((3,5),44),\n                 ((4,5),93)])\ng3 = creaGrafo (Orientacion.ND,\n                (1,7),\n                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),\n                 ((2,3),7),\n                 ((3,4),8),((3,5),7),\n                 ((4,5),5),\n                 ((5,6),3),((5,7),9),\n                 ((6,7),11)])\ng4 = creaGrafo (Orientacion.ND,\n                (1,7),\n                [((1,2),5),((1,3),9),((1,5),15),((1,6),6),\n                 ((2,3),7),\n                 ((3,4),8),((3,5),1),\n                 ((4,5),5),\n                 ((5,6),3),((5,7),9),\n                 ((6,7),11)])\n\ndef prim(g: Grafo) -> list[tuple[Peso, Vertice, Vertice]]:\n    n, *ns = nodos(g)\n    def prim_(t: list[Vertice],\n              r: list[Vertice],\n              ae: list[tuple[Peso, Vertice, Vertice]],\n              as_: list[tuple[tuple[Vertice, Vertice], Peso]]) \\\n              -> list[tuple[Peso, Vertice, Vertice]]:\n        if not as_:\n            return []\n        if not r:\n            return ae\n        e = min(((c,u,v)\n                 for ((u,v),c) in as_\n                 if u in t and v in r))\n        (_,_, v_) = e\n        return prim_([v_] + t, [x for x in r if x != v_], [e] + ae, as_)\n    return prim_([n], ns, [], aristas(g))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_prim() -> None:\n    assert prim(g1)  == [(55,2,4),(34,1,3),(32,2,5),(12,1,2)]\n    assert prim(g2)  == [(32,2,5),(12,2,4),(13,1,2),(11,1,3)]\n    assert prim(g3)  == [(9,5,7),(7,2,3),(5,5,4),(3,6,5),(6,1,6),(5,1,2)]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_prim()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas sobre el tipo abstracto de datos de los grafos 1. Coloreado correcto de un mapa 2. Nodos aislados de un grafo 3. Nodos conectados en un grafo 4. Algoritmo de Kruskal 5. Algoritmo de Prim A continuaci\u00f3n se muestran las soluciones.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[337],"tags":[],"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\/7952"}],"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=7952"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7952\/revisions"}],"predecessor-version":[{"id":7953,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7952\/revisions\/7953"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7952"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7952"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7952"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}