mayo 2023 – Exercitium

TAD de los grafos: Lazos de un grafo

PorJosé A. Alonso 31-mayo-20233-junio-2023

Usando el tipo abstracto de datos de los grafos, definir las funciones,

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

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

tales que

lazos g es el conjunto de los lazos (es decir, aristas cuyos extremos son iguales) del grafo g. Por ejemplo,

     λ> ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)]
     λ> ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)]
     λ> lazos ej1
     [(1,1),(3,3)]
     λ> lazos ej2
     []

λ> ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)]

λ> ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)]

λ> lazos ej1

[(1,1),(3,3)]

λ> lazos ej2

[]

nLazos g es el número de lazos del grafo g. Por ejemplo,

     λ> nLazos ej1
     2
     λ> nLazos ej2
     0

λ> nLazos ej1

λ> nLazos ej2

Soluciones

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

Soluciones en Haskell

module Grafo_Lazos_de_un_grafo where

import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, aristaEn, creaGrafo')
import Data.Ix (Ix)
import Test.Hspec (Spec, hspec, it, shouldBe)

lazos :: (Ix v,Num p) => Grafo v p -> [(v,v)]
lazos g = [(x,x) | x <- nodos g, aristaEn g (x,x)]

nLazos :: (Ix v,Num p) => Grafo v p ->  Int
nLazos = length . lazos

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    lazos ej1 `shouldBe` [(1,1),(3,3)]
  it "e2" $
    lazos ej2 `shouldBe` []
  it "e3" $
    nLazos ej1 `shouldBe` 2
  it "e4" $
    nLazos ej2 `shouldBe` 0
  where
    ej1, ej2 :: Grafo Int Int
    ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)]
    ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)]

-- La verificación es
--      λ> verifica
--
--      e1
--      e2
--      e3
--      e4
--
--      Finished in 0.0005 seconds
--      4 examples, 0 failures

module Grafo_Lazos_de_un_grafo where

import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, aristaEn, creaGrafo')

import Data.Ix (Ix)

import Test.Hspec (Spec, hspec, it, shouldBe)

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

lazos g = [(x,x) | x <- nodos g, aristaEn g (x,x)]

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

nLazos = length . lazos

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

lazos ej1 `shouldBe` [(1,1),(3,3)]

it "e2" $

lazos ej2 `shouldBe` []

it "e3" $

nLazos ej1 `shouldBe` 2

it "e4" $

nLazos ej2 `shouldBe` 0

where

ej1, ej2 :: Grafo Int Int

ej1 = creaGrafo' D (1,3) [(1,1),(2,3),(3,2),(3,3)]

ej2 = creaGrafo' ND (1,3) [(2,3),(3,1)]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- Finished in 0.0005 seconds

-- 4 examples, 0 failures

Soluciones en Python

from src.TAD.Grafo import (Grafo, Orientacion, Vertice, aristaEn, creaGrafo_,
                           nodos)


def lazos(g: Grafo) -> list[tuple[Vertice, Vertice]]:
    return [(x, x) for x in nodos(g) if aristaEn(g, (x, x))]

def nLazos(g: Grafo) -> int:
    return len(lazos(g))

# Verificación
# ============

def test_lazos() -> None:
    ej1 = creaGrafo_(Orientacion.D, (1,3), [(1,1),(2,3),(3,2),(3,3)])
    ej2 = creaGrafo_(Orientacion.ND, (1,3), [(2,3),(3,1)])
    assert lazos(ej1) == [(1,1),(3,3)]
    assert lazos(ej2) == []
    assert nLazos(ej1) == 2
    assert nLazos(ej2) == 0
    print("Verificado")

# La verificación es
#    >>> test_lazos()
#    Verificado

from src.TAD.Grafo import (Grafo, Orientacion, Vertice, aristaEn, creaGrafo_,

nodos)

def lazos(g: Grafo) -> list[tuple[Vertice, Vertice]]:

return [(x, x) for x in nodos(g) if aristaEn(g, (x, x))]

def nLazos(g: Grafo) -> int:

return len(lazos(g))

# Verificación

# ============

def test_lazos() -> None:

ej1 = creaGrafo_(Orientacion.D, (1,3), [(1,1),(2,3),(3,2),(3,3)])

ej2 = creaGrafo_(Orientacion.ND, (1,3), [(2,3),(3,1)])

assert lazos(ej1) == [(1,1),(3,3)]

assert lazos(ej2) == []

assert nLazos(ej1) == 2

assert nLazos(ej2) == 0

print("Verificado")

# La verificación es

# >>> test_lazos()

# Verificado

TAD de los grafos: Contiguos de un vértice

PorJosé A. Alonso 30-mayo-20233-junio-2023

