Menu Close

El tipo abstracto de datos de los grafos

José A. Alonso, ,

1. El tipo abstracto de datos de los grafos

Un grafo es una estructura que consta de un conjunto de vértices y un conjunto de aristas que conectan los vértices entre sí. Cada vértice representa una entidad o un elemento, y cada arista representa una relación o conexión entre dos vértices.

Por ejemplo,

         12
    1 -------- 2
    | \78     /|
    |  \   32/ |
    |   \   /  |
  34|     5    |55
    |   /   \  |
    |  /44   \ |
    | /     93\|
    3 -------- 4
         61

representa un grafo no dirigido, lo que significa que las aristas tienen una dirección específica. Cada arista tiene un peso asociado, que puede representar una medida o una valoración de la relación entre los vértices que conecta.

El grafo consta de cinco vértices numerados del 1 al 5. Las aristas especificadas en la lista indican las conexiones entre los vértices y sus respectivos pesos. Por ejemplo, la arista (1,2,12) indica que existe una conexión entre el vértice 1 y el vértice 2 con un peso de 12.

En el grafo representado, se pueden observar las conexiones entre los vértices de la siguiente manera:

  • El vértice 1 está conectado con el vértice 2 (peso 12), el vértice 3 (peso 34) y el vértice 5 (peso 78).
  • El vértice 2 está conectado con el vértice 4 (peso 55) y el vértice 5 (peso 32).
  • El vértice 3 está conectado con el vértice 4 (peso 61) y el vértice 5 (peso 44).
  • El vértice 4 está conectado con el vértice 5 (peso 93).

Las operaciones del tipo abstracto de datos (TAD) de los grafos son

   creaGrafo  :: (Ix v, Num p, Ord v, Ord p) =>
                  Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
   creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>
                  Orientacion -> (v,v) -> [(v,v)] -> Grafo v p
   dirigido   :: (Ix v,Num p) => (Grafo v p) -> Bool
   adyacentes :: (Ix v,Num p) => (Grafo v p) -> v -> [v]
   nodos      :: (Ix v,Num p) => (Grafo v p) -> [v]
   aristas    :: (Ix v,Num p) => (Grafo v p) -> [(v,v,p)]
   aristaEn   :: (Ix v,Num p) => (Grafo v p) -> (v,v) -> Bool
   peso       :: (Ix v,Num p) => v -> v -> (Grafo v p) -> p

tales que
+ creaGrafo o cs as es un grafo (dirigido o no, según el de o), con el par de cotas cs y listas de aristas as (cada arista es un trío formado por los dos vértices y su peso).
+ creaGrafo' es la versión de creaGrafo para los grafos sin pesos.
+ dirigido g se verifica si g es dirigido.
+ nodos g es la lista de todos los nodos del grafo g.
+ aristas g es la lista de las aristas del grafo g.
+ adyacentes g v es la lista de los vértices adyacentes al nodo v en el grafo g.
+ aristaEn g a se verifica si a es una arista del grafo g.
+ peso v1 v2 g es el peso de la arista que une los vértices v1 y v2 en el grafo g.

Usando el TAD de los grafos, el grafo anterior se puede definir por

   creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                       (2,4,55),(2,5,32),
                       (3,4,61),(3,5,44),
                       (4,5,93)]

con los siguientes argumentos:

  • ND: Es un parámetro de tipo Orientacion que indica si el es dirigido o no. En este caso, se utiliza ND, lo que significa “no dirigido”. Por lo tanto, el grafo creado será no dirigido, lo que implica que las aristas no tienen una dirección específica.
  • (1,5): Es el par de cotas que define los vértices del grafo. En este caso, el grafo tiene vértices numerados desde 1 hasta 5.
  • [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),(3,5,44),(4,5,93)]: Es una lista de aristas, donde cada arista está representada por un trío de valores. Cada trío contiene los dos vértices que están conectados por la arista y el peso de dicha arista.

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:
+ mediante lista de adyacencia,
+ mediante vector de adyacencia y
+ mediante matriz de adyacencia.

Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2. Los grafos en Haskell

2.1. El tipo abstracto de datos de los grafos en Haskell

El TAD de los grafos se encuentra en el módulo Grafo.hs cuyo contenido es el siguiente:

module TAD.Grafo
  (Orientacion (..),
   Grafo,
   creaGrafo,
   creaGrafo',
   dirigido,
   adyacentes,
   nodos,
   aristas,
   aristaEn,
   peso
  ) where
 
import TAD.GrafoConListaDeAdyacencia
-- import TAD.GrafoConVectorDeAdyacencia
-- import TAD.GrafoConMatrizDeAdyacencia

2.2. Implementación de los grafos mediante listas de adyacencia

La implementación se encuentra en el módulo GrafoConListaDeAdyacencia cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}
 
module TAD.GrafoConListaDeAdyacencia
    (Orientacion (..),
     Grafo,
     creaGrafo,
     creaGrafo',
     dirigido,
     adyacentes,
     nodos,
     aristas,
     aristaEn,
     peso
    ) where
 
-- Librerías auxiliares                                               --
import Data.Array
import Data.List
 
-- Orientacion es D (dirigida) ó ND (no dirigida).
data Orientacion = D | ND
  deriving (Eq, Show)
 
-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.
data Grafo v p = G Orientacion ([v],[((v,v),p)])
  deriving Eq
 
-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por
-- ejemplo,
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(3,2)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
escribeGrafo :: (Ix v,Num p,Eq p,Show v,Show p) => Grafo v p -> String
escribeGrafo (G o (vs,as)) =
  "G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")"
  where
    aristasReducidas
      | o == D    = as
      | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]
    escribeAristas
      | ponderado = show aristasReducidas
      | otherwise = show [a | (a,_) <- aristasReducidas]
    ponderado = any (\((_,_),p) -> p /= 0) as
 
-- Procedimiento de escritura de grafos
instance (Ix v,Num p,Eq p,Show v,Show p) => Show (Grafo v p) where
  show = escribeGrafo
 
-- (creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un trío
-- formado por los dos vértices y su peso). Por ejemplo,
--    λ> creaGrafo ND (1,3) [(1,2,12),(1,3,34)]
--    G ND ([1,2,3],[((1,2),12),((1,3),34),((2,1),12),((3,1),34)])
--    λ> creaGrafo D (1,3) [(1,2,12),(1,3,34)]
--    G D ([1,2,3],[((1,2),12),((1,3),34)])
--    λ> creaGrafo D (1,4) [(1,2,12),(1,3,34)]
--    G D ([1,2,3,4],[((1,2),12),((1,3),34)])
creaGrafo :: (Ix v, Num p, Ord v, Ord p) =>
             Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
