TAD de los grafos - Grafos ciclo
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 abstrado 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