Ir al contenido principal

Clausura transitiva de una relación binaria

La clausura transitiva de una relación binaria R es la menor relación transitiva que contiene a R. Se puede calcular usando la composición de relaciones. Veamos un ejemplo, en el que (R ∘ S) representa la composición de R y S (definida en el ejercicio del lunes): sea

R = [(1,2),(2,5),(5,6)]

la relación R no es transitiva ya que (1,2) y (1,5) pertenecen a R pero (1,5) no pertenece; sea

R1 = R ∪ (R ∘ R)
= [(1,2),(2,5),(5,6),(1,5),(2,6)]

la relación R1 tampoco es transitiva ya que (1,2) y (2,6) pertenecen a R pero (1,6) no pertenece; sea

R2 = R1 ∪ (R1 ∘ R1)
= [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]

La relación R2 es transitiva y contiene a R. Además, R2 es la clausura transitiva de R.

Definir la función

clausuraTransitiva :: Eq a => Rel a -> Rel a

tal que (clausuraTransitiva r) es la clausura transitiva de r. Por ejemplo,

λ> clausuraTransitiva [(1,2),(2,5),(5,6)]
[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]
λ> clausuraTransitiva [(1,2),(2,5),(5,6),(6,3)]
[(1,2),(2,5),(5,6),(6,3),(1,5),(2,6),(5,3),(1,6),(2,3),(1,3)]

Soluciones

import Data.List (union, nub)

-- 1ª definición
-- =============

clausuraTransitiva1 :: Eq a => [(a,a)] -> [(a,a)]
clausuraTransitiva1 r | r1 == r   = r
                      | otherwise = clausuraTransitiva1 r1
    where r1 = r `union` composicion r r

-- (transitiva r) se verifica si la relación r es transitiva. Por
-- ejemplo,
--    transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)]  ==  True
--    transitiva [(1,1),(1,3),(3,1),(5,5)]        ==  False
transitiva :: Eq a => [(a,a)] -> Bool
transitiva r = subconjunto (composicion r r) r

-- (composicion r s) es la composición de las relaciones binarias r y
-- s. Por ejemplo,
--    λ> composicion [(1,2)] [(2,3),(2,4)]
--    [(1,3),(1,4)]
--    λ> composicion [(1,2),(5,2)] [(2,3),(2,4)]
--    [(1,3),(1,4),(5,3),(5,4)]
--    λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)]
--    [(1,3)]
composicion :: Eq a => [(a,a)] -> [(a,a)] -> [(a,a)]
composicion r s = nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v]

-- (subconjunto xs ys) se verifica si xs es un subconjunto de xs. Por
-- ejemplo,
--    subconjunto [1,3] [3,1,5]  ==  True
--    subconjunto [3,1,5] [1,3]  ==  False
subconjunto :: Eq a => [a] -> [a] -> Bool
subconjunto xs ys = all (`elem` ys) xs

-- 2ª definición
-- =============

clausuraTransitiva2 :: Eq a => [(a,a)] -> [(a,a)]
clausuraTransitiva2 r | r1 == r   = r
                      | otherwise = clausuraTransitiva2 r1
    where r1 = r `union` composicion r r