creaGrafo o cs as =
  G o (range cs,
       sort ([((x1,x2),p) | (x1,x2,p) <- as] ++
             if o == D then []
             else [((x2,x1),p) | (x1,x2,p) <- as, x1 /= x2]))
 
-- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un par
-- de vértices y se supone que su peso es 0). Por ejemplo,
--    λ> creaGrafo' ND (1,3) [(2,1),(1,3)]
--    G ND ([1,2,3],[(1,2),(1,3)])
--    λ> creaGrafo' D (1,3) [(2,1),(1,3)]
--    G D ([1,2,3],[(1,3),(2,1)])
creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>
              Orientacion -> (v,v) -> [(v,v)] -> Grafo v p
creaGrafo' o cs as =
  creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]
 
-- ejGrafoND es el grafo
--             12
--        1 -------- 2
--        | \78     /|
--        |  \   32/ |
--        |   \   /  |
--      34|     5    |55
--        |   /   \  |
--        |  /44   \ |
--        | /     93\|
--        3 -------- 4
--             61
-- Se define por
ejGrafoND :: Grafo Int Int
ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                                (2,4,55),(2,5,32),
                                (3,4,61),(3,5,44),
                                (4,5,93)]
 
ejGrafoD :: Grafo Int Int
ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
                              (2,4,55),(2,5,32),
                              (3,4,61),(3,5,44),
                              (4,5,93)]
 
-- (dirigido g) se verifica si g es dirigido. Por ejemplo,
--    dirigido ejGrafoD   ==  True
--    dirigido ejGrafoND  ==  False
dirigido :: (Ix v,Num p) => Grafo v p -> Bool
dirigido (G o _) = o == D
 
-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,
--    nodos ejGrafoND  ==  [1,2,3,4,5]
--    nodos ejGrafoD   ==  [1,2,3,4,5]
nodos :: (Ix v,Num p) => Grafo v p -> [v]
nodos (G _ (ns,_)) = ns
 
-- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en
-- el grafo g. Por ejemplo,
--    adyacentes ejGrafoND 4  ==  [2,3,5]
--    adyacentes ejGrafoD  4  ==  [5]
adyacentes :: (Ix v, Num p) => Grafo v p -> v -> [v]
adyacentes (G _ (_,e)) v = nub [u | ((w,u),_) <- e, w == v]
 
-- (aristaEn g a) se verifica si a es una arista del grafo g. Por
-- ejemplo,
--    aristaEn ejGrafoND (5,1)  ==  True
--    aristaEn ejGrafoND (4,1)  ==  False
--    aristaEn ejGrafoD  (5,1)  ==  False
--    aristaEn ejGrafoD  (1,5)  ==  True
aristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool
aristaEn g (x,y) = y `elem` adyacentes g x
 
-- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2
-- en el grafo g. Por ejemplo,
--    peso 1 5 ejGrafoND  ==  78
--    peso 1 5 ejGrafoD   ==  78
peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p
peso x y (G _ (_,gs)) = head [c | ((x',y'),c) <- gs, (x,y) == (x',y')]
 
-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,
--    λ> aristas ejGrafoD
--    [((1,2),12),((1,3),34),((1,5),78),
--     ((2,4),55),((2,5),32),
--     ((3,4),61),((3,5),44),
--     ((4,5),93)]
--    λ> aristas ejGrafoND
--    [((1,2),12),((1,3),34),((1,5),78),
--     ((2,1),12),((2,4),55),((2,5),32),
--     ((3,1),34),((3,4),61),((3,5),44),
--     ((4,2),55),((4,3),61),((4,5),93),
--     ((5,1),78),((5,2),32),((5,3),44),((5,4),93)]
aristas :: (Ix v,Num p) => Grafo v p -> [((v,v),p)]
aristas (G _ (_,g)) = [((v1,v2),p) | ((v1,v2),p) <- g]

2.3. Implementación de los grafos mediante vectores de adyacencia

La implementación se encuentra en el módulo GrafoConVectorDeAdyacencia cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}
 
module TAD.GrafoConVectorDeAdyacencia
  (Orientacion (..),
   Grafo,
   creaGrafo,
   creaGrafo',
   dirigido,
   adyacentes,
   nodos,
   aristas,
   aristaEn,
   peso
  ) where
 
-- Librerías auxiliares
import Data.Array (Array, Ix, accumArray, indices, (!))
import Data.List (sort)
import Test.QuickCheck
 
-- Orientacion es D (dirigida) ó ND (no dirigida).
data Orientacion = D | ND
  deriving (Eq, Show)
 
-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.
data Grafo v p = G Orientacion (Array v [(v,p)])
  deriving Eq
 
-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por
-- ejemplo,
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(3,2)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
escribeGrafo :: (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Grafo v p -> String
escribeGrafo g@(G o _) =
  "G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")"
  where
    as = sort (aristas g)
    vs = nodos g
    aristasReducidas
      | o == D    = as
      | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]
    escribeAristas
      | ponderado = show aristasReducidas
      | otherwise = show [a | (a,_) <- aristasReducidas]
    ponderado = any (\((_,_),p) -> p /= 0) as
 
-- Procedimiento de escritura de grafos
instance (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Show (Grafo v p) where
  show = escribeGrafo
 
-- (creaGrafo o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un trío
-- formado por los dos vértices y su peso). Ver el ejemplo a continuación.
creaGrafo :: (Ix v, Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
creaGrafo o cs vs =
  G o (accumArray (\xs x -> xs++[x]) [] cs
                  ((if o == D then []
                    else [(x2,(x1,p))|(x1,x2,p) <- vs, x1 /= x2]) ++
                   [(x1,(x2,p)) | (x1,x2,p) <- vs]))
 
-- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un par
-- de vértices y se supone que su peso es 0). Por ejemplo,
--    λ> creaGrafo' ND (1,3) [(2,1),(1,3)]
--    G ND ([1,2,3],[(1,2),(1,3)])
--    λ> creaGrafo' D (1,3) [(2,1),(1,3)]
--    G D ([1,2,3],[(1,3),(2,1)])
creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>
              Orientacion -> (v,v) -> [(v,v)] -> Grafo v p
creaGrafo' o cs as =
  creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]
 
