La semana en Exercitium (10 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. Generadores de grafos
2. Grado de un vértice
3. Lema del apretón de manos
4. Grafos regulares
5. Grafos k-regulares

A continuación se muestran las soluciones.

1. Generadores de grafos

Definir un generador de grafos para comprobar propiedades de grafos con QuickCheck y hacer el tipo de los Grafos un subtipo de Arbitrary.

Usando el generador, con QuickCheck que para cualquier grafo g, las sumas de los grados positivos y la de los grados negativos de los vértices de g son iguales.

Soluciones

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

Soluciones en Haskell

La definición del generador es

{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

module TAD.GrafoGenerador where

import TAD.Grafo (Grafo, Orientacion (D, ND), creaGrafo)
import Test.QuickCheck (Arbitrary, Gen, arbitrary, choose, vectorOf)

-- (generaGND n ps) es el grafo completo de orden n tal que los pesos
-- están determinados por ps. Por ejemplo,
--    λ> generaGND 3 [4,2,5]
--    G ND ([1,2,3],[((1,2),4),((1,3),2),((2,3),5)])
--    λ> generaGND 3 [4,-2,5]
--    G ND ([1,2,3],[((1,2),4),((2,3),5)])
generaGND :: Int -> [Int] -> Grafo Int Int
generaGND n ps  = creaGrafo ND (1,n) l3
  where l1 = [(x,y) | x <- [1..n], y <- [1..n], x < y]
        l2 = zip l1 ps
        l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]

-- (generaGD n ps) es el grafo completo de orden n tal que los pesos
-- están determinados por ps. Por ejemplo,
--    λ> generaGD 3 [4,2,5]
--    G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5)])
--    λ> generaGD 3 [4,2,5,3,7,9,8,6]
--    G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5),
--                  ((2,1),3),((2,2),7),((2,3),9),
--                  ((3,1),8),((3,2),6)])
generaGD :: Int -> [Int] -> Grafo Int Int
generaGD n ps = creaGrafo D (1,n) l3
  where l1 = [(x,y) | x <- [1..n], y <- [1..n]]
        l2 = zip l1 ps
        l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]

-- genGD es un generador de grafos dirigidos. Por ejemplo,
--    λ> sample genGD
--    G D ([1],[])
--    G D ([1,2],[((1,1),5),((2,1),4)])
--    G D ([1,2],[((1,1),3),((1,2),3)])
--    G D ([1,2,3,4,5,6],[])
--    G D ([1,2],[((2,2),16)])
--    ...
genGD :: Gen (Grafo Int Int)
genGD = do
  n <- choose (1,10)
  xs <- vectorOf (n*n) arbitrary
  return (generaGD n xs)

-- genGND es un generador de grafos dirigidos. Por ejemplo,
--    λ> sample genGND
--    G ND ([1,2,3,4,5,6,7,8],[])
--    G ND ([1],[])
--    G ND ([1,2,3,4,5],[((1,2),2),((2,3),5),((3,4),5),((3,5),5)])
--    G ND ([1,2,3,4,5],[((1,2),6),((1,3),5),((1,5),1),((3,5),9),((4,5),6)])
--    G ND ([1,2,3,4],[((1,2),5),((3,4),2)])
--    G ND ([1,2,3],[])
--    G ND ([1,2,3,4],[((1,2),5),((1,4),14),((2,4),10)])
--    G ND ([1,2,3,4,5],[((1,5),8),((4,5),5)])
--    G ND ([1,2,3,4],[((1,2),1),((1,4),4),((2,3),4),((3,4),5)])
--    G ND ([1,2,3],[((1,2),8),((1,3),8),((2,3),3)])
--    ...
genGND :: Gen (Grafo Int Int)
genGND = do
  n <- choose (1,10)
  xs <- vectorOf (n*n) arbitrary
  return (generaGND n xs)

