Diferencia entre revisiones de «Relación transitiva»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 18:46 1 dic 2009

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:

\forall a,b,c\in A,\;aRb\;\land bRc\;\Rightarrow \;aRc

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.

Ejemplos

La relación binaria "menor que" en los enteros es transitiva:

Si $\ a<b$ y $\ b<c$ entonces $\ a<c$ .

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 $\ a|b$ y $\ b|c$ entonces $\ a|c$ .

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 $X\not \subset Y$ y $Y\not \subset Z$ pero no se cumple $X\not \subset Z$ 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.

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, $\forall a,b,c\in A,\ (a,b)\in R\land (b,c)\in R\;\Rightarrow \;(a,c)\in R$

Como matriz de adyacencia $M$ , la matriz es tal que $M\lor M^{2}=M.$

Como grafo, cada vez que desde un nodo $v_{1}$ se pueda llegar a otro $v_{3}$ , pasando primero por un nodo intermedio $v_{2}$ , entonces también existirá la arista $(v_{1},v_{3})$ .

Véase también

Clausura transitiva

@@ Línea 27: / Línea 27: @@
 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.
+== Representación ==
-== expliquen bien ps y pongas ejemplos no tonterias
+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]], <math>\forall a, b, c \in A,\ (a,b)\in R \and (b,c)\in R \; \Rightarrow \; (a,c)\in R</math>
+* Como [[matriz de adyacencia]] <math>M</math>, la matriz es tal que <math>M \or M^2 = M.</math>
+* Como [[grafo]], cada vez que desde un nodo <math>v_1</math> se pueda llegar a otro <math>v_3</math>, pasando primero por un nodo intermedio <math>v_2</math>, entonces también existirá la arista <math>(v_1, v_3)</math>.
 == Véase también ==