Grafos

TAD de los grafos: Grafos k-regulares

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

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

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: 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 k-regulares

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: Grado positivo y negativo de un vértice

Entradas recientes

Buscar

Correo electrónico