Menu Close

Etiqueta: Relaciones binarias

Representación matricial de relaciones binarias

José A. Alonso,

Dada una relación r sobre un conjunto de números enteros, la matriz asociada a r es una matriz booleana p (cuyos elementos son True o False), tal que p(i,j) = True si y sólo si i está relacionado con j mediante la relación r.

Las relaciones binarias homogéneas y las matrices booleanas se pueden representar por

   type Relacion = ([Int],[(Int,Int)])
   type Matriz = Array (Int,Int) Bool

Definir la función

   matrizRB:: Relacion -> Matriz

tal que (matrizRB r) es la matriz booleana asociada a r. Por ejemplo,

   λ> matrizRB ([1..3],[(1,1), (1,3), (3,1), (3,3)])
   array ((1,1),(3,3)) [((1,1),True) ,((1,2),False),((1,3),True),
                        ((2,1),False),((2,2),False),((2,3),False),
                        ((3,1),True) ,((3,2),False),((3,3),True)]
   λ> matrizRB ([1..3],[(1,3), (3,1)])
   array ((1,1),(3,3)) [((1,1),False),((1,2),False),((1,3),True),
                        ((2,1),False),((2,2),False),((2,3),False),
                        ((3,1),True) ,((3,2),False),((3,3),False)]
   λ> let n = 10^4 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)
   False