-- ejGrafoND es el grafo
--             12
--        1 -------- 2
--        | \78     /|
--        |  \   32/ |
--        |   \   /  |
--      34|     5    |55
--        |   /   \  |
--        |  /44   \ |
--        | /     93\|
--        3 -------- 4
--             61
-- representado mediante un vector de adyacencia; es decir,
--    λ> ejGrafoND
--    G ND ([1,2,3,4,5],
--          [((1,2),12),((1,3),34),((1,5),78),
--           ((2,4),55),((2,5),32),
--           ((3,4),61),((3,5),44),
--           ((4,5),93)])
ejGrafoND :: Grafo Int Int
ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                                (2,4,55),(2,5,32),
                                (3,4,61),(3,5,44),
                                (4,5,93)]
 
-- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas;
-- es decir,
--    λ> ejGrafoD
--    G D ([1,2,3,4,5],
--         [((1,2),12),((1,3),34),((1,5),78),
--          ((2,4),55),((2,5),32),
--          ((3,4),61),((3,5),44),
--          ((4,5),93)])
ejGrafoD :: Grafo Int Int
ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
                              (2,4,55),(2,5,32),
                              (3,4,61),(3,5,44),
                              (4,5,93)]
 
-- (dirigido g) se verifica si g es dirigido. Por ejemplo,
--    dirigido ejGrafoD   ==  True
--    dirigido ejGrafoND  ==  False
dirigido :: (Ix v,Num p) => Grafo v p -> Bool
dirigido (G o _) = o == D
 
-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,
--    nodos ejGrafoND  ==  [1,2,3,4,5]
--    nodos ejGrafoD   ==  [1,2,3,4,5]
nodos :: (Ix v,Num p) => Grafo v p -> [v]
nodos (G _ g) = indices g
 
-- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en
-- el grafo g. Por ejemplo,
--    adyacentes ejGrafoND 4  ==  [2,3,5]
--    adyacentes ejGrafoD  4  ==  [5]
adyacentes :: (Ix v,Num p) => Grafo v p -> v -> [v]
adyacentes (G _ g) v = map fst (g!v)
 
-- (aristaEn g a) se verifica si a es una arista del grafo g. Por
-- ejemplo,
--    aristaEn ejGrafoND (5,1)  ==  True
--    aristaEn ejGrafoND (4,1)  ==  False
--    aristaEn ejGrafoD (5,1)   ==  False
--    aristaEn ejGrafoD (1,5)   ==  True
aristaEn :: (Ix v,Num p) => Grafo v p -> (v,v) -> Bool
aristaEn g (x,y) = y `elem` adyacentes g x
 
-- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2
-- en el grafo g. Por ejemplo,
--    peso 1 5 ejGrafoND  ==  78
--    peso 1 5 ejGrafoD   ==  78
peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p
peso x y (G _ g) = head [c | (a,c) <- g!x , a == y]
 
-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,
--    λ> aristas ejGrafoD
--    [((1,2),12),((1,3),34),((1,5),78),
--     ((2,4),55),((2,5),32),
--     ((3,4),61),((3,5),44),
--     ((4,5),93)]
--    λ> aristas ejGrafoND
--    [((1,2),12),((1,3),34),((1,5),78),
--     ((2,1),12),((2,4),55),((2,5),32),
--     ((3,1),34),((3,4),61),((3,5),44),
--     ((4,2),55),((4,3),61),((4,5),93),
--     ((5,1),78),((5,2),32),((5,3),44),((5,4),93)]
aristas :: (Ix v,Num p) => Grafo v p -> [((v,v),p)]
aristas (G o g) = [((v1,v2),w) | v1 <- nodos (G o g) , (v2,w) <- g!v1]

2.3. Implementación de los grafos mediante vectores de adyacencia

La implementación se encuentra en el módulo GrafoConMatrizDeAdyacencia cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}
 
module TAD.GrafoConMatrizDeAdyacencia
  (Orientacion (..),
   Grafo,
   creaGrafo,
   creaGrafo',
   dirigido,
   adyacentes,
   nodos,
   aristas,
   aristaEn,
   peso
  ) where
 
-- Librerías auxiliares                                               --
import Data.Array
import Data.Maybe (isJust)
import Data.List (sort)
import Test.QuickCheck
 
-- Orientacion es D (dirigida) ó ND (no dirigida).
data Orientacion = D | ND
  deriving (Eq, Show)
 
-- (Grafo v p) es un grafo con vértices de tipo v y pesos de tipo p.
data Grafo v p = G Orientacion (Array (v,v) (Maybe p))
  deriving Eq
 
