TAD de los grafos: Grado de un vértice
El grado de un vértice v de un grafo dirigido g, es el número aristas de g que contiene a v. Si g es no dirigido, el grado de un vértice v es el número de aristas incidentes en v, teniendo en cuenta que los lazos se cuentan dos veces.
Usando el tipo abstracto de datos de los grafos, definir las funciones,
|
1 |
grado :: (Ix v,Num p) => Grafo v p -> v -> Int |
tal que grado g v es el grado del vértice v en el grafo g. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)] g2 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)] g3 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] g4 = creaGrafo' D (1,1) [(1,1)] g5 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)] g6 = creaGrafo' D (1,3) [(1,2),(1,3),(2,3),(3,3)] grado g1 5 == 4 grado g2 5 == 3 grado g2 1 == 3 grado g3 2 == 4 grado g3 1 == 2 grado g3 3 == 2 grado g4 1 == 2 grado g6 3 == 4 grado g6 3 == 4 |
Comprobar con QuickCheck que en todo grafo, el número de nodos de grado impar es par.
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 71 72 73 |
module Grafo_Grado_de_un_vertice where import TAD.Grafo (Grafo, Orientacion (D, ND), dirigido, nodos, creaGrafo') import Data.Ix (Ix) import Grafo_Lazos_de_un_grafo (lazos) import Grafo_Incidentes_de_un_vertice (incidentes) import Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg) import Test.Hspec (Spec, hspec, it, shouldBe) grado :: (Ix v,Num p) => Grafo v p -> v -> Int grado g v | dirigido g = gradoNeg g v + gradoPos g v | (v,v) `elem` lazos g = length (incidentes g v) + 1 | otherwise = length (incidentes g v) -- La propiedad es prop_numNodosGradoImpar :: Grafo Int Int -> Bool prop_numNodosGradoImpar g = even (length [v | v <- nodos g, odd (grado g v)]) -- La comprobación es -- λ> quickCheck prop_numNodosGradoImpar -- +++ OK, passed 100 tests. -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ grado g1 5 `shouldBe` 4 it "e2" $ grado g2 5 `shouldBe` 3 it "e3" $ grado g2 1 `shouldBe` 3 it "e4" $ grado g3 2 `shouldBe` 4 it "e5" $ grado g3 1 `shouldBe` 2 it "e6" $ grado g3 3 `shouldBe` 2 it "e7" $ grado g4 1 `shouldBe` 2 it "e8" $ grado g5 3 `shouldBe` 4 it "e9" $ grado g6 3 `shouldBe` 4 where g1, g2, g3, g4, g5, g6 :: Grafo Int Int g1 = creaGrafo' ND (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)] g2 = creaGrafo' D (1,5) [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)] g3 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] g4 = creaGrafo' D (1,1) [(1,1)] g5 = creaGrafo' ND (1,3) [(1,2),(1,3),(2,3),(3,3)] g6 = creaGrafo' D (1,3) [(1,2),(1,3),(2,3),(3,3)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- e7 -- e8 -- e9 -- -- Finished in 0.0015 seconds -- 9 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 48 49 50 51 52 53 54 55 56 |
from hypothesis import given from src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos from src.Grafo_Incidentes_de_un_vertice import incidentes from src.Grafo_Lazos_de_un_grafo import lazos from src.TAD.Grafo import (Grafo, Orientacion, Vertice, creaGrafo_, dirigido, nodos) from src.TAD.GrafoGenerador import gen_grafo def grado(g: Grafo, v: Vertice) -> int: if dirigido(g): return gradoNeg(g, v) + gradoPos(g, v) if (v, v) in lazos(g): return len(incidentes(g, v)) + 1 return len(incidentes(g, v)) # La propiedad esp @given(gen_grafo()) def test_grado1(g): assert len([v for v in nodos(g) if grado(g, v) % 2 == 1]) % 2 == 0 # La comprobación es # src> poetry run pytest -q Grafo_Grado_de_un_vertice.py # 1 passed in 0.36s # Verificación # ============ def test_grado() -> None: g1 = creaGrafo_(Orientacion.ND, (1,5), [(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)]) g2 = creaGrafo_(Orientacion.D, (1,5), [(1,2),(1,3),(1,5),(2,4),(2,5),(4,3),(4,5)]) g3 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,2),(3,1),(3,2)]) g4 = creaGrafo_(Orientacion.D, (1,1), [(1,1)]) g5 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(1,3),(2,3),(3,3)]) g6 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(1,3),(2,3),(3,3)]) assert grado(g1, 5) == 4 assert grado(g2, 5) == 3 assert grado(g2, 1) == 3 assert grado(g3, 2) == 4 assert grado(g3, 1) == 2 assert grado(g3, 3) == 2 assert grado(g4, 1) == 2 assert grado(g5, 3) == 4 assert grado(g6, 3) == 4 print("Verificado") # La verificación es # >>> test_grado() # Verificado |