La semana en Exercitium (3 de junio de 2023)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas sobre el tipo abstracto de datos de los grafos:
- 1. Incidentes de un vértice
- 2. Contiguos de un vértice
- 3. Lazos de un grafo
- 4. Número de aristas de un grafo
- 5. Grado positivo y negativo de un vértice
A continuación se muestran las soluciones.
1. Incidentes de un vértice
En un un grafo g, los incidentes de un vértice v es el conjuntos de vértices x de g para los que hay un arco (o una arista) de x a v; es decir, que v es adyacente a x.
Usando el tipo abstracto de datos de los grafos, definir la función,
1 |
incidentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v] |
tal que incidentes g v
es la lista de los vértices incidentes en el vértice v
. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> incidentes g1 1 [3] λ> incidentes g1 2 [1,2,3] λ> incidentes g1 3 [] λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> incidentes g2 1 [2,3] λ> incidentes g2 2 [1,2,3] λ> incidentes g2 3 [1,2] |
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 |
module Grafo_Incidentes_de_un_vertice where import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, adyacentes, creaGrafo') import Data.Ix import Test.Hspec incidentes :: (Ix v,Num p) => Grafo v p -> v -> [v] incidentes g v = [x | x <- nodos g, v `elem` adyacentes g x] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ incidentes g1 1 `shouldBe` [3] it "e2" $ incidentes g1 2 `shouldBe` [1,2,3] it "e3" $ incidentes g1 3 `shouldBe` [] it "e4" $ incidentes g2 1 `shouldBe` [2,3] it "e5" $ incidentes g2 2 `shouldBe` [1,2,3] it "e6" $ incidentes g2 3 `shouldBe` [1,2] where g1, g2 :: Grafo Int Int g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- -- Finished in 0.0005 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 |
from src.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, creaGrafo_, nodos) def incidentes(g: Grafo, v: Vertice) -> list[Vertice]: return [x for x in nodos(g) if v in adyacentes(g, x)] # Verificación # ============ def test_incidentes() -> None: g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,2),(3,1),(3,2)]) g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,2),(3,1),(3,2)]) assert incidentes(g1,1) == [3] assert incidentes(g1,2) == [1, 2, 3] assert incidentes(g1,3) == [] assert incidentes(g2, 1) == [2, 3] assert incidentes(g2, 2) == [1, 2, 3] assert incidentes(g2, 3) == [1, 2] print("Verificado") # La verificación es # >>> test_incidentes() # Verificado |
2. Contiguos de un vértice
En un un grafo g, los contiguos de un vértice v es el conjuntos de vértices x de g tales que x es adyacente o incidente con v.
Usando el tipo abstracto de datos de los grafos, definir la función,
1 |
contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v] |
tal que contiguos g v
es el conjunto de los vértices de g contiguos con el vértice v. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> contiguos g1 1 [2,3] λ> contiguos g1 2 [2,1,3] λ> contiguos g1 3 [1,2] λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] λ> contiguos g2 1 [2,3] λ> contiguos g2 2 [1,2,3] λ> contiguos g2 3 [1,2] |
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 |
module Grafo_Contiguos_de_un_vertice where import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo') import Grafo_Incidentes_de_un_vertice (incidentes) import Data.List (nub) import Data.Ix import Test.Hspec contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v] contiguos g v = nub (adyacentes g v ++ incidentes g v) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ contiguos g1 1 `shouldBe` [2,3] it "e2" $ contiguos g1 2 `shouldBe` [2,1,3] it "e3" $ contiguos g1 3 `shouldBe` [1,2] it "e4" $ contiguos g2 1 `shouldBe` [2,3] it "e5" $ contiguos g2 2 `shouldBe` [1,2,3] it "e6" $ contiguos g2 3 `shouldBe` [1,2] where g1, g2 :: Grafo Int Int g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)] g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- -- Finished in 0.0005 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 |
from src.Grafo_Incidentes_de_un_vertice import incidentes from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_ def contiguos(g: Grafo, v: Vertice) -> list[Vertice]: return list(set(adyacentes(g, v) + incidentes(g, v))) # Verificación # ============ def test_contiguos() -> None: g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,2),(3,1),(3,2)]) g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,2),(3,1),(3,2)]) assert contiguos(g1, 1) == [2, 3] assert contiguos(g1, 2) == [1, 2, 3] assert contiguos(g1, 3) == [1, 2] assert contiguos(g2, 1) == [2, 3] assert contiguos(g2, 2) == [1, 2, 3] assert contiguos(g2, 3) == [1, 2] print("Verificado") # La verificación es # >>> test_contiguos() # Verificado |
3. Lazos de un grafo
Usando el tipo abstracto de datos de los grafos, definir las funciones,
1 2 |
lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)] nLazos :: (Ix v,Num p) => Grafo v p -> Int |
tales que
lazos g
es el conjunto de los lazos (es decir, aristas cuyos extremos son iguales) del grafog
. Por ejemplo,
1 2 3 4 5 6 |
λ> ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)] λ> ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)] λ> lazos ej1 [(1,1),(3,3)] λ> lazos ej2 [] |
nLazos g
es el número de lazos del grafog
. Por ejemplo,
1 2 3 4 |
λ> nLazos ej1 2 λ> nLazos ej2 0 |
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 |
module Grafo_Lazos_de_un_grafo where import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, aristaEn, creaGrafo') import Data.Ix (Ix) import Test.Hspec (Spec, hspec, it, shouldBe) lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)] lazos g = [(x,x) | x <- nodos g, aristaEn g (x,x)] nLazos :: (Ix v,Num p) => Grafo v p -> Int nLazos = length . lazos -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ lazos ej1 `shouldBe` [(1,1),(3,3)] it "e2" $ lazos ej2 `shouldBe` [] it "e3" $ nLazos ej1 `shouldBe` 2 it "e4" $ nLazos ej2 `shouldBe` 0 where ej1, ej2 :: Grafo Int Int ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)] ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0005 seconds -- 4 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 |
from src.TAD.Grafo import (Grafo, Orientacion, Vertice, aristaEn, creaGrafo_, nodos) def lazos(g: Grafo) -> list[tuple[Vertice, Vertice]]: return [(x, x) for x in nodos(g) if aristaEn(g, (x, x))] def nLazos(g: Grafo) -> int: return len(lazos(g)) # Verificación # ============ def test_lazos() -> None: ej1 = creaGrafo_(Orientacion.D, (1,3), [(1,1),(2,3),(3,2),(3,3)]) ej2 = creaGrafo_(Orientacion.ND, (1,3), [(2,3),(3,1)]) assert lazos(ej1) == [(1,1),(3,3)] assert lazos(ej2) == [] assert nLazos(ej1) == 2 assert nLazos(ej2) == 0 print("Verificado") # La verificación es # >>> test_lazos() # Verificado |
4. Número de aristas de un grafo
Usando el tipo abstracto de datos de los grafos, definir la función,
1 |
nAristas :: (Ix v,Num p) => Grafo v p -> Int |
tal que nAristas g
es el número de aristas del grafo g
. Si g es no dirigido, las aristas de v1
a v2
y de v2
a v1
sólo se cuentan una vez. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
λ> 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' ND (1,3) [(1,2),(1,3),(2,3),(3,3)] λ> g4 = creaGrafo' ND (1,4) [(1,1),(1,2),(3,3)] λ> nAristas g1 8 λ> nAristas g2 7 λ> nAristas g3 4 λ> nAristas g4 3 λ> nAristas (completo 4) 6 λ> nAristas (completo 5) 10 |
Definir la función
1 |
prop_nAristasCompleto :: Int -> Bool |
tal que prop_nAristasCompleto n
se verifica si el número de aristas del grafo completo de orden n
es n*(n-1)/2
y, usando la función, comprobar que la propiedad se cumple para n
de 1 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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
module Grafo_Numero_de_aristas_de_un_grafo where import TAD.Grafo (Grafo, Orientacion (D, ND), dirigido, aristas, creaGrafo') import Data.Ix (Ix) import Grafo_Lazos_de_un_grafo (nLazos) import Grafo_Grafos_completos (completo) import Test.Hspec (Spec, hspec, it, shouldBe, describe) -- 1ª solución -- =========== nAristas :: (Ix v,Num p) => Grafo v p -> Int nAristas g | dirigido g = length (aristas g) | otherwise = (length (aristas g) + nLazos g) `div` 2 -- 2ª solución -- =========== nAristas2 :: (Ix v,Num p) => Grafo v p -> Int nAristas2 g | dirigido g = length (aristas g) | otherwise = length [(x,y) | ((x,y),_) <- aristas g, x <= y] -- Propiedad -- ========= prop_nAristasCompleto :: Int -> Bool prop_nAristasCompleto n = nAristas (completo n) == n*(n-1) `div` 2 -- La comprobación es -- λ> and [prop_nAristasCompleto n | n <- [1..20]] -- True -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do describe "def. 1" $ specG nAristas describe "def. 2" $ specG nAristas2 specG :: (Grafo Int Int -> Int) -> Spec specG nAristas' = do it "e1" $ nAristas' g1 `shouldBe` 8 it "e2" $ nAristas' g2 `shouldBe` 7 it "e3" $ nAristas' g3 `shouldBe` 4 it "e4" $ nAristas' g4 `shouldBe` 3 it "e5" $ nAristas' (completo 4) `shouldBe` 6 it "e6" $ nAristas' (completo 5) `shouldBe` 10 where g1, g2, g3, g4 :: 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' ND (1,3) [(1,2),(1,3),(2,3),(3,3)] g4 = creaGrafo' ND (1,4) [(1,1),(1,2),(3,3)] -- La verificación es -- λ> verifica -- -- def. 1 -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- def. 2 -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- -- Finished in 0.0013 seconds -- 12 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 |
from src.Grafo_Grafos_completos import completo from src.Grafo_Lazos_de_un_grafo import nLazos from src.TAD.Grafo import Grafo, Orientacion, aristas, creaGrafo_, dirigido # 1ª solución # =========== def nAristas(g: Grafo) -> int: if dirigido(g): return len(aristas(g)) return (len(aristas(g)) + nLazos(g)) // 2 # 2ª solución # =========== def nAristas2(g: Grafo) -> int: if dirigido(g): return len(aristas(g)) return len([(x, y) for ((x,y),_) in aristas(g) if x <= y]) # Propiedad # ========= def prop_nAristasCompleto(n: int) -> bool: return nAristas(completo(n)) == n*(n-1) // 2 # La comprobación es # >>> all(prop_nAristasCompleto(n) for n in range(1, 21)) # True # Verificación # ============ def test_nAristas() -> 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.ND, (1,3), [(1,2),(1,3),(2,3),(3,3)]) g4 = creaGrafo_(Orientacion.ND, (1,4), [(1,1),(1,2),(3,3)]) for nAristas_ in [nAristas, nAristas2]: assert nAristas_(g1) == 8 assert nAristas_(g2) == 7 assert nAristas_(g3) == 4 assert nAristas_(g4) == 3 assert nAristas_(completo(4)) == 6 assert nAristas_(completo(5)) == 10 print("Verificado") # La verificación es # >>> test_nAristas() # Verificado |
5. Grado positivo y negativo de un vértice
El grado positivo de un vértice v de un grafo g es el número de vértices de g adyacentes con v y su grado negativo es el número de vértices de g incidentes con v.
Usando el tipo abstracto de datos de los grafos, definir las funciones,
1 2 |
gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int |
tales que
+ gradoPos g v
es el grado positivo del vértice v
en el grafo g
. Por ejemplo,
1 2 3 4 5 6 7 8 |
λ> 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)] λ> gradoPos g1 5 4 λ> gradoPos g2 5 0 λ> gradoPos g2 1 3 |
gradoNeg g v
es el grado negativo del vérticev
en el grafog
. Por ejemplo,
1 2 3 4 5 6 |
λ> gradoNeg g1 5 4 λ> gradoNeg g2 5 3 λ> gradoNeg g2 1 0 |
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 74 75 76 77 78 79 80 |
module Grafo_Grados_positivos_y_negativos where import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo') import Data.Ix (Ix) import Grafo_Incidentes_de_un_vertice (incidentes) import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª definición de gradoPos gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int gradoPos g v = length (adyacentes g v) -- 2ª definición de gradoPos gradoPos2 :: (Ix v,Num p) => Grafo v p -> v -> Int gradoPos2 g = length . adyacentes g -- 1ª definición de gradoNeg gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int gradoNeg g v = length (incidentes g v) -- 2ª definición de gradoNeg gradoNeg2 :: (Ix v,Num p) => Grafo v p -> v -> Int gradoNeg2 g = length . incidentes g -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ gradoPos g1 5 `shouldBe` 4 it "e2" $ gradoPos g2 5 `shouldBe` 0 it "e3" $ gradoPos g2 1 `shouldBe` 3 it "e4" $ gradoNeg g1 5 `shouldBe` 4 it "e5" $ gradoNeg g2 5 `shouldBe` 3 it "e6" $ gradoNeg g2 1 `shouldBe` 0 it "e7" $ gradoPos2 g1 5 `shouldBe` 4 it "e8" $ gradoPos2 g2 5 `shouldBe` 0 it "e9" $ gradoPos2 g2 1 `shouldBe` 3 it "e10" $ gradoNeg2 g1 5 `shouldBe` 4 it "e11" $ gradoNeg2 g2 5 `shouldBe` 3 it "e12" $ gradoNeg2 g2 1 `shouldBe` 0 where g1, g2 :: 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)] -- La verificación es -- λ> verifica -- -- def. 1 -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- def. 2 -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- -- Finished in 0.0013 seconds -- 12 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 |
from src.Grafo_Incidentes_de_un_vertice import incidentes from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_ def gradoPos(g: Grafo, v: Vertice) -> int: return len(adyacentes(g, v)) def gradoNeg(g: Grafo, v: Vertice) -> int: return len(incidentes(g, v)) # Verificación # ============ def test_GradoPosNeg() -> 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)]) assert gradoPos(g1, 5) == 4 assert gradoPos(g2, 5) == 0 assert gradoPos(g2, 1) == 3 assert gradoNeg(g1, 5) == 4 assert gradoNeg(g2, 5) == 3 assert gradoNeg(g2, 1) == 0 print("Verificado") # La verificación es # >>> test_GradoPosNeg() # Verificado |