En un un grafo g, los contiguos de un vértice v es el conjuntos de vértices x de g tales que x es adyacente o incidente con v.

Usando el tipo abstracto de datos de los grafos, definir la función,

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

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

tal que contiguos g v es el conjunto de los vértices de g contiguos con el vértice v. Por ejemplo,

   λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> contiguos g1 1
   [2,3]
   λ> contiguos g1 2
   [2,1,3]
   λ> contiguos g1 3
   [1,2]
   λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> contiguos g2 1
   [2,3]
   λ> contiguos g2 2
   [1,2,3]
   λ> contiguos g2 3
   [1,2]

λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]

λ> contiguos g1 1

[2,3]

λ> contiguos g1 2

[2,1,3]

λ> contiguos g1 3

[1,2]

λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]

λ> contiguos g2 1

[2,3]

λ> contiguos g2 2

[1,2,3]

λ> contiguos g2 3

[1,2]

Soluciones

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

Soluciones en Haskell

module Grafo_Contiguos_de_un_vertice where

import TAD.Grafo (Grafo, Orientacion (D, ND), adyacentes, creaGrafo')
import Grafo_Incidentes_de_un_vertice (incidentes)
import Data.List (nub)
import Data.Ix
import Test.Hspec

contiguos :: (Ix v,Num p) => Grafo v p -> v -> [v]
contiguos g v = nub (adyacentes g v ++ incidentes g v)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    contiguos g1 1 `shouldBe` [2,3]
  it "e2" $
    contiguos g1 2 `shouldBe` [2,1,3]
  it "e3" $
    contiguos g1 3 `shouldBe` [1,2]
  it "e4" $
    contiguos g2 1 `shouldBe` [2,3]
  it "e5" $
    contiguos g2 2 `shouldBe` [1,2,3]
  it "e6" $
    contiguos g2 3 `shouldBe` [1,2]
  where
    g1, g2 :: Grafo Int Int
    g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]
    g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--
--    Finished in 0.0005 seconds
--    6 examples, 0 failures

module Grafo_Contiguos_de_un_vertice where

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

import Grafo_Incidentes_de_un_vertice (incidentes)

import Data.List (nub)

import Data.Ix

import Test.Hspec

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

contiguos g v = nub (adyacentes g v ++ incidentes g v)

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

contiguos g1 1 `shouldBe` [2,3]

it "e2" $

contiguos g1 2 `shouldBe` [2,1,3]

it "e3" $

contiguos g1 3 `shouldBe` [1,2]

it "e4" $

contiguos g2 1 `shouldBe` [2,3]

it "e5" $

contiguos g2 2 `shouldBe` [1,2,3]

it "e6" $

contiguos g2 3 `shouldBe` [1,2]

where

g1, g2 :: Grafo Int Int

g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]

g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- e6

-- Finished in 0.0005 seconds

-- 6 examples, 0 failures

Soluciones en Python

from src.Grafo_Incidentes_de_un_vertice import incidentes
from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_


def contiguos(g: Grafo, v: Vertice) -> list[Vertice]:
    return list(set(adyacentes(g, v) + incidentes(g, v)))

# Verificación
# ============

def test_contiguos() -> None:
    g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,2),(3,1),(3,2)])
    g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,2),(3,1),(3,2)])
    assert contiguos(g1, 1) == [2, 3]
    assert contiguos(g1, 2) == [1, 2, 3]
    assert contiguos(g1, 3) == [1, 2]
    assert contiguos(g2, 1) == [2, 3]
    assert contiguos(g2, 2) == [1, 2, 3]
    assert contiguos(g2, 3) == [1, 2]
    print("Verificado")

# La verificación es
#    >>> test_contiguos()
#    Verificado

from src.Grafo_Incidentes_de_un_vertice import incidentes

from src.TAD.Grafo import Grafo, Orientacion, Vertice, adyacentes, creaGrafo_

def contiguos(g: Grafo, v: Vertice) -> list[Vertice]:

return list(set(adyacentes(g, v) + incidentes(g, v)))

# Verificación

# ============

def test_contiguos() -> None:

g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,2),(3,1),(3,2)])

g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,2),(3,1),(3,2)])

assert contiguos(g1, 1) == [2, 3]

assert contiguos(g1, 2) == [1, 2, 3]

assert contiguos(g1, 3) == [1, 2]

assert contiguos(g2, 1) == [2, 3]

assert contiguos(g2, 2) == [1, 2, 3]

assert contiguos(g2, 3) == [1, 2]

print("Verificado")

# La verificación es

# >>> test_contiguos()

# Verificado

TAD de los grafos: Incidentes de un vértice