-- (escribeGrafo g) es la cadena correspondiente al grafo g. Por
-- ejemplo,
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G ND ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,5),(2,2,0)])
--    "G D ([1,2,3],[((1,2),0),((2,2),0),((2,3),5)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(2,3,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(2,3)])"
--    λ> escribeGrafo (creaGrafo D (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G D ([1,2,3],[(1,2),(2,2),(3,2)])"
--    λ> escribeGrafo (creaGrafo ND (1,3) [(1,2,0),(3,2,0),(2,2,0)])
--    "G ND ([1,2,3],[(1,2),(2,2),(2,3)])"
escribeGrafo :: (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Grafo v p -> String
escribeGrafo g@(G o _) =
  "G " ++ show o ++ " (" ++ show vs ++ "," ++ escribeAristas ++ ")"
  where
    as = sort (aristas g)
    vs = nodos g
    aristasReducidas
      | o == D    = as
      | otherwise = [((x,y),p) | ((x,y),p) <- as, x <= y]
    escribeAristas
      | ponderado = show aristasReducidas
      | otherwise = show [a | (a,_) <- aristasReducidas]
    ponderado = any (\((_,_),p) -> p /= 0) as
 
-- Procedimiento de escritura de grafos
instance (Ix v,Num p,Ord v, Ord p,Show v,Show p) => Show (Grafo v p) where
  show = escribeGrafo
 
-- (creaGrafo d cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un trío
-- formado por los dos vértices y su peso). Ver el ejemplo a continuación.
creaGrafo :: (Ix v,Num p) => Orientacion -> (v,v) -> [(v,v,p)] -> Grafo v p
creaGrafo D cs as =
  G D (matrizVacia cs // [((v1,v2),Just c) | (v1,v2,c) <- as])
creaGrafo ND cs as =
  G ND (matrizVacia cs // ([((v1,v2),Just c) | (v1,v2,c) <- as] ++
                           [((v2,v1),Just c) | (v1,v2,c) <- as, v1 /= v2]))
 
matrizVacia :: Ix v => (v,v) -> Array (v,v) (Maybe p)
matrizVacia (l,u) =
  listArray ((l,l),(u,u)) (repeat Nothing)
 
-- (creaGrafo' o cs as) es un grafo (dirigido o no, según el valor de o),
-- con el par de cotas cs y listas de aristas as (cada arista es un par
-- de vértices y se supone que su peso es 0). Por ejemplo,
--    λ> creaGrafo' ND (1,3) [(2,1),(1,3)]
--    G ND ([1,2,3],[(1,2),(1,3)])
--    λ> creaGrafo' D (1,3) [(2,1),(1,3)]
--    G D ([1,2,3],[(1,3),(2,1)])
creaGrafo' :: (Ix v, Num p, Ord v, Ord p) =>
              Orientacion -> (v,v) -> [(v,v)] -> Grafo v p
creaGrafo' o cs as =
  creaGrafo o cs [(v1,v2,0) | (v1,v2) <- as]
 
-- ejGrafoND es el grafo
--             12
--        1 -------- 2
--        | \78     /|
--        |  \   32/ |
--        |   \   /  |
--      34|     5    |55
--        |   /   \  |
--        |  /44   \ |
--        | /     93\|
--        3 -------- 4
--             61
-- representado mediante una matriz de adyacencia.
--    λ> ejGrafoND
--    G ND array ((1,1),(5,5))
--               [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),
--                ((1,4),Nothing),((1,5),Just 78),((2,1),Just 12),
--                ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),
--                ((2,5),Just 32),((3,1),Just 34),((3,2),Nothing),
--                ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),
--                ((4,1),Nothing),((4,2),Just 55),((4,3),Just 61),
--                ((4,4),Nothing),((4,5),Just 93),((5,1),Just 78),
--                ((5,2),Just 32),((5,3),Just 44),((5,4),Just 93),
--                ((5,5),Nothing)]
ejGrafoND :: Grafo Int Int
ejGrafoND = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78),
                                (2,4,55),(2,5,32),
                                (3,4,61),(3,5,44),
                                (4,5,93)]
 
-- ejGrafoD es el mismo grafo que ejGrafoND pero orientando las aristas;
-- es decir,
--    λ> ejGrafoD
--    G D (array ((1,1),(5,5))
--               [((1,1),Nothing),((1,2),Just 12),((1,3),Just 34),
--                ((1,4),Nothing),((1,5),Just 78),((2,1),Nothing),
--                ((2,2),Nothing),((2,3),Nothing),((2,4),Just 55),
--                ((2,5),Just 32),((3,1),Nothing),((3,2),Nothing),
--                ((3,3),Nothing),((3,4),Just 61),((3,5),Just 44),
--                ((4,1),Nothing),((4,2),Nothing),((4,3),Nothing),
--                ((4,4),Nothing),((4,5),Just 93),((5,1),Nothing),
--                ((5,2),Nothing),((5,3),Nothing),((5,4),Nothing),
--                ((5,5),Nothing)])
ejGrafoD :: Grafo Int Int
ejGrafoD = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),
                              (2,4,55),(2,5,32),
                              (3,4,61),(3,5,44),
                              (4,5,93)]
 
-- (dirigido g) se verifica si g es dirigido. Por ejemplo,
--    dirigido ejGrafoD   ==  True
--    dirigido ejGrafoND  ==  False
dirigido :: (Ix v,Num p) => Grafo v p -> Bool
dirigido (G o _) = o == D
 
-- (nodos g) es la lista de todos los nodos del grafo g. Por ejemplo,
--    nodos ejGrafoND  ==  [1,2,3,4,5]
--    nodos ejGrafoD   ==  [1,2,3,4,5]
nodos :: (Ix v,Num p) => Grafo v p -> [v]
nodos (G _ g) = range (l,u)
  where ((l,_),(u,_)) = bounds g
 
