TAD de los grafos: Grafos k-regulares
Un grafo k-regular es un grafo con todos sus vértices son de grado k.
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int |
tal que (regularidad g) es la regularidad de g. Por ejemplo,
|
1 2 3 4 5 6 |
regularidad (creaGrafo' ND (1,2) [(1,2),(2,3)]) == Just 1 regularidad (creaGrafo' D (1,2) [(1,2),(2,3)]) == Nothing regularidad (completo 4) == Just 3 regularidad (completo 5) == Just 4 regularidad (grafoCiclo 4) == Just 2 regularidad (grafoCiclo 5) == Just 2 |
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).
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
module Grafo_Grafos_k_regulares where import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, creaGrafo') import Data.Ix (Ix) import Grafo_Grado_de_un_vertice (grado) import Grafo_Grafos_regulares (regular) import Grafo_Grafos_completos (completo) import Grafo_Grafos_ciclos (grafoCiclo) import Test.Hspec (Spec, hspec, it, shouldBe) regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int regularidad g | regular g = Just (grado g (head (nodos g))) | otherwise = Nothing -- La propiedad de k-regularidad de los grafos completos es prop_completoRegular :: Int -> Bool prop_completoRegular n = regularidad (completo n) == Just (n-1) -- La comprobación es -- λ> and [prop_completoRegular n | n <- [1..20]] -- True -- La propiedad de k-regularidad de los grafos ciclos es prop_cicloRegular :: Int -> Bool prop_cicloRegular n = regularidad (grafoCiclo n) == Just 2 -- La comprobación es -- λ> and [prop_cicloRegular n | n <- [3..20]] -- True -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ regularidad g1 `shouldBe` Just 1 it "e2" $ regularidad g2 `shouldBe` Nothing it "e3" $ regularidad (completo 4) `shouldBe` Just 3 it "e4" $ regularidad (completo 5) `shouldBe` Just 4 it "e5" $ regularidad (grafoCiclo 4) `shouldBe` Just 2 it "e6" $ regularidad (grafoCiclo 5) `shouldBe` Just 2 where g1, g2 :: Grafo Int Int g1 = creaGrafo' ND (1,2) [(1,2),(2,3)] g2 = creaGrafo' D (1,2) [(1,2),(2,3)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- -- Finished in 0.0027 seconds -- 6 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 42 43 44 45 46 47 |
from typing import Optional from src.Grafo_Grado_de_un_vertice import grado from src.Grafo_Grafos_ciclos import grafoCiclo from src.Grafo_Grafos_completos import completo from src.Grafo_Grafos_regulares import regular from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos def regularidad(g: Grafo) -> Optional[int]: if regular(g): return grado(g, nodos(g)[0]) return None # La propiedad de k-regularidad de los grafos completos es def prop_completoRegular(n: int) -> bool: return regularidad(completo(n)) == n - 1 # La comprobación es # >>> all(prop_completoRegular(n) for n in range(1, 21)) # True # La propiedad de k-regularidad de los grafos ciclos es def prop_cicloRegular(n: int) -> bool: return regularidad(grafoCiclo(n)) == 2 # La comprobación es # >>> all(prop_cicloRegular(n) for n in range(3, 21)) # True # Verificación # ============ def test_k_regularidad() -> None: g1 = creaGrafo_(Orientacion.ND, (1,2), [(1,2),(2,3)]) g2 = creaGrafo_(Orientacion.D, (1,2), [(1,2),(2,3)]) assert regularidad(g1) == 1 assert regularidad(g2) is None assert regularidad(completo(4)) == 3 assert regularidad(completo(5)) == 4 assert regularidad(grafoCiclo(4)) == 2 assert regularidad(grafoCiclo(5)) == 2 print("Verificado") # La verificación es # >>> test_k_regularidad() # Verificado |