-- genG es un generador de grafos. Por ejemplo,
--    λ> sample genG
--    G ND ([1,2,3,4,5,6],[])
--    G D ([1],[((1,1),2)])
--    G D ([1,2],[((1,1),9)])
--    ...
genG :: Gen (Grafo Int Int)
genG = do
  d <- choose (True,False)
  n <- choose (1,10)
  xs <- vectorOf (n*n) arbitrary
  if d then return (generaGD n xs)
       else return (generaGND n xs)

-- Los grafos está contenido en la clase de los objetos generables
-- aleatoriamente.
instance Arbitrary (Grafo Int Int) where
  arbitrary = genG

{-# LANGUAGE FlexibleInstances #-}

{-# OPTIONS_GHC -fno-warn-orphans #-}

module TAD.GrafoGenerador where

import TAD.Grafo (Grafo, Orientacion (D, ND), creaGrafo)

import Test.QuickCheck (Arbitrary, Gen, arbitrary, choose, vectorOf)

-- (generaGND n ps) es el grafo completo de orden n tal que los pesos

-- están determinados por ps. Por ejemplo,

-- λ> generaGND 3 [4,2,5]

-- G ND ([1,2,3],[((1,2),4),((1,3),2),((2,3),5)])

-- λ> generaGND 3 [4,-2,5]

-- G ND ([1,2,3],[((1,2),4),((2,3),5)])

generaGND :: Int -> [Int] -> Grafo Int Int

generaGND n ps = creaGrafo ND (1,n) l3

where l1 = [(x,y) | x <- [1..n], y <- [1..n], x < y]

l2 = zip l1 ps

l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]

-- (generaGD n ps) es el grafo completo de orden n tal que los pesos

-- están determinados por ps. Por ejemplo,

-- λ> generaGD 3 [4,2,5]

-- G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5)])

-- λ> generaGD 3 [4,2,5,3,7,9,8,6]

-- G D ([1,2,3],[((1,1),4),((1,2),2),((1,3),5),

-- ((2,1),3),((2,2),7),((2,3),9),

-- ((3,1),8),((3,2),6)])

generaGD :: Int -> [Int] -> Grafo Int Int

generaGD n ps = creaGrafo D (1,n) l3

where l1 = [(x,y) | x <- [1..n], y <- [1..n]]

l2 = zip l1 ps

l3 = [(x,y,z) | ((x,y),z) <- l2, z > 0]

-- genGD es un generador de grafos dirigidos. Por ejemplo,

-- λ> sample genGD

-- G D ([1],[])

-- G D ([1,2],[((1,1),5),((2,1),4)])

-- G D ([1,2],[((1,1),3),((1,2),3)])

-- G D ([1,2,3,4,5,6],[])

-- G D ([1,2],[((2,2),16)])

-- ...

genGD :: Gen (Grafo Int Int)

genGD = do

n <- choose (1,10)

xs <- vectorOf (n*n) arbitrary

return (generaGD n xs)

-- genGND es un generador de grafos dirigidos. Por ejemplo,

-- λ> sample genGND

-- G ND ([1,2,3,4,5,6,7,8],[])

-- G ND ([1],[])

-- G ND ([1,2,3,4,5],[((1,2),2),((2,3),5),((3,4),5),((3,5),5)])

-- G ND ([1,2,3,4,5],[((1,2),6),((1,3),5),((1,5),1),((3,5),9),((4,5),6)])

-- G ND ([1,2,3,4],[((1,2),5),((3,4),2)])

-- G ND ([1,2,3],[])

-- G ND ([1,2,3,4],[((1,2),5),((1,4),14),((2,4),10)])

-- G ND ([1,2,3,4,5],[((1,5),8),((4,5),5)])

-- G ND ([1,2,3,4],[((1,2),1),((1,4),4),((2,3),4),((3,4),5)])

-- G ND ([1,2,3],[((1,2),8),((1,3),8),((2,3),3)])

-- ...