PorJosé A. Alonso 29-mayo-20233-junio-2023

En un un grafo g, los incidentes de un vértice v es el conjuntos de vértices x de g para los que hay un arco (o una arista) de x a v; es decir, que v es adyacente a x.

Usando el tipo abstracto de datos de los grafos, definir la función,

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

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

tal que incidentes g v es la lista de los vértices incidentes en el vértice v. Por ejemplo,

   λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> incidentes g1 1
   [3]
   λ> incidentes g1 2
   [1,2,3]
   λ> incidentes g1 3
   []
   λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]
   λ> incidentes g2 1
   [2,3]
   λ> incidentes g2 2
   [1,2,3]
   λ> incidentes g2 3
   [1,2]

λ> g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]

λ> incidentes g1 1

[3]

λ> incidentes g1 2

[1,2,3]

λ> incidentes g1 3

[]

λ> g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]

λ> incidentes g2 1

[2,3]

λ> incidentes g2 2

[1,2,3]

λ> incidentes g2 3

[1,2]

Soluciones

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

Soluciones en Haskell

module Grafo_Incidentes_de_un_vertice where

import TAD.Grafo (Grafo, Orientacion (D, ND), nodos,  adyacentes, creaGrafo')
import Data.Ix
import Test.Hspec

incidentes :: (Ix v,Num p) => Grafo v p -> v -> [v]
incidentes g v = [x | x <- nodos g, v `elem` adyacentes g x]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    incidentes g1 1 `shouldBe` [3]
  it "e2" $
    incidentes g1 2 `shouldBe` [1,2,3]
  it "e3" $
    incidentes g1 3 `shouldBe` []
  it "e4" $
    incidentes g2 1 `shouldBe` [2,3]
  it "e5" $
    incidentes g2 2 `shouldBe` [1,2,3]
  it "e6" $
    incidentes g2 3 `shouldBe` [1,2]
  where
    g1, g2 :: Grafo Int Int
    g1  = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]
    g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--
--    Finished in 0.0005 seconds
--    6 examples, 0 failures

module Grafo_Incidentes_de_un_vertice where

import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, adyacentes, creaGrafo')

import Data.Ix

import Test.Hspec

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

incidentes g v = [x | x <- nodos g, v `elem` adyacentes g x]

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

incidentes g1 1 `shouldBe` [3]

it "e2" $

incidentes g1 2 `shouldBe` [1,2,3]

it "e3" $

incidentes g1 3 `shouldBe` []

it "e4" $

incidentes g2 1 `shouldBe` [2,3]

it "e5" $

incidentes g2 2 `shouldBe` [1,2,3]

it "e6" $

incidentes g2 3 `shouldBe` [1,2]

where

g1, g2 :: Grafo Int Int

g1 = creaGrafo' D (1,3) [(1,2),(2,2),(3,1),(3,2)]

g2 = creaGrafo' ND (1,3) [(1,2),(2,2),(3,1),(3,2)]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- e6

-- Finished in 0.0005 seconds

-- 6 examples, 0 failures

Soluciones en Python

from src.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, creaGrafo_,
                           nodos)


def incidentes(g: Grafo, v: Vertice) -> list[Vertice]:
    return [x for x in nodos(g) if v in adyacentes(g, x)]

# Verificación
# ============

def test_incidentes() -> None:
    g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,2),(3,1),(3,2)])
    g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,2),(3,1),(3,2)])
    assert incidentes(g1,1) == [3]
    assert incidentes(g1,2) == [1, 2, 3]
    assert incidentes(g1,3) == []
    assert incidentes(g2, 1) == [2, 3]
    assert incidentes(g2, 2) == [1, 2, 3]
    assert incidentes(g2, 3) == [1, 2]
    print("Verificado")

# La verificación es
#    >>> test_incidentes()
#    Verificado

from src.TAD.Grafo import (Grafo, Orientacion, Vertice, adyacentes, creaGrafo_,

nodos)

def incidentes(g: Grafo, v: Vertice) -> list[Vertice]:

return [x for x in nodos(g) if v in adyacentes(g, x)]

# Verificación

# ============

def test_incidentes() -> None:

g1 = creaGrafo_(Orientacion.D, (1,3), [(1,2),(2,2),(3,1),(3,2)])

g2 = creaGrafo_(Orientacion.ND, (1,3), [(1,2),(2,2),(3,1),(3,2)])

assert incidentes(g1,1) == [3]

assert incidentes(g1,2) == [1, 2, 3]

assert incidentes(g1,3) == []

assert incidentes(g2, 1) == [2, 3]

assert incidentes(g2, 2) == [1, 2, 3]

assert incidentes(g2, 3) == [1, 2]

print("Verificado")