-- (adyacentes g v) es la lista de los vértices adyacentes al nodo v en
-- el grafo g. Por ejemplo,
--    adyacentes ejGrafoND 4  ==  [2,3,5]
--    adyacentes ejGrafoD  4  ==  [5]
adyacentes :: (Ix v,Num p,Eq p) => Grafo v p -> v -> [v]
adyacentes (G o g) v =
  [v' | v' <- nodos (G o g), isJust (g!(v,v'))]
 
-- (aristaEn g a) se verifica si a es una arista del grafo g. Por
-- ejemplo,
--    aristaEn ejGrafoND (5,1)  ==  True
--    aristaEn ejGrafoND (4,1)  ==  False
aristaEn :: (Ix v,Num p,Eq p) => Grafo v p -> (v,v) -> Bool
aristaEn (G _o g) (x,y) = isJust (g!(x,y))
 
-- (peso v1 v2 g) es el peso de la arista que une los vértices v1 y v2
-- en el grafo g. Por ejemplo,
--    peso 1 5 ejGrafoND  ==  78
--    peso 1 5 ejGrafoD   ==  78
peso :: (Ix v,Num p) => v -> v -> Grafo v p -> p
peso x y (G _ g)  = w where (Just w) = g!(x,y)
 
-- (aristas g) es la lista de las aristas del grafo g. Por ejemplo,
--    λ> aristas ejGrafoD
--    [(1,2,12),(1,3,34),(1,5,78),(2,4,55),(2,5,32),(3,4,61),
--     (3,5,44),(4,5,93)]
--    λ> aristas ejGrafoND
--    [(1,2,12),(1,3,34),(1,5,78),(2,1,12),(2,4,55),(2,5,32),
--     (3,1,34),(3,4,61),(3,5,44),(4,2,55),(4,3,61),(4,5,93),
--     (5,1,78),(5,2,32),(5,3,44),(5,4,93)]
aristas :: (Ix v,Num p, Eq p) => Grafo v p -> [((v,v),p)]
aristas g@(G _ e) = [((v1,v2),extrae(e!(v1,v2)))
                     | v1 <- nodos g,
                       v2 <- nodos g,
                       aristaEn g (v1,v2)]
  where extrae (Just w) = w
        extrae _        = error "Imposible"

3. Los grafos en Python

3.1. El tipo abstracto de los grafos en Python

La implementación se encuentra en el módulo Grafo.py cuyo contenido es el siguiente:

__all__ = [
    'Orientacion',
    'Grafo',
    'creaGrafo',
    'creaGrafo_',
    'dirigido',
    'adyacentes',
    'nodos',
    'aristas',
    'aristaEn',
    'peso'
    ]
 
from src.TAD.GrafoConListaDeAdyacencia import (Grafo, Orientacion, adyacentes,
                                               aristaEn, aristas, creaGrafo,
                                               creaGrafo_, dirigido, nodos, peso)

3.2. Implementación de los grafos mediante listas

Se define la clase Grafo con los siguientes métodos:

  • dirigido() se verifica si el grafo es dirigido.
  • nodos() es la lista de todos los nodos del grafo.
  • aristas() es la lista de las aristas del grafo.
  • adyacentes(v) es la lista de los vértices adyacentes al vértice v en el grafo.
  • aristaEn(a) se verifica si a es una arista del grafo.
  • peso(v1, v2) es el peso de la arista que une los vértices v1 y v2 en el grafo.

Por ejemplo,

>>> Grafo(Orientacion.D, (1,3), [((1,2),0),((3,2),0),((2,2),0)])
G D ([1, 2, 3], [(1, 2), (2, 2), (3, 2)])
>>> Grafo(Orientacion.ND, (1,3), [((1,2),0),((3,2),0),((2,2),0)])
G ND ([1, 2, 3], [(1, 2), (2, 2), (2, 3)])
>>> Grafo(Orientacion.ND, (1,3), [((1,2),0),((3,2),5),((2,2),0)])
G ND ([1, 2, 3], [((1, 2), 0), ((2, 2), 0), ((2, 3), 5)])
>>> Grafo(Orientacion.D, (1,3), [((1,2),0),((3,2),5),((2,2),0)])
G D ([1, 2, 3], [((1, 2), 0), ((2, 2), 0), ((3, 2), 5)])
>>> ejGrafoND: Grafo = Grafo(Orientacion.ND,
                             (1, 5),
                             [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
                              ((2, 4), 55), ((2, 5), 32),
                              ((3, 4), 61), ((3, 5), 44),
                              ((4, 5), 93)])
>>> ejGrafoND
G ND ([1, 2, 3, 4, 5],
      [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
       ((2, 4), 55), ((2, 5), 32),
       ((3, 4), 61), ((3, 5), 44),
       ((4, 5), 93)])
>> ejGrafoD: Grafo = Grafo(Orientacion.D,
                           (1,5),
                           [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
                            ((2, 4), 55), ((2, 5), 32),
                            ((3, 4), 61), ((3, 5), 44),
                            ((4, 5), 93)])
>>> ejGrafoD
G D ([1, 2, 3, 4, 5],
     [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
      ((2, 4), 55), ((2, 5), 32),
      ((3, 4), 61), ((3, 5), 44),
      ((4, 5), 93)])
>>> ejGrafoD.dirigido()
True
>>> ejGrafoND.dirigido()
False
>>> ejGrafoND.nodos()
[1, 2, 3, 4, 5]
>>> ejGrafoD.nodos()
[1, 2, 3, 4, 5]
>>> ejGrafoND.adyacentes(4)
[2, 3, 5]
>>> ejGrafoD.adyacentes(4)
[5]
>>> ejGrafoND.aristaEn((5, 1))
True
>>> ejGrafoND.aristaEn((4, 1))
False
>>> ejGrafoD.aristaEn((5, 1))
False
>>> ejGrafoD.aristaEn((1, 5))
True
>>> ejGrafoND.peso(1, 5)
78
>>> ejGrafoD.peso(1, 5)
78
>>> ejGrafoD._aristas
[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
 ((2, 4), 55), ((2, 5), 32),
 ((3, 4), 61), ((3, 5), 44),
 ((4, 5), 93)]
>>> ejGrafoND._aristas
[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
 ((2, 1), 12), ((2, 4), 55), ((2, 5), 32),
 ((3, 1), 34), ((3, 4), 61), ((3, 5), 44),
 ((4, 2), 55), ((4, 3), 61), ((4, 5), 93),
 ((5, 1), 78), ((5, 2), 32), ((5, 3), 44),
 ((5, 4), 93)]

Además se definen las correspondientes funciones. Por ejemplo,

>>> creaGrafo(Orientacion.ND, (1,3), [((1,2),12),((1,3),34)])
G ND ([1, 2, 3], [((1, 2), 12), ((1, 3), 34), ((2, 1), 12), ((3, 1), 34)])
>>> creaGrafo(Orientacion.D, (1,3), [((1,2),12),((1,3),34)])
G D ([1, 2, 3], [((1, 2), 12), ((1, 3), 34)])
>>> creaGrafo(Orientacion.D, (1,4), [((1,2),12),((1,3),34)])
G D ([1, 2, 3, 4], [((1, 2), 12), ((1, 3), 34)])
>>> ejGrafoND2: Grafo = creaGrafo(Orientacion.ND,
                                  (1,5),
                                  [((1,2),12),((1,3),34),((1,5),78),
                                   ((2,4),55),((2,5),32),
                                   ((3,4),61),((3,5),44),
                                   ((4,5),93)])
>>> ejGrafoND2
G ND ([1, 2, 3, 4, 5],
      [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
       ((2, 4), 55), ((2, 5), 32),
       ((3, 4), 61), ((3, 5), 44),
       ((4, 5), 93)])
>>> ejGrafoD2: Grafo = creaGrafo(Orientacion.D,
                                 (1,5),
                                 [((1,2),12),((1,3),34),((1,5),78),
                                  ((2,4),55),((2,5),32),
                                  ((3,4),61),((3,5),44),
                                  ((4,5),93)])
>>> ejGrafoD2
G D ([1, 2, 3, 4, 5],
     [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
      ((2, 4), 55), ((2, 5), 32),
      ((3, 4), 61), ((3, 5), 44),
      ((4, 5), 93)])
>>> creaGrafo_(Orientacion.D, (1,3), [(2, 1), (1, 3)])
G D ([1, 2, 3], [(1, 3), (2, 1)])
>>> creaGrafo_(Orientacion.ND, (1,3), [(2, 1), (1, 3)])
G ND ([1, 2, 3], [(1, 2), (1, 3)])
>>> dirigido(ejGrafoD2)
True
>>> dirigido(ejGrafoND2)
False
>>> nodos(ejGrafoND2)
[1, 2, 3, 4, 5]
>>> nodos(ejGrafoD2)
[1, 2, 3, 4, 5]
>>> adyacentes(ejGrafoND2, 4)
[2, 3, 5]
>>> adyacentes(ejGrafoD2, 4)
[5]
>>> aristaEn(ejGrafoND2, (5,1))
True
>>> aristaEn(ejGrafoND2, (4,1))
False
>>> aristaEn(ejGrafoD2, (5,1))
False
>>> aristaEn(ejGrafoD2, (1,5))
True
>>> peso(1, 5, ejGrafoND2)
78
>>> peso(1, 5, ejGrafoD2)
78
>>> aristas(ejGrafoD2)
[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
 ((2, 4), 55), ((2, 5), 32),
 ((3, 4), 61), ((3, 5), 44),
 ((4, 5), 93)]
>>> aristas(ejGrafoND2)
[((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
 ((2, 1), 12), ((2, 4), 55), ((2, 5), 32),
 ((3, 1), 34), ((3, 4), 61), ((3, 5), 44),
 ((4, 2), 55), ((4, 3), 61), ((4, 5), 93),
 ((5, 1), 78), ((5, 2), 32), ((5, 3), 44), ((5, 4), 93)]

La implementación se encuentra en el módulo GrafoConListaDeAdyacencia cuyo contenido es el siguiente:

from enum import Enum
 
Orientacion = Enum('Orientacion', ['D', 'ND'])
 
Vertice = int
Cotas = tuple[Vertice, Vertice]
Peso = float
Arista = tuple[tuple[Vertice, Vertice], Peso]
 
class Grafo:
    def __init__(self,
                 _orientacion: Orientacion,
                 _cotas: Cotas,
                 _aristas: list[Arista]):
        self._orientacion = _orientacion
        self._cotas = _cotas
        if _orientacion == Orientacion.ND:
            simetricas = [((v2, v1), p) for ((v1, v2), p)
                          in _aristas
                          if v1 != v2]
            self._aristas = sorted(_aristas + simetricas)
        else:
            self._aristas = sorted(_aristas)
 
    def nodos(self) -> list[Vertice]:
        (x, y) = self._cotas
        return list(range(x, 1 + y))
 
    def __repr__(self) -> str:
        o = self._orientacion
        vs = nodos(self)
        ns = self._aristas
        escribeOrientacion = "D" if o == Orientacion.D else "ND"
        ponderado = {p for ((_, _), p) in ns} != {0}
        aristasReducidas = ns if o == Orientacion.D \
            else [((x, y), p)
                  for ((x, y), p) in ns
                  if x <= y]
        escribeAristas = str(aristasReducidas) if ponderado \
            else str([a for (a, _) in aristasReducidas])
        return f"G {escribeOrientacion} ({vs}, {escribeAristas})"
 
    def dirigido(self) -> bool:
        return self._orientacion == Orientacion.D
 
    def adyacentes(self, v: int) -> list[int]:
        return list(set(u for ((w, u), _)
                        in self._aristas
                        if w == v))
 
    def aristaEn(self, a: tuple[Vertice, Vertice]) -> bool:
        (x, y) = a
        return y in self.adyacentes(x)
 
    def peso(self, v1: Vertice, v2: Vertice) -> Peso:
        return [p for ((x1, x2), p)
                in self._aristas
                if (x1, x2) == (v1, v2)][0]
 
def creaGrafo(o: Orientacion,
              cs: Cotas,
              as_: list[Arista]) -> Grafo:
    return Grafo(o, cs, as_)
 
def creaGrafo_(o: Orientacion,
              cs: Cotas,
              as_: list[tuple[Vertice, Vertice]]) -> Grafo:
    return Grafo(o, cs, [((v1, v2), 0) for (v1, v2) in as_])
 
def dirigido(g: Grafo) -> bool:
    return g.dirigido()
 
def nodos(g: Grafo) -> list[Vertice]:
    return g.nodos()
 
def adyacentes(g: Grafo, v: Vertice) -> list[Vertice]:
    return g.adyacentes(v)
 
def aristaEn(g: Grafo, a: tuple[Vertice, Vertice]) -> bool:
    return g.aristaEn(a)
 
def peso(v1: Vertice, v2: Vertice, g: Grafo) -> Peso:
    return g.peso(v1, v2)
 
def aristas(g: Grafo) -> list[Arista]:
    return g._aristas
 
# En los ejemplos se usarán los grafos (no dirigido y dirigido)
# correspondientes a
#             12
#        1 -------- 2
#        | \78     /|
#        |  \   32/ |
#        |   \   /  |
#      34|     5    |55
#        |   /   \  |
#        |  /44   \ |
#        | /     93\|
#        3 -------- 4
#             61
# definidos por
ejGrafoND: Grafo = Grafo(Orientacion.ND,
                         (1, 5),
                         [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
                          ((2, 4), 55), ((2, 5), 32),
                          ((3, 4), 61), ((3, 5), 44),
                          ((4, 5), 93)])
ejGrafoD: Grafo = Grafo(Orientacion.D,
                        (1,5),
                        [((1, 2), 12), ((1, 3), 34), ((1, 5), 78),
                         ((2, 4), 55), ((2, 5), 32),
                         ((3, 4), 61), ((3, 5), 44),
                         ((4, 5), 93)])
 
ejGrafoND2: Grafo = creaGrafo(Orientacion.ND,
                              (1,5),
                              [((1,2),12),((1,3),34),((1,5),78),
                               ((2,4),55),((2,5),32),
                               ((3,4),61),((3,5),44),
                               ((4,5),93)])
 
ejGrafoD2: Grafo = creaGrafo(Orientacion.D,
                             (1,5),
                             [((1,2),12),((1,3),34),((1,5),78),
                              ((2,4),55),((2,5),32),
                              ((3,4),61),((3,5),44),
                              ((4,5),93)])
Leer más →

TAD de los polinomios: Factorización de un polinomio

José A. Alonso, ,

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

   factorizacion :: Polinomio Int -> [Polinomio Int]

tal que factorizacion p es la lista de la descomposición del polinomio p en factores obtenida mediante el regla de Ruffini. Por ejemplo,

   λ> ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol1
   x^5 + 5*x^2 + 4*x
   λ> factorizacion ejPol1
   [1*x,1*x + 1,x^3 + -1*x^2 + 1*x + 4]
   λ> ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
   λ> ejPol2
   x^3 + 2*x^2 + -1*x + -2
   λ> factorizacion ejPol2
   [1*x + -1,1*x + 1,1*x + 2,1]

Soluciones

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


Soluciones en Haskell

module Pol_Factorizacion_de_un_polinomio where
 
import TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)
import Pol_Termino_independiente_de_un_polinomio (terminoIndep)
import Pol_Raices_enteras_de_un_polinomio (divisores)
import Pol_Regla_de_Ruffini (cocienteRuffini)
import Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)
import Pol_Transformaciones_polinomios_densas (densaApolinomio)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
factorizacion :: Polinomio Int -> [Polinomio Int]
factorizacion p
  | esPolCero p = [p]
  | otherwise   = aux (0 : divisores (terminoIndep p))
  where
    aux [] = [p]
    aux (r:rs)
        | esRaizRuffini r p =
            densaApolinomio [1,-r] : factorizacion (cocienteRuffini r p)
        | otherwise = aux rs
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    map show (factorizacion ejPol1)
      `shouldBe` ["1*x","1*x + 1","x^3 + -1*x^2 + 1*x + 4"]
  it "e2" $
    map show (factorizacion ejPol2)
      `shouldBe` ["1*x + -1","1*x + 1","1*x + 2","1"]
  where
    ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0015 seconds
--    2 examples, 0 failures


Soluciones en Python

from src.Pol_Raices_enteras_de_un_polinomio import divisores
from src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \
    esRaizRuffini
from src.Pol_Regla_de_Ruffini import cocienteRuffini
from src.Pol_Termino_independiente_de_un_polinomio import terminoIndep
from src.Pol_Transformaciones_polinomios_densas import densaApolinomio
from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero
 
 
def factorizacion(p: Polinomio[int]) -> list[Polinomio[int]]:
    def aux(xs: list[int]) -> list[Polinomio[int]]:
        if not xs:
            return [p]
        r, *rs = xs
        if esRaizRuffini(r, p):
            return [densaApolinomio([1, -r])] + factorizacion(cocienteRuffini(r, p))
        return aux(rs)
 
    if esPolCero(p):
        return [p]
    return aux([0] + divisores(terminoIndep(p)))
 
# Verificación
# ============
 
def test_factorizacion() -> None:
    ejPol1 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero())))
    assert list(map(str, factorizacion(ejPol1))) \
        == ["1*x", "1*x + 1", "x^3 + -1*x^2 + 1*x + 4"]
    ejPol2 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero()))))
    assert list(map(str, factorizacion(ejPol2))) \
        == ["1*x + -1", "1*x + 1", "1*x + 2", "1"]
    print("Verificado")
 
