Menu Close

Día: 25 de mayo de 2023

TAD de los grafos: Grafos ciclos

José A. Alonso, ,

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)

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

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

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


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
Leer más →