{"id":7947,"date":"2023-06-10T09:37:48","date_gmt":"2023-06-10T07:37:48","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7947"},"modified":"2023-06-10T09:37:48","modified_gmt":"2023-06-10T07:37:48","slug":"10-jun-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/10-jun-23\/","title":{"rendered":"La semana en Exercitium (10 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. Generadores de grafos<\/a><\/li>\n<li><a href=\"#ej2\">2. Grado de un v\u00e9rtice<\/a><\/li>\n<li><a href=\"#ej3\">3. Lema del apret\u00f3n de manos<\/a><\/li>\n<li><a href=\"#ej4\">4. Grafos regulares<\/a><\/li>\n<li><a href=\"#ej5\">5. Grafos k-regulares<\/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. Generadores de grafos<\/h3>\n<p>Definir un generador de grafos para comprobar propiedades de grafos con QuickCheck y hacer el tipo de los Grafos un subtipo de Arbitrary.<\/p>\n<p>Usando el generador, con QuickCheck que para cualquier grafo g, las sumas de los grados positivos y la de los grados negativos de los v\u00e9rtices de g son iguales.<\/p>\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<p>La definici\u00f3n del generador es<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE FlexibleInstances #-}\n{-# OPTIONS_GHC -fno-warn-orphans #-}\n\nmodule TAD.GrafoGenerador where\n\nimport TAD.Grafo (Grafo, Orientacion (D, ND), creaGrafo)\nimport Test.QuickCheck (Arbitrary, Gen, arbitrary, choose, vectorOf)\n\n-- (generaGND n ps) es el grafo completo de orden n tal que los pesos\n-- est\u00e1n determinados por ps. Por ejemplo,\n--    \u03bb> generaGND 3 [4,2,5]\n--    G ND ([1,2,3],[((1,2),4),((1,3),2),((2,3),5)])\n--    \u03bb> generaGND 3 [4,-2,5]\n--    G ND ([1,2,3],[((1,2),4),((2,3),5)])\ngeneraGND :: Int -> [Int] -> Grafo Int Int\ngeneraGND n ps  = creaGrafo ND (1,n) l3\n  where l1 = [(x,y) | x <- [1..n], y <- [1..n], x < y]\n        l2 = zip l1 ps\n        l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]\n\n-- (generaGD n ps) es el grafo completo de orden n tal que los pesos\n-- est\u00e1n determinados por ps. Por ejemplo,\n--    \u03bb> generaGD 3 [4,2,5]\n--    G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5)])\n--    \u03bb> generaGD 3 [4,2,5,3,7,9,8,6]\n--    G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5),\n--                  ((2,1),3),((2,2),7),((2,3),9),\n--                  ((3,1),8),((3,2),6)])\ngeneraGD :: Int -> [Int] -> Grafo Int Int\ngeneraGD n ps = creaGrafo D (1,n) l3\n  where l1 = [(x,y) | x <- [1..n], y <- [1..n]]\n        l2 = zip l1 ps\n        l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]\n\n-- genGD es un generador de grafos dirigidos. Por ejemplo,\n--    \u03bb> sample genGD\n--    G D ([1],[])\n--    G D ([1,2],[((1,1),5),((2,1),4)])\n--    G D ([1,2],[((1,1),3),((1,2),3)])\n--    G D ([1,2,3,4,5,6],[])\n--    G D ([1,2],[((2,2),16)])\n--    ...\ngenGD :: Gen (Grafo Int Int)\ngenGD = do\n  n <- choose (1,10)\n  xs <- vectorOf (n*n) arbitrary\n  return (generaGD n xs)\n\n-- genGND es un generador de grafos dirigidos. Por ejemplo,\n--    \u03bb> sample genGND\n--    G ND ([1,2,3,4,5,6,7,8],[])\n--    G ND ([1],[])\n--    G ND ([1,2,3,4,5],[((1,2),2),((2,3),5),((3,4),5),((3,5),5)])\n--    G ND ([1,2,3,4,5],[((1,2),6),((1,3),5),((1,5),1),((3,5),9),((4,5),6)])\n--    G ND ([1,2,3,4],[((1,2),5),((3,4),2)])\n--    G ND ([1,2,3],[])\n--    G ND ([1,2,3,4],[((1,2),5),((1,4),14),((2,4),10)])\n--    G ND ([1,2,3,4,5],[((1,5),8),((4,5),5)])\n--    G ND ([1,2,3,4],[((1,2),1),((1,4),4),((2,3),4),((3,4),5)])\n--    G ND ([1,2,3],[((1,2),8),((1,3),8),((2,3),3)])\n--    ...\ngenGND :: Gen (Grafo Int Int)\ngenGND = do\n  n <- choose (1,10)\n  xs <- vectorOf (n*n) arbitrary\n  return (generaGND n xs)\n\n-- genG es un generador de grafos. Por ejemplo,\n--    \u03bb> sample genG\n--    G ND ([1,2,3,4,5,6],[])\n--    G D ([1],[((1,1),2)])\n--    G D ([1,2],[((1,1),9)])\n--    ...\ngenG :: Gen (Grafo Int Int)\ngenG = do\n  d <- choose (True,False)\n  n <- choose (1,10)\n  xs <- vectorOf (n*n) arbitrary\n  if d then return (generaGD n xs)\n       else return (generaGND n xs)\n\n-- Los grafos est\u00e1 contenido en la clase de los objetos generables\n-- aleatoriamente.\ninstance Arbitrary (Grafo Int Int) where\n  arbitrary = genG\n<\/pre>\n<p>La comprobaci\u00f3n de la propiedad es<\/p>\n<pre lang=\"haskell\">\nmodule Grafo_Propiedades_de_grados_positivos_y_negativos where\n\nimport TAD.Grafo (Grafo, nodos)\nimport TAD.GrafoGenerador\nimport Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg)\nimport Test.QuickCheck\n\n-- La propiedad es\nprop_sumaGrados :: Grafo Int Int -> Bool\nprop_sumaGrados g =\n  sum [gradoPos g v | v <- vs] == sum [gradoNeg g v | v <- vs]\n  where vs = nodos g\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_sumaGrados\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<p>La definici\u00f3n del generador es<\/p>\n<pre lang=\"python\">\nfrom hypothesis import strategies as st\nfrom hypothesis.strategies import composite\n\nfrom src.TAD.Grafo import Orientacion, creaGrafo_\n\n\n# Generador de aristas. Por ejemplo,\n#    >>> gen_aristas(5).example()\n#    [(2, 5), (4, 5), (1, 2), (2, 3), (4, 1)]\n#    >>> gen_aristas(5).example()\n#    [(3, 4)]\n#    >>> gen_aristas(5).example()\n#    [(5, 3), (3, 2), (1, 3), (5, 2)]\n@composite\ndef gen_aristas(draw, n):\n    as_ = draw(st.lists(st.tuples(st.integers(1,n),\n                                  st.integers(1,n)),\n                        unique=True))\n    return as_\n\n# Generador de grafos no dirigidos. Por ejemplo,\n#    >>> gen_grafoND().example()\n#    G ND ([1, 2, 3, 4, 5], [(1, 4), (5, 5)])\n#    >>> gen_grafoND().example()\n#    G ND ([1], [])\n#    >>> gen_grafoND().example()\n#    G ND ([1, 2, 3, 4, 5, 6, 7, 8], [(7, 7)])\n#    >>> gen_grafoND().example()\n#    G ND ([1, 2, 3, 4, 5, 6], [(1, 3), (2, 4), (3, 3), (3, 5)])\n@composite\ndef gen_grafoND(draw):\n    n = draw(st.integers(1,10))\n    as_ = [(x, y) for (x, y ) in draw(gen_aristas(n)) if x <= y]\n    return creaGrafo_(Orientacion.ND, (1,n), as_)\n\n# Generador de grafos dirigidos. Por ejemplo,\n#    >>> gen_grafoD().example()\n#    G D ([1, 2, 3, 4], [(3, 3), (4, 1)])\n#    >>> gen_grafoD().example()\n#    G D ([1, 2], [(1, 1), (2, 1), (2, 2)])\n#    >>> gen_grafoD().example()\n#    G D ([1, 2], [])\n@composite\ndef gen_grafoD(draw):\n    n = draw(st.integers(1,10))\n    as_ = draw(gen_aristas(n))\n    return creaGrafo_(Orientacion.D, (1,n), as_)\n\n# Generador de grafos. Por ejemplo,\n#    >>> gen_grafo().example()\n#    G ND ([1, 2, 3, 4, 5, 6, 7], [(1, 3)])\n#    >>> gen_grafo().example()\n#    G D ([1], [])\n#    >>> gen_grafo().example()\n#    G D ([1, 2, 3, 4, 5, 6, 7], [(1, 3), (3, 4), (5, 5)])\n@composite\ndef gen_grafo(draw):\n    o = draw(st.sampled_from([Orientacion.D, Orientacion.ND]))\n    if o == Orientacion.ND:\n        return draw(gen_grafoND())\n    return draw(gen_grafoD())\n<\/pre>\n<p>La comprobaci\u00f3n de la propiedad es<\/p>\n<pre lang=\"python\">\nfrom hypothesis import given\n\nfrom src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos\nfrom src.TAD.Grafo import nodos\nfrom src.TAD.GrafoGenerador import gen_grafo\n\n\n# La propiedad es\n@given(gen_grafo())\ndef test_sumaGrados(g):\n    vs = nodos(g)\n    assert sum((gradoPos(g, v) for v in vs)) == sum((gradoNeg(g, v) for v in vs))\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q Grafo_Propiedades_de_grados_positivos_y_negativos.py\n#    1 passed in 0.31s\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Grado de un v\u00e9rtice<\/h3>\n<p>El <strong>grado<\/strong> de un v\u00e9rtice v de un grafo dirigido g, es el n\u00famero  aristas de g que contiene a v. Si g es no dirigido, el grado de un v\u00e9rtice v es el n\u00famero de aristas incidentes en v, teniendo en cuenta que los lazos se cuentan dos veces.<\/p>\n<p>Usando el <a href=\"https:\/\/bit.ly\/45cQ3Fo\">tipo abstracto de datos de los grafos<\/a>, definir las funciones,<\/p>\n<pre lang=\"text\">\n   grado :: (Ix v,Num p) => Grafo v p -> v -> Int\n<\/pre>\n<p>tal que <code>grado g v<\/code> es el grado del v\u00e9rtice <code>v<\/code> en el grafo <code>g<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]\n   g2 = creaGrafo' D  (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]\n   g3 = creaGrafo' D  (1,3) [(1,2),(2,2),(3,1),(3,2)]\n   g4 = creaGrafo' D  (1,1) [(1,1)]\n   g5 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)]\n   g6 = creaGrafo' D  (1,3) [(1,2),(1,3),(2,3),(3,3)]\n   grado g1 5 ==  4\n   grado g2 5 ==  3\n   grado g2 1 ==  3\n   grado g3 2 ==  4\n   grado g3 1 ==  2\n   grado g3 3 ==  2\n   grado g4 1 ==  2\n   grado g6 3 ==  4\n   grado g6 3 ==  4\n<\/pre>\n<p>Comprobar con QuickCheck que en todo grafo, el n\u00famero de nodos de grado impar es par.<\/p>\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_Grado_de_un_vertice where\n\nimport TAD.Grafo (Grafo, Orientacion (D, ND), dirigido, nodos, creaGrafo')\nimport Data.Ix (Ix)\nimport Grafo_Lazos_de_un_grafo (lazos)\nimport Grafo_Incidentes_de_un_vertice (incidentes)\nimport Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ngrado :: (Ix v,Num p) => Grafo v p -> v -> Int\ngrado g v | dirigido g           = gradoNeg g v + gradoPos g v\n          | (v,v) `elem` lazos g = length (incidentes g v) + 1\n          | otherwise            = length (incidentes g v)\n\n-- La propiedad es\nprop_numNodosGradoImpar :: Grafo Int Int -> Bool\nprop_numNodosGradoImpar g =\n  even (length [v | v <- nodos g, odd (grado g v)])\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_numNodosGradoImpar\n--    +++ OK, passed 100 tests.\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    grado g1 5 `shouldBe`  4\n  it \"e2\" $\n    grado g2 5 `shouldBe`  3\n  it \"e3\" $\n    grado g2 1 `shouldBe`  3\n  it \"e4\" $\n    grado g3 2 `shouldBe`  4\n  it \"e5\" $\n    grado g3 1 `shouldBe`  2\n  it \"e6\" $\n    grado g3 3 `shouldBe`  2\n  it \"e7\" $\n    grado g4 1 `shouldBe`  2\n  it \"e8\" $\n    grado g5 3 `shouldBe`  4\n  it \"e9\" $\n    grado g6 3 `shouldBe`  4\n  where\n    g1, g2, g3, g4, g5, g6 :: Grafo Int Int\n    g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]\n    g2 = creaGrafo' D  (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]\n    g3 = creaGrafo' D  (1,3) [(1,2),(2,2),(3,1),(3,2)]\n    g4 = creaGrafo' D  (1,1) [(1,1)]\n    g5 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)]\n    g6 = creaGrafo' D  (1,3) [(1,2),(1,3),(2,3),(3,3)]\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--    e9\n--\n--    Finished in 0.0015 seconds\n--    9 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom hypothesis import given\n\nfrom src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos\nfrom src.Grafo_Incidentes_de_un_vertice import incidentes\nfrom src.Grafo_Lazos_de_un_grafo import lazos\nfrom src.TAD.Grafo import (Grafo, Orientacion, Vertice, creaGrafo_, dirigido,\n                           nodos)\nfrom src.TAD.GrafoGenerador import gen_grafo\n\n\ndef grado(g: Grafo, v: Vertice) -> int:\n    if dirigido(g):\n        return gradoNeg(g, v) + gradoPos(g, v)\n    if (v, v) in lazos(g):\n        return len(incidentes(g, v)) + 1\n    return len(incidentes(g, v))\n\n# La propiedad esp\n@given(gen_grafo())\ndef test_grado1(g):\n    assert len([v for v in nodos(g) if grado(g, v) % 2 == 1]) % 2 == 0\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q Grafo_Grado_de_un_vertice.py\n#    1 passed in 0.36s\n\n# Verificaci\u00f3n\n# ============\n\ndef test_grado() -> None:\n    g1 = creaGrafo_(Orientacion.ND, (1,5),\n                    [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)])\n    g2 = creaGrafo_(Orientacion.D, (1,5),\n                    [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)])\n    g3 = creaGrafo_(Orientacion.D, (1,3),\n                    [(1,2),(2,2),(3,1),(3,2)])\n    g4 = creaGrafo_(Orientacion.D, (1,1),\n                    [(1,1)])\n    g5 = creaGrafo_(Orientacion.ND, (1,3),\n                    [(1,2),(1,3),(2,3),(3,3)])\n    g6 = creaGrafo_(Orientacion.D, (1,3),\n                    [(1,2),(1,3),(2,3),(3,3)])\n    assert grado(g1, 5) == 4\n    assert grado(g2, 5) == 3\n    assert grado(g2, 1) == 3\n    assert grado(g3, 2) == 4\n    assert grado(g3, 1) == 2\n    assert grado(g3, 3) == 2\n    assert grado(g4, 1) == 2\n    assert grado(g5, 3) == 4\n    assert grado(g6, 3) == 4\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_grado()\n#    Verificado\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Lema del apret\u00f3n de manos<\/h3>\n<p>En la teor\u00eda de grafos, se conoce como \"Lema del apret\u00f3n de manos\" la siguiente propiedad: la suma de los grados de los v\u00e9rtices de g es el doble del n\u00famero de aristas de g.<\/p>\n<p>Comprobar con QuickCheck que para cualquier grafo g, se verifica dicha propiedad.<\/p>\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\">\nimport TAD.Grafo (Grafo, nodos)\nimport TAD.GrafoGenerador\nimport Grafo_Grado_de_un_vertice (grado)\nimport Grafo_Numero_de_aristas_de_un_grafo (nAristas)\nimport Test.QuickCheck\n\nprop_apretonManos :: Grafo Int Int -> Bool\nprop_apretonManos g =\n  sum [grado g v | v <- nodos g] == 2 * nAristas g\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_apretonManos\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom hypothesis import given\n\nfrom src.Grafo_Grado_de_un_vertice import grado\nfrom src.Grafo_Numero_de_aristas_de_un_grafo import nAristas\nfrom src.TAD.Grafo import nodos\nfrom src.TAD.GrafoGenerador import gen_grafo\n\n\n# La propiedad es\n@given(gen_grafo())\ndef test_apreton(g):\n    assert sum((grado(g, v) for v in nodos(g))) == 2 * nAristas(g)\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q Grafo_Lema_del_apreton_de_manos.py\n#    1 passed in 0.32s\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Grafos regulares<\/h3>\n<p>Un <a href=\"https:\/\/bit.ly\/3C16Uxn\">grafo regular<\/a> es un grafo en el que todos sus v\u00e9rtices tienen el mismo grado.<\/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   regular :: (Ix v,Num p) => Grafo v p -> Bool\n<\/pre>\n<p>tal que (regular g) se verifica si el grafo g es regular. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> regular (creaGrafo' D (1,3) [(1,2),(2,3),(3,1)])\n   True\n   \u03bb> regular (creaGrafo' ND (1,3) [(1,2),(2,3)])\n   False\n   \u03bb> regular (completo 4)\n   True\n<\/pre>\n<p>Comprobar que los grafos completos son regulares.<\/p>\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_Grafos_regulares where\n\nimport TAD.Grafo (Grafo, Orientacion (D, ND), nodos, creaGrafo')\nimport Data.Ix (Ix)\nimport Grafo_Grado_de_un_vertice (grado)\nimport Grafo_Grafos_completos (completo)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\nregular :: (Ix v,Num p) => Grafo v p -> Bool\nregular g = and [grado g v == k | v <- vs]\n  where vs = nodos g\n        k  = grado g (head vs)\n\n-- La propiedad de la regularidad de todos los grafos completos de orden\n-- entre m y n es\nprop_CompletoRegular :: Int -> Int -> Bool\nprop_CompletoRegular m n =\n  and [regular (completo x) | x <- [m..n]]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> prop_CompletoRegular 1 30\n--    True\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    regular g1 `shouldBe` True\n  it \"e2\" $\n    regular g2 `shouldBe` False\n  it \"e3\" $\n    regular (completo 4) `shouldBe` True\n  where\n    g1, g2 :: Grafo Int Int\n    g1 = creaGrafo' D (1,3) [(1,2),(2,3),(3,1)]\n    g2 = creaGrafo' ND (1,3) [(1,2),(2,3)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--\n--    Finished in 0.0006 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.Grafo_Grado_de_un_vertice import grado\nfrom src.Grafo_Grafos_completos import completo\nfrom src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos\n\n\ndef regular(g: Grafo) -> bool:\n    vs = nodos(g)\n    k = grado(g, vs[0])\n    return all(grado(g, v) == k for v in vs)\n\n# La propiedad de la regularidad de todos los grafos completos de orden\n# entre m y n es\ndef prop_CompletoRegular(m: int, n: int) -> bool:\n    return all(regular(completo(x)) for x in range(m, n + 1))\n\n# La comprobaci\u00f3n es\n#    >>> prop_CompletoRegular(1, 30)\n#    True\n\n# Verificaci\u00f3n\n# ============\n\ndef test_regular() -> None:\n    g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,3),(3,1)])\n    g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,3)])\n    assert regular(g1)\n    assert not regular(g2)\n    assert regular(completo(4))\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_regular()\n#    Verificado\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Grafos k-regulares<\/h3>\n<p>Un <a href=\"https:\/\/bit.ly\/3C16Uxn\">grafo k-regular<\/a> es un grafo con todos sus v\u00e9rtices son de grado k.<\/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   regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int\n<\/pre>\n<p>tal que (regularidad g) es la regularidad de g. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   regularidad (creaGrafo' ND (1,2) [(1,2),(2,3)]) == Just 1\n   regularidad (creaGrafo' D (1,2) [(1,2),(2,3)])  == Nothing\n   regularidad (completo 4)                        == Just 3\n   regularidad (completo 5)                        == Just 4\n   regularidad (grafoCiclo 4)                      == Just 2\n   regularidad (grafoCiclo 5)                      == Just 2\n<\/pre>\n<p>Comprobar que el grafo completo de orden n es (n-1)-regular (para n de 1 a 20) y el grafo ciclo de orden n es 2-regular (para n de 3 a 20).<\/p>\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_Grafos_k_regulares where\n\nimport TAD.Grafo (Grafo, Orientacion (D, ND), nodos, creaGrafo')\nimport Data.Ix (Ix)\nimport Grafo_Grado_de_un_vertice (grado)\nimport Grafo_Grafos_regulares (regular)\nimport Grafo_Grafos_completos (completo)\nimport Grafo_Grafos_ciclos (grafoCiclo)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\nregularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int\nregularidad g\n  | regular g = Just (grado g (head (nodos g)))\n  | otherwise = Nothing\n\n-- La propiedad de k-regularidad de los grafos completos es\nprop_completoRegular :: Int -> Bool\nprop_completoRegular n =\n  regularidad (completo n) == Just (n-1)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> and [prop_completoRegular n | n <- [1..20]]\n--    True\n\n-- La propiedad de k-regularidad de los grafos ciclos es\nprop_cicloRegular :: Int -> Bool\nprop_cicloRegular n =\n  regularidad (grafoCiclo n) == Just 2\n\n-- La comprobaci\u00f3n es\n--    \u03bb> and [prop_cicloRegular n | n <- [3..20]]\n--    True\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    regularidad g1             `shouldBe` Just 1\n  it \"e2\" $\n    regularidad g2             `shouldBe` Nothing\n  it \"e3\" $\n    regularidad (completo 4)   `shouldBe` Just 3\n  it \"e4\" $\n    regularidad (completo 5)   `shouldBe` Just 4\n  it \"e5\" $\n    regularidad (grafoCiclo 4) `shouldBe` Just 2\n  it \"e6\" $\n    regularidad (grafoCiclo 5) `shouldBe` Just 2\n  where\n    g1, g2 :: Grafo Int Int\n    g1 = creaGrafo' ND (1,2) [(1,2),(2,3)]\n    g2 = creaGrafo' D (1,2) [(1,2),(2,3)]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--    e5\n--    e6\n--\n--    Finished in 0.0027 seconds\n--    6 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import Optional\n\nfrom src.Grafo_Grado_de_un_vertice import grado\nfrom src.Grafo_Grafos_ciclos import grafoCiclo\nfrom src.Grafo_Grafos_completos import completo\nfrom src.Grafo_Grafos_regulares import regular\nfrom src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos\n\n\ndef regularidad(g: Grafo) -> Optional[int]:\n    if regular(g):\n        return grado(g, nodos(g)[0])\n    return None\n\n# La propiedad de k-regularidad de los grafos completos es\ndef prop_completoRegular(n: int) -> bool:\n    return regularidad(completo(n)) == n - 1\n\n# La comprobaci\u00f3n es\n#    >>> all(prop_completoRegular(n) for n in range(1, 21))\n#    True\n\n# La propiedad de k-regularidad de los grafos ciclos es\ndef prop_cicloRegular(n: int) -> bool:\n    return regularidad(grafoCiclo(n)) == 2\n\n# La comprobaci\u00f3n es\n#    >>> all(prop_cicloRegular(n) for n in range(3, 21))\n#    True\n\n# Verificaci\u00f3n\n# ============\n\ndef test_k_regularidad() -> None:\n    g1 = creaGrafo_(Orientacion.ND, (1,2), [(1,2),(2,3)])\n    g2 = creaGrafo_(Orientacion.D, (1,2), [(1,2),(2,3)])\n    assert regularidad(g1) == 1\n    assert regularidad(g2) is None\n    assert regularidad(completo(4)) == 3\n    assert regularidad(completo(5)) == 4\n    assert regularidad(grafoCiclo(4)) == 2\n    assert regularidad(grafoCiclo(5)) == 2\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_k_regularidad()\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. Generadores de grafos 2. Grado de un v\u00e9rtice 3. Lema del apret\u00f3n de manos 4. Grafos regulares 5. Grafos k-regulares 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\/7947"}],"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=7947"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7947\/revisions"}],"predecessor-version":[{"id":7948,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7947\/revisions\/7948"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7947"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7947"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7947"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}