# La verificación es
#    >>> test_factorizacion()
#    Verificado
Leer más →

TAD de los polinomios: Raíces enteras de un polinomio

José A. Alonso, ,

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

    raicesRuffini :: Polinomio Int -> [Int]

tal que raicesRuffini p es la lista de las raices enteras de p, calculadas usando el regla de Ruffini. Por ejemplo,

    λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
    λ> ejPol1
    3*x^4 + -5*x^2 + 3
    λ> raicesRuffini ejPol1
    []
    λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    λ> ejPol2
    x^5 + 5*x^2 + 4*x
    λ> raicesRuffini ejPol2
    [0,-1]
    λ> ejPol3 = consPol 4 6 (consPol 1 2 polCero)
    λ> ejPol3
    6*x^4 + 2*x
    λ> raicesRuffini ejPol3
    [0]
    λ> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
    λ> ejPol4
    x^3 + 2*x^2 + -1*x + -2
    λ> raicesRuffini ejPol4
    [1,-1,-2]

Soluciones

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


Soluciones en Haskell

module Pol_Raices_enteras_de_un_polinomio where
 
import TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)
import Pol_Termino_independiente_de_un_polinomio (terminoIndep)
import Pol_Regla_de_Ruffini (cocienteRuffini)
import Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
raicesRuffini :: Polinomio Int -> [Int]
raicesRuffini p
  | esPolCero p = []
  | otherwise   = aux (0 : divisores (terminoIndep p))
  where aux [] = []
        aux (r:rs)
          | esRaizRuffini r p = r : raicesRuffini (cocienteRuffini r p)
          | otherwise         = aux rs
 