genGND :: Gen (Grafo Int Int)

genGND = do

n <- choose (1,10)

xs <- vectorOf (n*n) arbitrary

return (generaGND n xs)

-- genG es un generador de grafos. Por ejemplo,

-- λ> sample genG

-- G ND ([1,2,3,4,5,6],[])

-- G D ([1],[((1,1),2)])

-- G D ([1,2],[((1,1),9)])

-- ...

genG :: Gen (Grafo Int Int)

genG = do

d <- choose (True,False)

n <- choose (1,10)

xs <- vectorOf (n*n) arbitrary

if d then return (generaGD n xs)

else return (generaGND n xs)

-- Los grafos está contenido en la clase de los objetos generables

-- aleatoriamente.

instance Arbitrary (Grafo Int Int) where

arbitrary = genG

La comprobación de la propiedad es

module Grafo_Propiedades_de_grados_positivos_y_negativos where

import TAD.Grafo (Grafo, nodos)
import TAD.GrafoGenerador
import Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg)
import Test.QuickCheck

-- La propiedad es
prop_sumaGrados :: Grafo Int Int -> Bool
prop_sumaGrados g =
  sum [gradoPos g v | v <- vs] == sum [gradoNeg g v | v <- vs]
  where vs = nodos g

-- La comprobación es
--    λ> quickCheck prop_sumaGrados
--    +++ OK, passed 100 tests.

module Grafo_Propiedades_de_grados_positivos_y_negativos where

import TAD.Grafo (Grafo, nodos)

import TAD.GrafoGenerador

import Grafo_Grados_positivos_y_negativos (gradoPos, gradoNeg)

import Test.QuickCheck

-- La propiedad es

prop_sumaGrados :: Grafo Int Int -> Bool

prop_sumaGrados g =

sum [gradoPos g v | v <- vs] == sum [gradoNeg g v | v <- vs]

where vs = nodos g

-- La comprobación es

-- λ> quickCheck prop_sumaGrados

-- +++ OK, passed 100 tests.

Soluciones en Python

La definición del generador es

from hypothesis import strategies as st
from hypothesis.strategies import composite

from src.TAD.Grafo import Orientacion, creaGrafo_


# Generador de aristas. Por ejemplo,
#    >>> gen_aristas(5).example()
#    [(2, 5), (4, 5), (1, 2), (2, 3), (4, 1)]
#    >>> gen_aristas(5).example()
#    [(3, 4)]
#    >>> gen_aristas(5).example()
#    [(5, 3), (3, 2), (1, 3), (5, 2)]
@composite
def gen_aristas(draw, n):
    as_ = draw(st.lists(st.tuples(st.integers(1,n),
                                  st.integers(1,n)),
                        unique=True))
    return as_

# Generador de grafos no dirigidos. Por ejemplo,
#    >>> gen_grafoND().example()
#    G ND ([1, 2, 3, 4, 5], [(1, 4), (5, 5)])
#    >>> gen_grafoND().example()
#    G ND ([1], [])
#    >>> gen_grafoND().example()
#    G ND ([1, 2, 3, 4, 5, 6, 7, 8], [(7, 7)])
#    >>> gen_grafoND().example()
#    G ND ([1, 2, 3, 4, 5, 6], [(1, 3), (2, 4), (3, 3), (3, 5)])
@composite
def gen_grafoND(draw):
    n = draw(st.integers(1,10))
    as_ = [(x, y) for (x, y ) in draw(gen_aristas(n)) if x <= y]
    return creaGrafo_(Orientacion.ND, (1,n), as_)

# Generador de grafos dirigidos. Por ejemplo,
#    >>> gen_grafoD().example()
#    G D ([1, 2, 3, 4], [(3, 3), (4, 1)])
#    >>> gen_grafoD().example()
#    G D ([1, 2], [(1, 1), (2, 1), (2, 2)])
#    >>> gen_grafoD().example()
#    G D ([1, 2], [])
@composite
def gen_grafoD(draw):
    n = draw(st.integers(1,10))
    as_ = draw(gen_aristas(n))
    return creaGrafo_(Orientacion.D, (1,n), as_)

