Relación transitiva
De Wikipedia, la enciclopedia libre
Una relación binaria R sobre un conjunto A es transitiva cuando se cumple: siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el tercero.
Esto es:
Una relación R es transitiva si: a R b y b R c se cumple a R c.
La propiedad anterior se conoce como transitividad.
[editar] Ejemplos
La relación binaria "menor que" en los enteros es transitiva:
Si
y
entonces
.
Así, puesto que 2 < 5 y 5 < 7, la transitividad implica que 2<7.
En general las relaciones de orden (ser menor, mayor, igual, menor o igual, mayor o igual) son transitivas.
La relación binaria "divide a" en los enteros también es transitiva. Denotando por a | b a la expresión "a divide a b":
Si
y
entonces
.
Dado que 3|12 (3 divide a 12) y 12|48 (12 divide a 48), la transitividad establece que 3|48 (3 divide a 48).
Sin embargo, no todas las relaciones binarias son transitivas. La relación "no es subconjunto" no es transitiva. Por ejemplo, si X = {1,2,3}, Y={2,3,4,5}, Z={1,2,3,4}. Entonces
Se cumple
y
pero no se cumple
puesto que X es subconjunto de Z.
Otro ejemplo de relación binaria que no es transitiva es "ser la mitad de": 5 es la mitad de 10 y 10 es la mitad de 20, pero 5 no es la mitad de 20.
[editar] Representación
Una relación binaria se puede representar como pares ordenados, mediante una matriz de adyacencia o mediante un grafo. Para el caso de una relación transitiva, cada una de estas representaciones tiene características especiales:
- Como pares ordenados,
- Como matriz de adyacencia M, la matriz es tal que
- Como grafo, cada vez que desde un nodo v1 se pueda llegar a otro v3, pasando primero por un nodo intermedio v2, entonces también existirá la arista (v1,v3).