-- (divisores n) es la lista de todos los divisores enteros de n. Por
-- ejemplo,
--    divisores 4     ==  [1,-1,2,-2,4,-4]
--    divisores (-6)  ==  [1,-1,2,-2,3,-3,6,-6]
divisores :: Int -> [Int]
divisores n = concat [[x,-x] | x <- [1..abs n], rem n x == 0]
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    raicesRuffini ejPol1 `shouldBe` []
  it "e2" $
    raicesRuffini ejPol2 `shouldBe` [0,-1]
  it "e3" $
    raicesRuffini ejPol3 `shouldBe` [0]
  it "e4" $
    raicesRuffini ejPol4 `shouldBe` [1,-1,-2]
  where
    ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
    ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    ejPol3 = consPol 4 6 (consPol 1 2 polCero)
    ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--
--    Finished in 0.0013 seconds
--    4 examples, 0 failures


Soluciones en Python

from src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \
    esRaizRuffini
from src.Pol_Regla_de_Ruffini import cocienteRuffini
from src.Pol_Termino_independiente_de_un_polinomio import terminoIndep
from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero
 
 
# (divisores n) es la lista de todos los divisores enteros de n. Por
# ejemplo,
#    divisores(4)  == [1, 2, 4, -1, -2, -4]
#    divisores(-6) == [1, 2, 3, 6, -1, -2, -3, -6]
def divisores(n: int) -> list[int]:
    xs = [x for x in range(1, abs(n)+1) if n % x == 0]
    return xs + [-x for x in xs]
 
def raicesRuffini(p: Polinomio[int]) -> list[int]:
    if esPolCero(p):
        return []
    def aux(rs: list[int]) -> list[int]:
        if not rs:
            return []
        x, *xs = rs
        if esRaizRuffini(x, p):
            return [x] + raicesRuffini(cocienteRuffini(x, p))
        return aux(xs)
 
    return aux([0] + divisores(terminoIndep(p)))
 
