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,

   incidentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]

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,

   λ> 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]

λ> 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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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,

   contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v]

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,

   λ> 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]

λ> 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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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,

   lazos  :: (Ix v,Num p) => Grafo v p -> [(v,v)]
   nLazos :: (Ix v,Num p) => Grafo v p -> Int

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 grafo g. Por ejemplo,

     λ> 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
     []

λ> 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 grafo g. Por ejemplo,

     λ> nLazos ej1
     2
     λ> nLazos ej2
     0

λ> nLazos ej1

λ> nLazos ej2

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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

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

Soluciones en Python

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

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,

   nAristas :: (Ix v,Num p) => Grafo v p ->  Int

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,

   λ> 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

λ> 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

λ> nAristas g2

λ> nAristas g3

λ> nAristas g4

λ> nAristas (completo 4)

λ> nAristas (completo 5)

Definir la función

   prop_nAristasCompleto :: Int -> Bool

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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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,

   gradoPos :: (Ix v,Num p) => Grafo v p -> v -> Int
   gradoNeg :: (Ix v,Num p) => Grafo v p -> v -> Int

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,

     λ> 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

λ> 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

λ> gradoPos g2 5

λ> gradoPos g2 1

gradoNeg g v es el grado negativo del vértice v en el grafo g. Por ejemplo,

     λ> gradoNeg g1 5
     4
     λ> gradoNeg g2 5
     3
     λ> gradoNeg g2 1
     0

λ> gradoNeg g1 5

λ> gradoNeg g2 5

λ> gradoNeg g2 1

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

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

Se puede imprimir o compartir con