TAD de los grafos: Grafos regulares
Un grafo regular es un grafo en el que todos sus vértices tienen el mismo grado.
Usando el tipo abstracto de datos de los grafos, definir la función,
|
1 |
regular :: (Ix v,Num p) => Grafo v p -> Bool |
tal que (regular g) se verifica si el grafo g es regular. Por ejemplo,
|
1 2 3 4 5 6 |
λ> regular (creaGrafo' D (1,3) [(1,2),(2,3),(3,1)]) True λ> regular (creaGrafo' ND (1,3) [(1,2),(2,3)]) False λ> regular (completo 4) True |
Comprobar que los grafos completos son regulares.
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 |
module Grafo_Grafos_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_completos (completo) import Test.Hspec (Spec, hspec, it, shouldBe) regular :: (Ix v,Num p) => Grafo v p -> Bool regular g = and [grado g v == k | v <- vs] where vs = nodos g k = grado g (head vs) -- La propiedad de la regularidad de todos los grafos completos de orden -- entre m y n es prop_CompletoRegular :: Int -> Int -> Bool prop_CompletoRegular m n = and [regular (completo x) | x <- [m..n]] -- La comprobación es -- λ> prop_CompletoRegular 1 30 -- True -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ regular g1 `shouldBe` True it "e2" $ regular g2 `shouldBe` False it "e3" $ regular (completo 4) `shouldBe` True where g1, g2 :: Grafo Int Int g1 = creaGrafo' D (1,3) [(1,2),(2,3),(3,1)] g2 = creaGrafo' ND (1,3) [(1,2),(2,3)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.0006 seconds -- 3 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 |
from src.Grafo_Grado_de_un_vertice import grado from src.Grafo_Grafos_completos import completo from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos def regular(g: Grafo) -> bool: vs = nodos(g) k = grado(g, vs[0]) return all(grado(g, v) == k for v in vs) # La propiedad de la regularidad de todos los grafos completos de orden # entre m y n es def prop_CompletoRegular(m: int, n: int) -> bool: return all(regular(completo(x)) for x in range(m, n + 1)) # La comprobación es # >>> prop_CompletoRegular(1, 30) # True # Verificación # ============ def test_regular() -> None: g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,3),(3,1)]) g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,3)]) assert regular(g1) assert not regular(g2) assert regular(completo(4)) print("Verificado") # La verificación es # >>> test_regular() # Verificado |