# Verificación
# ============
 
def test_raicesRuffini() -> None:
    ejPol1 = consPol(4, 3, consPol(2, -5, consPol(0, 3, polCero())))
    assert raicesRuffini(ejPol1) == []
    ejPol2 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero())))
    assert raicesRuffini(ejPol2) == [0, -1]
    ejPol3 = consPol(4, 6, consPol(1, 2, polCero()))
    assert raicesRuffini(ejPol3) == [0]
    ejPol4 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero()))))
    assert raicesRuffini(ejPol4) == [1, -1, -2]
    print("Verificado")
 
# La verificación es
#    >>> test_raicesRuffini()
#    Verificado
Leer más →

TAD de los polinomios: Reconocimiento de raíces por la regla de Ruffini

José A. Alonso, ,

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

   esRaizRuffini :: Int -> Polinomio Int -> Bool

tal que esRaizRuffini r p se verifica si r es una raiz de p, usando para ello el regla de Ruffini. Por ejemplo,

   λ> ejPol = consPol 4 6 (consPol 1 2 polCero)
   λ> ejPol
   6*x^4 + 2*x
   λ> esRaizRuffini 0 ejPol
   True
   λ> esRaizRuffini 1 ejPol
   False

Soluciones

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


Soluciones en Haskell

module Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini where
 
import TAD.Polinomio (Polinomio, consPol, polCero)
import Pol_Regla_de_Ruffini (restoRuffini)
 
esRaizRuffini :: Int -> Polinomio Int -> Bool
esRaizRuffini r p = restoRuffini r p == 0


Soluciones en Python

from src.Pol_Regla_de_Ruffini import restoRuffini
from src.TAD.Polinomio import Polinomio, consPol, polCero
 
 
def esRaizRuffini(r: int, p: Polinomio[int]) -> bool:
    return restoRuffini(r, p) == 0
Leer más →

TAD de los polinomios: Regla de Ruffini

José A. Alonso, ,

Usando el tipo abstracto de los polinomios, definir las funciones

   cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int
   restoRuffini    :: Int -> Polinomio Int -> Int

tales que

  • cocienteRuffini r p es el cociente de dividir el polinomio p por el polinomio x-r. Por ejemplo:
     λ> ejPol = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
     λ> ejPol
     x^3 + 2*x^2 + -1*x + -2
     λ> cocienteRuffini 2 ejPol
     x^2 + 4*x + 7
     λ> cocienteRuffini (-2) ejPol
     x^2 + -1
     λ> cocienteRuffini 3 ejPol
     x^2 + 5*x + 14
  • restoRuffini r p es el resto de dividir el polinomio p por el polinomio x-r. Por ejemplo,
     λ> restoRuffini 2 ejPol
     12
     λ> restoRuffini (-2) ejPol
     0
     λ> restoRuffini 3 ejPol
     40

Comprobar con QuickCheck que, dado un polinomio p y un número entero r, las funciones anteriores verifican la propiedad de la división euclídea.

Soluciones

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


Soluciones en Haskell

import TAD.Polinomio (Polinomio, consPol, polCero)
import Pol_Transformaciones_polinomios_densas (densaApolinomio,
                                               polinomioAdensa)
import Pol_Division_de_Ruffini_con_representacion_densa (ruffiniDensa)
import Pol_Producto_polinomios (multPol)
import Pol_Suma_de_polinomios (sumaPol)
import Pol_Crea_termino (creaTermino)
import Test.QuickCheck
 
-- 1ª definición de cocienteRuffini
-- ================================
 
cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int
cocienteRuffini r p = densaApolinomio (init (ruffiniDensa r (polinomioAdensa p)))
 
-- 2ª definición de cocienteRuffini
-- ================================
 
cocienteRuffini2 :: Int -> Polinomio Int -> Polinomio Int
cocienteRuffini2 r = densaApolinomio . ruffiniDensa r . init . polinomioAdensa
 
-- 1ª definición de restoRuffini
-- =============================
 
restoRuffini :: Int -> Polinomio Int -> Int
restoRuffini r p = last (ruffiniDensa r (polinomioAdensa p))
 
-- 2ª definición de restoRuffini
-- =============================
 
restoRuffini2 :: Int -> Polinomio Int -> Int
restoRuffini2 r = last . ruffiniDensa r . polinomioAdensa
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es
prop_diviEuclidea :: Int -> Polinomio Int -> Bool
prop_diviEuclidea r p =
  p == sumaPol (multPol coci divi) rest
  where coci = cocienteRuffini r p
        divi = densaApolinomio [1,-r]
        rest = creaTermino 0 (restoRuffini r p)
 
-- La comprobación es
--    λ> quickCheck prop_diviEuclidea
--    +++ OK, passed 100 tests.


Soluciones en Python

from hypothesis import given
from hypothesis import strategies as st
 
from src.Pol_Crea_termino import creaTermino
from src.Pol_Division_de_Ruffini_con_representacion_densa import ruffiniDensa
from src.Pol_Producto_polinomios import multPol
from src.Pol_Suma_de_polinomios import sumaPol
from src.Pol_Transformaciones_polinomios_densas import (densaApolinomio,
                                                        polinomioAdensa)
from src.TAD.Polinomio import (Polinomio, consPol, esPolCero, polCero,
                               polinomioAleatorio)
 
 
def cocienteRuffini(r: int, p: Polinomio[int]) -> Polinomio[int]:
    if esPolCero(p):
        return polCero()
    return densaApolinomio(ruffiniDensa(r, polinomioAdensa(p))[:-1])
 
def restoRuffini(r: int, p: Polinomio[int]) -> int:
    if esPolCero(p):
        return 0
    return ruffiniDensa(r, polinomioAdensa(p))[-1]
 
# Comprobación de la propiedad
# ============================
 
# La propiedad es
@given(r=st.integers(), p=polinomioAleatorio())
def test_diviEuclidea (r: int, p: Polinomio[int]) -> None:
    coci = cocienteRuffini(r, p)
    divi = densaApolinomio([1, -r])
    rest = creaTermino(0, restoRuffini(r, p))
    assert p == sumaPol(multPol(coci, divi), rest)
 
# La comprobación es
#    src> poetry run pytest -q Pol_Regla_de_Ruffini.py
#    1 passed in 0.32s
Leer más →