# Generador de grafos. Por ejemplo,
#    >>> gen_grafo().example()
#    G ND ([1, 2, 3, 4, 5, 6, 7], [(1, 3)])
#    >>> gen_grafo().example()
#    G D ([1], [])
#    >>> gen_grafo().example()
#    G D ([1, 2, 3, 4, 5, 6, 7], [(1, 3), (3, 4), (5, 5)])
@composite
def gen_grafo(draw):
    o = draw(st.sampled_from([Orientacion.D, Orientacion.ND]))
    if o == Orientacion.ND:
        return draw(gen_grafoND())
    return draw(gen_grafoD())

from hypothesis import strategies as st

from hypothesis.strategies import composite

from src.TAD.Grafo import Orientacion, creaGrafo_

# Generador de aristas. Por ejemplo,

# >>> gen_aristas(5).example()

# [(2, 5), (4, 5), (1, 2), (2, 3), (4, 1)]

# >>> gen_aristas(5).example()

# [(3, 4)]

# >>> gen_aristas(5).example()

# [(5, 3), (3, 2), (1, 3), (5, 2)]

@composite

def gen_aristas(draw, n):

as_ = draw(st.lists(st.tuples(st.integers(1,n),

st.integers(1,n)),

unique=True))

return as_

# Generador de grafos no dirigidos. Por ejemplo,

# >>> gen_grafoND().example()

# G ND ([1, 2, 3, 4, 5], [(1, 4), (5, 5)])

# >>> gen_grafoND().example()

# G ND ([1], [])

# >>> gen_grafoND().example()

# G ND ([1, 2, 3, 4, 5, 6, 7, 8], [(7, 7)])

# >>> gen_grafoND().example()

# G ND ([1, 2, 3, 4, 5, 6], [(1, 3), (2, 4), (3, 3), (3, 5)])

@composite

def gen_grafoND(draw):

n = draw(st.integers(1,10))

as_ = [(x, y) for (x, y ) in draw(gen_aristas(n)) if x <= y]

return creaGrafo_(Orientacion.ND, (1,n), as_)

# Generador de grafos dirigidos. Por ejemplo,

# >>> gen_grafoD().example()

# G D ([1, 2, 3, 4], [(3, 3), (4, 1)])

# >>> gen_grafoD().example()

# G D ([1, 2], [(1, 1), (2, 1), (2, 2)])

# >>> gen_grafoD().example()

# G D ([1, 2], [])

@composite

def gen_grafoD(draw):

n = draw(st.integers(1,10))

as_ = draw(gen_aristas(n))

return creaGrafo_(Orientacion.D, (1,n), as_)

# Generador de grafos. Por ejemplo,

# >>> gen_grafo().example()

# G ND ([1, 2, 3, 4, 5, 6, 7], [(1, 3)])

# >>> gen_grafo().example()

# G D ([1], [])

# >>> gen_grafo().example()

# G D ([1, 2, 3, 4, 5, 6, 7], [(1, 3), (3, 4), (5, 5)])

@composite

def gen_grafo(draw):

o = draw(st.sampled_from([Orientacion.D, Orientacion.ND]))

if o == Orientacion.ND:

return draw(gen_grafoND())

return draw(gen_grafoD())

La comprobación de la propiedad es

from hypothesis import given

from src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos
from src.TAD.Grafo import nodos
from src.TAD.GrafoGenerador import gen_grafo


# La propiedad es
@given(gen_grafo())
def test_sumaGrados(g):
    vs = nodos(g)
    assert sum((gradoPos(g, v) for v in vs)) == sum((gradoNeg(g, v) for v in vs))

# La comprobación es
#    src> poetry run pytest -q Grafo_Propiedades_de_grados_positivos_y_negativos.py
#    1 passed in 0.31s