# La verificación es

# >>> test_incidentes()

# Verificado

TAD de los grafos: Número de vértices

PorJosé A. Alonso 26-mayo-20233-junio-2023

Usando el tipo abstracto de datos de los grafos, definir la función,

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

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

tal que nVertices g es el número de vértices del grafo g. Por ejemplo,

   nVertices (creaGrafo' D (1,5) [(1,2),(3,1)])   ==  5
   nVertices (creaGrafo' ND (2,4) [(1,2),(3,1)])  ==  3

1 2	nVertices (creaGrafo' D (1,5) [(1,2),(3,1)]) == 5 nVertices (creaGrafo' ND (2,4) [(1,2),(3,1)]) == 3

Soluciones

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

Soluciones en Haskell

module Grafo_Numero_de_vertices where

import TAD.Grafo (Grafo, Orientacion (D, ND), nodos, creaGrafo')
import Data.Ix

nVertices :: (Ix v, Num p) => Grafo v p ->  Int
nVertices = length . nodos

module Grafo_Numero_de_vertices where

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

import Data.Ix

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

nVertices = length . nodos

Soluciones en Python

from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos


def nVertices(g: Grafo) -> int:
    return len(nodos(g))

from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_, nodos

def nVertices(g: Grafo) -> int:

return len(nodos(g))

TAD de los grafos: Grafos ciclos

PorJosé A. Alonso 25-mayo-20233-junio-2023

El ciclo de orden n, C(n), es un grafo no dirigido cuyo conjunto de vértices es {1,…,n} y las aristas son

   (1,2), (2,3), ..., (n-1,n), (n,1)

1	(1,2), (2,3), ..., (n-1,n), (n,1)

Usando el tipo abstracto de datos de los grafos, definir la función,

   grafoCiclo :: Int -> Grafo Int Int

1	grafoCiclo :: Int -> Grafo Int Int

tal que (grafoCiclo n) es el grafo ciclo de orden n. Por ejemplo,

   λ> grafoCiclo 3
   G ND ([1,2,3],[(1,2),(1,3),(2,3)])

1 2	λ> grafoCiclo 3 G ND ([1,2,3],[(1,2),(1,3),(2,3)])

Soluciones

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

Soluciones en Haskell

module Grafo_Grafos_ciclos where

import TAD.Grafo (Grafo, Orientacion (ND), creaGrafo')
import Test.Hspec (Spec, hspec, it, shouldBe)

grafoCiclo :: Int -> Grafo Int Int
grafoCiclo n =
  creaGrafo' ND (1,n) ((n,1):[(x,x+1) | x <- [1..n-1]])

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    show (grafoCiclo 3) `shouldBe`
    "G ND ([1,2,3],[(1,2),(1,3),(2,3)])"

-- La verificación es
--    λ> verifica
--
--    e1
--
--    Finished in 0.0006 seconds
--    1 example, 0 failures

module Grafo_Grafos_ciclos where

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

import Test.Hspec (Spec, hspec, it, shouldBe)

grafoCiclo :: Int -> Grafo Int Int

grafoCiclo n =

creaGrafo' ND (1,n) ((n,1):[(x,x+1) | x <- [1..n-1]])

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

show (grafoCiclo 3) `shouldBe`

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

-- La verificación es

-- λ> verifica

-- e1

-- Finished in 0.0006 seconds

-- 1 example, 0 failures

Soluciones en Python

from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_


def grafoCiclo(n: int) -> Grafo:
    return creaGrafo_(Orientacion.ND,
                      (1, n),
                      [(n,1)] + [(x, x + 1) for x in range(1, n)])

# Verificación
# ============

def test_grafoCiclo() -> None:
    assert str(grafoCiclo(3)) == \
        "G ND ([1, 2, 3], [(1, 2), (1, 3), (2, 3)])"
    print("Verificado")

# La verificación es
#    >>> test_grafoCiclo()
#    Verificado

from src.TAD.Grafo import Grafo, Orientacion, creaGrafo_

def grafoCiclo(n: int) -> Grafo:

return creaGrafo_(Orientacion.ND,

(1, n),

[(n,1)] + [(x, x + 1) for x in range(1, n)])

# Verificación

# ============

def test_grafoCiclo() -> None:

assert str(grafoCiclo(3)) == \

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

print("Verificado")

# La verificación es

# >>> test_grafoCiclo()

# Verificado

Meses: mayo 2023

TAD de los grafos: Lazos de un grafo

TAD de los grafos: Contiguos de un vértice

TAD de los grafos: Incidentes de un vértice

TAD de los grafos: Número de vértices

TAD de los grafos: Grafos ciclos

Entradas recientes

Buscar

Correo electrónico