Exercitium

TAD de los grafos: Grafos regulares

PorJosé A. Alonso 8-junio-20233-junio-2023

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

TAD de los grafos: Lema del apretón de manos

PorJosé A. Alonso 7-junio-202328-mayo-2023

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

TAD de los grafos: Grado de un vértice

PorJosé A. Alonso 6-junio-20233-junio-2023

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

TAD de los grafos: Generadores de grafos

PorJosé A. Alonso 5-junio-20233-junio-2023

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

TAD de los grafos: Grado positivo y negativo de un vértice

PorJosé A. Alonso 2-junio-20233-junio-2023

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

TAD de los grafos: Grafos regulares

TAD de los grafos: Lema del apretón de manos

TAD de los grafos: Grado de un vértice

TAD de los grafos: Generadores de grafos

TAD de los grafos: Grado positivo y negativo de un vértice

Entradas recientes

Buscar

Correo electrónico