from hypothesis import given

from src.Grafo_Grados_positivos_y_negativos import gradoNeg, gradoPos

from src.TAD.Grafo import nodos

from src.TAD.GrafoGenerador import gen_grafo

# La propiedad es

@given(gen_grafo())

def test_sumaGrados(g):

vs = nodos(g)

assert sum((gradoPos(g, v) for v in vs)) == sum((gradoNeg(g, v) for v in vs))

# La comprobación es

# src> poetry run pytest -q Grafo_Propiedades_de_grados_positivos_y_negativos.py

# 1 passed in 0.31s

2. 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,

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

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,

   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

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

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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

3. Lema del apretón de manos

En la teoría de grafos, se conoce como “Lema del apretón de manos” la siguiente propiedad: la suma de los grados de los vértices de g es el doble del número de aristas de g.

Comprobar con QuickCheck que para cualquier grafo g, se verifica dicha propiedad.

Soluciones

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

Soluciones en Haskell

import TAD.Grafo (Grafo, nodos)
import TAD.GrafoGenerador
import Grafo_Grado_de_un_vertice (grado)
import Grafo_Numero_de_aristas_de_un_grafo (nAristas)
import Test.QuickCheck

prop_apretonManos :: Grafo Int Int -> Bool
prop_apretonManos g =
  sum [grado g v | v <- nodos g] == 2 * nAristas g

-- La comprobación es
--    λ> quickCheck prop_apretonManos
--    +++ OK, passed 100 tests.

import TAD.Grafo (Grafo, nodos)

import TAD.GrafoGenerador

import Grafo_Grado_de_un_vertice (grado)

import Grafo_Numero_de_aristas_de_un_grafo (nAristas)

import Test.QuickCheck

prop_apretonManos :: Grafo Int Int -> Bool

prop_apretonManos g =

sum [grado g v | v <- nodos g] == 2 * nAristas g

-- La comprobación es

-- λ> quickCheck prop_apretonManos

-- +++ OK, passed 100 tests.

Soluciones en Python

from hypothesis import given

from src.Grafo_Grado_de_un_vertice import grado
from src.Grafo_Numero_de_aristas_de_un_grafo import nAristas
from src.TAD.Grafo import nodos
from src.TAD.GrafoGenerador import gen_grafo


# La propiedad es
@given(gen_grafo())
def test_apreton(g):
    assert sum((grado(g, v) for v in nodos(g))) == 2 * nAristas(g)

# La comprobación es
#    src> poetry run pytest -q Grafo_Lema_del_apreton_de_manos.py
#    1 passed in 0.32s

from hypothesis import given

from src.Grafo_Grado_de_un_vertice import grado

from src.Grafo_Numero_de_aristas_de_un_grafo import nAristas

from src.TAD.Grafo import nodos

from src.TAD.GrafoGenerador import gen_grafo

# La propiedad es

@given(gen_grafo())

def test_apreton(g):

assert sum((grado(g, v) for v in nodos(g))) == 2 * nAristas(g)

# La comprobación es

# src> poetry run pytest -q Grafo_Lema_del_apreton_de_manos.py

# 1 passed in 0.32s

4. 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,

   regular :: (Ix v,Num p) => Grafo v p -> Bool

1	regular :: (Ix v,Num p) => Grafo v p -> Bool

tal que (regular g) se verifica si el grafo g es regular. Por ejemplo,

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

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

Soluciones en Haskell

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

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

Soluciones en Python

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

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

5. 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,

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

1	regularidad :: (Ix v,Num p) => Grafo v p -> Maybe Int

tal que (regularidad g) es la regularidad de g. Por ejemplo,

   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

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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

1. Generadores de grafos

2. Grado de un vértice

3. Lema del apretón de manos

4. Grafos regulares

5. Grafos k-regulares

Se puede imprimir o compartir con